QUESTION DESCRIPTION 

You are a waiter at a party. There are N stacked plates on pile Ao .

Each plate has a number written on it. Then there will be q iterations. In i-th iteration, you start picking up the plates in Ai-1 from the top one by one and check whether the number written on the plate is divisible by the -th prime.

If the number is divisible, you stack that plate on pile Bi .

Otherwise, you stack that plate on pile Ai . After Q iterations, plates can only be on pile B1,B2,......Bq, Aq .

Output numbers on these plates from top to bottom of each piles in order of B1,B2,....Bq, Aq . Mandatory Declaration is "vector<int> p"

Input Format

The first line contains two space separated integers, N and Q.

The next line contains N space separated integers representing the initial pile of plates, i.e., Ao .

The leftmost value represents the bottom plate of the pile.

Constraints

1<=N<=5*10^4

2<=number(i)<=10^4

1<=Q<=1200

Output Format

Output N lines. Each line contains a number written on the plate. Printing should be done in the order defined above.


TEST CASE 1 

INPUT
5 1
3 4 7 6 5
OUTPUT
4
6
3
7
5

TEST CASE 2 

INPUT
6 1 
8 1 9 2 7 3
OUTPUT
8
2
1
9
7
3

Solution : 

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main()
{
    int q, n, v;
    vector<int> primes;
    primes.push_back(2);
    primes.push_back(3);
    for(int i = 5; i <= 10000; i++)
    {
        int no = 0;
        for(int j = 2; j*j <= i; j++)
        {
            if(i%j == 0)
                no = 1;
        }
        if(!no)
            primes.push_back(i);
    }
    cin>>n>>q;
    stack<int> stack1, stack2, stack3;
    for(int i = 0 ; i < n; i++)
    {
        cin>>v;
        stack1.push(v);
    }
    for(int i = 0 ; i < q; i++)
    {
        if(stack1.empty())
            break;
        int cur = primes[i];
        while(!stack1.empty())
        {
            int ele = stack1.top();
            stack1.pop();
            if(ele%cur == 0)
            {
                stack2.push(ele);
            }
            else
            {
                stack3.push(ele);
            }
        }
        while(!stack2.empty())
        {
            cout<<stack2.top()<<endl;
            stack2.pop();
        }
        stack1 = stack3;
        while(!stack3.empty())
            stack3.pop();
    }
    while(!stack1.empty())
    {
        cout<<stack1.top()<<endl;
        stack1.pop();
    }
    return 0;
}

Waiter Problem Using Stacks: A C++ Solution
The "Waiter Problem" is a fascinating challenge that involves simulating the process of sorting plates stacked on piles based on divisibility by prime numbers over multiple iterations. This type of problem is typical in competitive programming, where efficient data structures and algorithms are necessary to handle large inputs and complex operations.
In this blog, we'll discuss how to approach the problem using stacks and vectors in C++. We'll break down the problem, understand its requirements, develop a plan for the solution, and implement the logic step by step. We'll also analyze the test cases provided to ensure the solution is robust.
Table of Contents
  1. Problem Overview and Input/Output
  2. Understanding the Divisibility Logic
  3. Approach and Algorithm Design
  4. C++ Code Implementation
  5. Explanation of the Code
  6. Sample Test Cases with Detailed Analysis
  7. Conclusion
1. Problem Overview and Input/Output
Problem Statement:
  • You are given a stack of N plates, each plate having a number written on it. The plates are arranged in an initial stack A0, and you need to perform q iterations.
  • In each iteration i, you pick up the plates from the top of the current pile (A(i-1)) and check whether the number on each plate is divisible by the i-th prime number.
    • If divisible, the plate is moved to pile Bi.
    • If not divisible, the plate is stacked on pile Ai.
  • After q iterations, plates will only be present on piles B1, B2, ..., Bq, and Aq.
  • Finally, you need to output all the plates from these piles in a specific order: first print the plates from B1, B2, ..., Bq, and then print the plates from Aq.
Input Format:
  1. The first line contains two integers N (number of plates) and Q (number of iterations).
  2. The second line contains N integers, which represent the initial stack of plates (A0).
Output Format:
  • Output N lines, where each line contains a plate number in the required order.
Constraints:
  • 1 <= N <= 50,000
  • 2 <= number(i) <= 10,000
  • 1 <= Q <= 1200
2. Understanding the Divisibility Logic
In each iteration:
  • A prime number is chosen, and each plate is checked if its number is divisible by the current prime.
  • Plates divisible by the prime are moved to the pile Bi, while non-divisible plates are moved to Ai.
By maintaining this structure, we can ensure that after each iteration, plates are divided based on their divisibility, and eventually, all plates are distributed across the piles B1, B2, ..., Bq, and Aq.
3. Approach and Algorithm Design
To solve this problem efficiently, we need to:
  1. Generate prime numbers: Since the problem involves divisibility by prime numbers, we need a list of primes to be used in each iteration.
  2. Use stacks for plate management: We'll use stacks to simulate the process of picking plates from the top and distributing them based on divisibility.
  3. Perform q iterations:
    • In each iteration, plates will be checked for divisibility by the i-th prime.
    • Plates divisible by the prime go to the pile Bi, and others go to the pile Ai.
  4. Output plates from all piles: Once the iterations are complete, we output the plates in the order from B1, B2, ..., Bq, and then Aq.
Plan:
  1. Prime Number Generation: Use the Sieve of Eratosthenes to precompute a list of prime numbers.
  2. Iteration Logic: Use two stacks for each iteration: one stack to store plates divisible by the current prime and one stack for non-divisible plates.
  3. Output: After all iterations, output the plates in the specified order.
4. C++ Code Implementation

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// Function to generate prime numbers using the Sieve of Eratosthenes
vector<int> generatePrimes(int limit) {
    vector<int> primes;
    vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= limit; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * 2; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return primes;
}

int main() {
    int N, Q;
    cin >> N >> Q;

    // Declare the initial pile of plates (A0)
    stack<int> A0;
    vector<int> plates(N);
    
    for (int i = 0; i < N; i++) {
        cin >> plates[i];
    }

    // Push plates onto A0 (note: we push in reverse order to simulate a stack)
    for (int i = N - 1; i >= 0; i--) {
        A0.push(plates[i]);
    }

    // Generate the first few primes
    vector<int> primes = generatePrimes(10000);

    // Stacks for Bi and Ai in each iteration
    vector<stack<int>> B(Q);
    stack<int> currentStack = A0, nextStack;

    // Perform Q iterations
    for (int i = 0; i < Q; i++) {
        int currentPrime = primes[i];

        // Process current stack
        while (!currentStack.empty()) {
            int plate = currentStack.top();
            currentStack.pop();

            // If divisible by the current prime, push to Bi
            if (plate % currentPrime == 0) {
                B[i].push(plate);
            } 
            // Otherwise, push to the next Ai stack
            else {
                nextStack.push(plate);
            }
        }

        // Move nextStack to currentStack for the next iteration
        currentStack = nextStack;

        // Clear nextStack for future use
        while (!nextStack.empty()) {
            nextStack.pop();
        }
    }

    // Output the plates in the required order
    for (int i = 0; i < Q; i++) {
        while (!B[i].empty()) {
            cout << B[i].top() << endl;
            B[i].pop();
        }
    }

    while (!currentStack.empty()) {
        cout << currentStack.top() << endl;
        currentStack.pop();
    }

    return 0;
}

5. Explanation of the Code
1. Prime Number Generation:
We use the Sieve of Eratosthenes to generate a list of prime numbers up to 10,000. This ensures that we have enough primes for up to 1,200 iterations.
vector<int> generatePrimes(int limit) {
    vector<int> primes;
    vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= limit; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * 2; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return primes;
}

2. Processing Plates:
We first push all the input plates onto the initial stack A0. The plates are pushed in reverse order since the leftmost value represents the bottom plate in the input.

for (int i = N - 1; i >= 0; i--) {
    A0.push(plates[i]);
}

3. Iterations:
For each iteration, we check whether each plate from the current stack is divisible by the current prime. If divisible, the plate is pushed onto stack Bi; otherwise, it goes into the next iteration stack Ai.

for (int i = 0; i < Q; i++) {
    int currentPrime = primes[i];
    while (!currentStack.empty()) {
        int plate = currentStack.top();
        currentStack.pop();
        if (plate % currentPrime == 0) {
            B[i].push(plate);
        } else {
            nextStack.push(plate);
        }
    }
    currentStack = nextStack;
    while (!nextStack.empty()) {
        nextStack.pop();
    }
}