SCRDPW Editorial

editorial
, ,
1

Problem Link
Author: @maazbinasad3
Tester: @prasoonjain006
Editorialist: @maazbinasad3
Difficulty: Easy-Medium
Prerequisites : Game theory, Strings

Problem description
You and your friend are playing a game in which either of you can remove a character from a given string of odd length until the size reaches exactly 11. If the resultant string starts with 5,you win, else you lose. You both play optimally.

Quick explanation
You will always try to remove a character other than 5 whenever you encounter it starting from beginning while your friend tries to remove character 5 from beginning because string should (or should not) start with 5 for both of you to play optimally.

Solution

Setter’s solution

  #include<vector>
  #include<iostream>
  #include<unordered_set>
  #include<algorithm>
#define pb push_back
#define vi vector<long long int>
#pragma GCC optimize("O2")



using namespace std;

typedef long long int ll;

int main(){
ll n;
cin>>n;
string str;
cin>>str;
int v=(n-11)/2;
int p=(n-11)/2;
for(int i=0;i<str.size();i++){
    if(str[i]!='5'){
        str[i]='A';
        v--;
    }
     if(v==0){
        break;
     }
}
for(int i=0;i<str.size();i++){
    if(str[i]=='5'){
        str[i]='A';
        p--;
    }
     if(p==0){
        break;
     }
}
string res;
for(int i=0;i<str.size();i++){
    if(str[i]!='A')
    res.pb(str[i]);
}
if(res[0]=='5'){
    cout<<"YES"<<"\n";
}
else{
    cout<<"NO"<<"\n";
}

}

1 Like