PROBLEM LINK:
Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest
Author: Raghav Agarwal
Tester: Miten Shah
Editorialist: Ansh Gupta
DIFFICULTY:
SIMPLE
PREREQUISITES:
Observation
PROBLEM:
There is a string S of length N consisting of only 0's and 1's. Players take turns moving - on his turn, a player chooses some block of S and erases it. The remaining parts of S are then concatenated together (without changing the order), and the other player then makes a move on this modified string.The player who is unable to make a move at the end loses the game and has to leave Wasseypur.
QUICK EXPLANATION:
Given a string of length n consisting of only 0's and 1's. Two players are playing a game. Game goes in turn, in each turn a player can erase a block from the current string and the remaining part of the string will concatenate to make the current string for another player.The player who will not be able to make a move at the end will lose the game. Assuming the game will start from the first player, find out the winner.
EXPLANATION:
Firstly, find out the different number of blocks in the given string, let say it is K. If a player erases the left most or right most block number of blocks will be reduced by 1 but if he erases any other block, the number of blocks will be reduced by 2.
Now, from the first player’s perspective,
K = 1 2 3 4 5 6 7 8 9 10 11
Condition: W L W W L W W L W W L
W - winning condition, L- Losing condition It can be seen,
if (K % 3 == 2 ) it is a losing condition for the first player otherwise winning.
TIME COMPLEXITY:
Overall time complexity would be be: O(n) per test case, where n is the size of string.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define fast_io std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string s;
cin >> s;
int cnt = 1;
for (int i = 1; i < n; i++)
cnt += s[i] != s[i - 1];
if (cnt % 3 == 2)
cout << "RAMADHIR\n";
else
cout << "SAHID\n";
}
}
Tester's Solution
// created by mtnshh
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define err() cout<<"--------------------------"<<endl;
#define errA(A) for(auto i:A) cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define ft first
#define sd second
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
#define endl "\n"
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cerr << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int max_q = 1e4;
const int max_n = 1e5;
const int max_sum_n = 1e6;
const ll N = 100005;
const ll INF = 1e12;
void solve(ll n){
string s = readStringLn(n, n);
rep(i,0,n) assert(s[i] != '0' or s[i] != '1');
ll cnt = 0;
char last = '$';
rep(i,0,n){
if(s[i] != last){
last = s[i];
cnt += 1;
}
}
if(cnt % 3 == 2) cout << "RAMADHIR" << endl;
else cout << "SAHID" << endl;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll q = readIntLn(1, max_q);
ll sum_n = 0;
while(q--){
ll n = readIntLn(1, max_n);
solve(n);
sum_n += n;
}
assert(sum_n <= max_sum_n);
assert(getchar()==-1);
}
Editorialist's Solution
#include"bits/stdc++.h"
using namespace std;
int N = 0;
void solve()
{
int n;
cin >> n;
N += n;
assert(1 <= n and n <= 1e5);
assert(1 <= N and N <= 1e6);
string s;
cin >> s;
for (int i = 0; i < n; i++) {
assert(s[i] == '0' || s[i] == '1');
}
int cnt = 1;
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1]) {
cnt++;
}
}
if (cnt % 3 == 2) {
cout << "RAMADHIR" << endl;
}
else {
cout << "SAHID" << endl;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
assert(1 <= t and t <= 1e4);
while (t--)
{
solve();
}
return 0;
}