Recent CP News

The Football Fest || FIFA One

Problem Statement

The very famous football club Manchester United decided to popularize football in India by organizing a football fest. The fest had many events for different sections of people.
For the awesome coders of Hacker Earth, there was an event called PASS and BACK. In this event, the coders were given N passes and players having ids between 1 and 1000000.
Initially, some player with a given id had the ball in his possession. The coders had to make a program to display the id of the player who possessed the ball after exactly N passes.

Description of the passes:
There were two kinds of passes:
1. P ID
2. 

Explanation :

for the first kind of pass, the player in possession of the ball passes the ball to player with id=ID while for the second kind of a pass, the player in possession of the ball passes the ball back to the player who had passed the ball to him.

NOTE:

It is guaranteed that the given order of all the passes will be a valid order.

INPUT :

The first line of the input contains the number of test cases. For each test case, two space-separated integers Nand ID ( of the player possessing the ball in the very beginning). N lines follow describing the passes. ( for a description of the passes, refer the statement above. )

OUTPUT :

Output to each test case should be a single line containing the “Player” ID (quotes for clarity) of the player who possesses the ball after N passes.

CONSTRAINTS :

1≤T≤100
1≤N≤100000

SAMPLE INPUT

1
10 23
P 86
P 63
P 60
B
P 47
B
P 99
P 9
B
B

SAMPLE OUTPUT

Player 9

Explanation

Initially, Player having id=23 posses ball. After pass 1, Player having id=86 posses ball. After pass 2, Player having id=63 posses ball. After pass 3, Player having id=60 posses ball. After pass 4, Player having id=63posses ball. After pass 5, Player having id=47 posses ball. After pass 6, Player having id=63 posses ball. After pass 7, Player having id=99 posses ball. After pass 8, Player having id=9 posses ball. After pass 9, Player having id=99 posses ball. After pass 10, Player having id=9 posses ball.

________________________________________________________________________________

SOLUTION

#include <bits/stdc++.h>

using namespace std;

stack < int > s;

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);          // Decrease Time of cin, cout.

    int n , t, d, id;
    char c;

    cin >> t;

    while(t--){

        cin >> n >> d;

        while(!s.empty()) s.pop();      // clear the stack in each test case

        s.push(d);

        for(int i = 0; i < n; i++){

            cin >> c;

            if(c == 'B'){

                int second = s.top();   // pop 2 elements
                s.pop();

                int first = s.top();
                s.pop();

                s.push(second);     // push the 2 elements in reverse order
                s.push(first);
                continue;
            }

            cin >> id;
            s.push(id);         // normal pushing in the stack 
        }

        cout << "Player " << s.top() << "\n";
    }

    return 0;
}

Brief Description:

Given two space separated integers N and ID ( of the player possessing the ball in the very beginning).
N lines follow describing the passes.

  1. P ID
  2. B

For the first kind of pass, the player in possession of the ball passes the ball to player with id=ID while for the second kind of a pass, the player in possession of the ball passes the ball back to the player who had passed the ball to him.

Print the “Player” ID (quotes for clarity) of the player who possesses the ball after N passes.
(The top value on the Stack of the passes).

Detailed Editorial:

This Question depends on your data structure knowledge as you can easily solve this
question using suitable data structure which is a stack in our question.

You have 2 types of instructions in this question:

1) PID:

So you can easily push the new ID in the stack to keep track of the latest player
who has the ball.

2) B:

Now you should pass the ball to the previous player so you can easily pop the last
player from the stack, but you must first push the current player, then the previous player
to make the previous player at the top of the stack.

Note: In the B instruction: you should also push the current player before pushing the previous
player because you want also to update the current player to be the penultimate player.

Time Complexity: O(N).

Memory Space Complexity: O(N).

{Code With Codeater}

Give Your Reviews




Leave a Reply