In this HackerEarth Passing, the Parcel problem solution Have you ever been a part of the exciting game Passing the Parcel? Sid is on a school picnic with his classmates. The teacher decides to make the whole class play the game of Passing the Parcel. Since the winner of the game gets lots of chocolates and ice cream as his/her prize, all the students are over-excited about the game, including Sid. Here are the rules of the game:

For the purpose of the game, our Parcel here is a football.
There are a total of N students in the class. Their roll numbers being.
All N students are made to sit uniformly in a circle in roll number order (ie. from 1 to N in a clockwise direction).
The Parcel is first handed over to the student with roll number 1.
The teacher starts playing a song using a loud stereo system. The lyrics of the song are denoted by a string that consists of only the letters 'a' and 'b'. Assume that each lyric of the song is a single letter.
If the lyric 'a' occurs in the song, the student who is currently holding the Parcel passes it on to the next student. This passing takes place in a clockwise direction.
If the lyric 'b' occurs in the song, the student who is currently holding the Parcel loses his/her chances of winning the game. He/she hands over the parcel to the next student (in a clockwise direction) and moves out.
The game continues until a single student survives in the end. He/she will be the winner of the game.
Note that the song repeats continuously ie. while the game is going on, if, at all the song ends, the stereo system will automatically start playing the song from the start without any delay.
Given N the number of students in the class and the lyrics of the song, you have to find out the roll number of the student who wins the game.



HackerEarth Passing the Parcel problem solution


HackerEarth Passing the Parcel problem solution.

#include<stdio.h>
int removestudent(int c[],int index,int *n)
{
    int i;
    for(i=index+1;i<=(*n);i++)
    {
        c[i-1]=c[i];
    }
    (*n)--;
}
int main()
{
    int n,l,c[1010],i,j;
    char s[1010];
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        c[i]=i;
    }
    char ch=getchar();
    scanf("%s",s);
    l=strlen(s);
    i=0;
    j=1;
    while(n>1)
    {
      if(s[i]=='b')
      {
        removestudent(c,j,&n);
        j--;
      }
      i=(i+1)%l;
      j=j+1;
      if(j>n)
      {
        j-=n;
      }
    }
    printf("%d\n",c[1]);
    return(0);
}


Second solution

#include<bits/stdc++.h>
using namespace std;

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define PII pair<int,int>
#define all(x) x.begin(),x.end()
#define VI vector<int>
#define VII vector<pair<int,int> >
#define VL vector<long long int >
#define VLL vector<pair<long long ,long long > >
#define PLL pair<long long ,long long >
#define itr iterator
#define fill(x,v) fill(all(x),v)

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define sc4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define sc5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)

#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)
#define pr4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define pr5(a,b,c,d,e) printf("%d %d %d %d %d\n",a,b,c,d,e)

#define scll(x) scanf("%lld",&x)
#define prll(x) printf("%lld\n",x)
#define ms(x) memset(x,0,sizeof(x))

#define ll long long int
#define li long int
#define ff float
#define db double

#define rep(i,a,b) for(i=a;i<b;i++)
#define repr(i,a,b) for(i=a;i>=b;i--)

#define print_v(x) for(int i=0;i<x.size();i++) cout << x[i] << " " 
#define debug(x) cout << "#debug" << " " << x << endl

#define MOD 5000000

int random_long(int digit=8)
{
   int len=digit;
   int x=0;
   for ( int i = 0; i < len; ++i )
   {
    int dig = rand() % 10;
    while ( x == 0 && dig == 0 )
      dig = rand() % 10;
    x = x * 10 + dig;
  }
   return x;
}

int random(int l, int r)
{
    int diff = r - l + 1;

    return l+random_long()%diff;

}

#define MAX 1001
bool V[MAX];
int main(){

  int n;
  sc1(n);
  assert(n<=1000 && n>=1);
  string str;
  cin >> str; 
  int i=0,j=0,k,sz;
  sz=str.length();
  assert(sz<=1000 && sz>=1);
  int ans ,temp;
  temp = n;
  while(1) {  

    if(str[i]=='b'){
      while(V[j]){
        j++;
        j%=n;
      }
      V[j]=1;
      ans = j;
      temp-- ;
    }else{

      while(V[j]){
        j++;
        j%=n;
      } 
    }
    i++;
    i%=sz;
    j++;
    j%=n;
    if(!temp)
      break;
  }
  pr1(ans+1);
  return 0;
}