結果
問題 | No.102 トランプを奪え |
ユーザー | goodbaton |
提出日時 | 2015-08-09 19:49:03 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 259 ms / 5,000 ms |
コード長 | 2,369 bytes |
コンパイル時間 | 504 ms |
コンパイル使用メモリ | 73,840 KB |
実行使用メモリ | 24,240 KB |
最終ジャッジ日時 | 2023-09-25 07:33:02 |
合計ジャッジ時間 | 1,751 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 11 ms
7,064 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 26 ms
8,868 KB |
testcase_06 | AC | 21 ms
6,952 KB |
testcase_07 | AC | 9 ms
6,008 KB |
testcase_08 | AC | 35 ms
10,924 KB |
testcase_09 | AC | 259 ms
24,240 KB |
testcase_10 | AC | 257 ms
23,116 KB |
ソースコード
#include <cstdio> #include <cstdlib> #include <iostream> #include <string> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <cstring> typedef long long ll; using namespace std; #define mod 1000000007 #define INF 1000000000 #define LLINF 2000000000000000000LL #define PI 3.1415926536 #define SIZE 1000 int memo[2][15][15][15][15][53]; int dfs(int turn,int a,int b,int c,int d,int ta,int ji){ int ret[4][4],RET; int T=ta,A=a,B=b,C=c,D=d; if(memo[turn][a+1][b+1][c+1][d+1][T]>0) return memo[turn][a+1][b+1][c+1][d+1][T]-1; if(a==0 || b==0 || c==0 || d==0){ if(turn==1){ //taro ta+=(ji+1)/2; ji-=(ji+1)/2; }else{ //jiro ji+=(ta+1)/2; ta-=(ta+1)/2; } if(a==0) a=-1; if(b==0) b=-1; if(c==0) c=-1; if(d==0) d=-1; } if(a==-1 && b==-1 && c==-1 && d==-1){ if(ta>ji){ memo[turn][A+1][B+1][C+1][D+1][T] = 3; return 2; }else if(ta==ji){ memo[turn][A+1][B+1][C+1][D+1][T] = 2; return 1; }else{ memo[turn][A+1][B+1][C+1][D+1][T] = 1; return 0; } } for(int i=0;i<4;i++) for(int j=1;j<=3;j++) ret[j][i] = 0+turn*2; //T:0 J:2 for(int i=1;i<=3;i++){ if(!turn) ta++; else ji++; if(a>=i) ret[i][0] = dfs(!turn,a-i,b,c,d,ta,ji); if(b>=i) ret[i][1] = dfs(!turn,a,b-i,c,d,ta,ji); if(c>=i) ret[i][2] = dfs(!turn,a,b,c-i,d,ta,ji); if(d>=i) ret[i][3] = dfs(!turn,a,b,c,d-i,ta,ji); } RET = 0+turn*2; for(int j=1;j<=3;j++){ for(int i=0;i<4;i++){ if(turn==0){ //taro RET = max(ret[j][i],RET); }else{ //jiro RET = min(ret[j][i],RET); } } } memo[turn][A+1][B+1][C+1][D+1][T] = RET+1; return RET; } int main(){ int a,b,c,d,sum,ans; scanf("%d%d%d%d",&a,&b,&c,&d); ans = dfs(0,a,b,c,d,0,0); if(ans==2){ puts("Taro"); }else if(ans==0){ puts("Jiro"); }else{ puts("Draw"); } return 0; }