/**
* author: NotLinux
* created: 06.09.2022 ~ 09:33:06
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
#include "/home/notlinux/debug.h"
#else
#define debug(x...) void(37)
#endif
int n,k;string str;
vector<vector<vector<int>>>dp;
vector<int>pre,suff;
//state of a game is 1 if I won this state
//state of a game is 0 if I lost this state
int func(int l,int r,int z){
if(l+r >= n)return 0;
if(dp[l][r][z]!=-1)return dp[l][r][z];//using dp optimization
int toplam=pre[l+1]+suff[n-r-1];//number of the red pebbles in the range [0,l] + [r,n]
//now we check if the game ends this turn
if((toplam-z)==k){//has the opponent lost
dp[l][r][z] = 1;
return dp[l][r][z];//return that I won in this state
}
else if(z == k){//have I lost
dp[l][r][z] = 0;
return dp[l][r][z];//return that I lost in this state
}
//now we check what happens if we go from one of two cases : p1 and p2
int p1,p2;//two possible cases
if((l+r)%2==0){//is this my turn
p1=func(l+1,r,z+(str[l]=='C'));//what happens if I take from left
p2=func(l,r+1,z+(str[n-r-1]=='C'));//what happens if I take from right
}
else {//is this his turn
p1=func(l+1,r,z);//what happens if he takes from left
p2=func(l,r+1,z);//what happens if he takes from right
}
//if I won in p1 or p2 , than I won in this state , else I lost in this state , same logic for the opponent
if((l+r)%2==0){//is this my turn
dp[l][r][z] = p1|p2;//choose the optimal for urself
}
else {//is this his turn
dp[l][r][z] = p1&p2;//he chooses optimal for himself
}
return dp[l][r][z];//return the state of the game
}
void solve(){
cin>>n>>k>>str;
dp.assign(n,vector<vector<int>>(n,vector<int>(n,-1)));
pre.resize(n+1);suff.resize(n+1);
for(int i=0;i<n;i++)pre[i+1]=pre[i]+(str[i]=='C');//building the prefix array
for(int i=n-1;i>0;i--)suff[i-1]=suff[i]+(str[i-1]=='C');//building the suffix array
cout<<(func(0,0,0)?"DA":"NE")<<endl;//if I won print DA
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);
int tt=1;
//cin >> tt;
while(tt--)solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
