Header Ad

HackerEarth Bit Flipping Game Nissan problem solution

In this HackerEarth Bit Flipping Game Nissan problem solution, Two players A and B are playing a game. They are given N binary numbers as input. Each binary number is represented as a string of characters '0' or '1'. The string always ends at '1'.  In one move each player decides a bit position p. Then he visits all the numbers and if their bit at that position is '1' then he changes it to '0'. It is mandatory to flip(change '1' to '0') a bit of at least one number in each move. The player who is unable to make a move loses. Player A begins the game.


HackerEarth Bit Flipping Game <Nissan> problem solution


HackerEarth Bit Flipping Game Nissan problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define reset(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define print(a,start,end) for(i=start;i<=end;++i) cout<<a[i];
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int f[1000001];
int main()
{
ios_base::sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n;i++)
{
string s;
cin >> s;
for(int j = 0;j < s.length(); j++)
{
if(s[j] == '1')
f[j]++;
}
}
int ct = 0;
for(int i = 0; i <= 1000000; i++)
{
if(f[i])
++ct;
}
if(ct % 2)
{
cout << "A" << endl;
cout << ct << endl;
}
else
{
cout << "B" << endl;
cout << ct << endl;
}
}


Second solution

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 1e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define PQPGB priority_queue<pii ,vector< pll >, greater< pll > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

using namespace std;

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
#endif
fast_io;
int n; cin>>n;
assert(n>=1 && n<=100000);
string s[n];
int mx=0;
for(int i=0;i<n;i++) {
cin>>s[i];
mx=max(mx,(int)s[i].size());
}
int cnt[mx+1];
mem(cnt,0);
for(int i=0;i<n;i++) {
for(int j=0;j<s[i].size();j++) {
assert(s[i][j]=='0' || s[i][j]=='1');
cnt[j]+=(s[i][j]=='1');
}
}
int ans=0;
for(int i=0;i<mx;i++) {
ans+=(cnt[i]>0);
}
if(ans&1) cout<<"A\n";
else cout<<"B\n";
cout<<ans<<endl;


return 0;
}

Post a Comment

0 Comments