Editorial for Triomino Game
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <set> #define fr(a,b,c) for (a=b;a<=c;a++) using namespace std; int g[4][888]; set <int> a; void init() { int i,j; fr(j,1,3) g[j][1]=1; fr(i,2,800) { // 0 a.clear(); fr(j,0,i-2) a.insert(g[0][j]^g[1][i-2-j]); for (j=0;a.count(j)>0;j++); g[0][i]=j; // 1 a.clear(); fr(j,0,i-1) a.insert(g[0][j]^(j+2<=i?g[2][i-2-j]:0)); fr(j,0,i-2) a.insert(g[0][j]^g[3][i-2-j]); fr(j,0,i-2) a.insert(g[1][j]^g[1][i-2-j]); for (j=0;a.count(j)>0;j++); g[1][i]=j; // 2 a.clear(); fr(j,0,i-1) a.insert(g[1][j]^(j+2<=i?g[2][i-2-j]:0)); fr(j,0,i-2) a.insert(g[1][j]^g[3][i-2-j]); for (j=0;a.count(j)>0;j++); g[2][i]=j; // 3 a.clear(); fr(j,0,i-1) a.insert(g[1][j]^(j+2<=i?g[2][i-2-j]:0)); fr(j,0,i-2) a.insert(g[1][j]^g[3][i-2-j]); for (j=0;a.count(j)>0;j++); g[3][i]=j; } } int main() { int n,test; init(); cin >> test; while (test--) { cin >> n; cout << (g[0][n]?'X':'Y') << endl; } return 0; }
Code mẫu của RR
{$R+,Q+} const FINP=''; FOUT=''; MAXN=801; oo=100; var f1,f2:text; test,n:longint; g:array[0..MAXN,0..1,0..1] of longint; dd:array[0..oo] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; var i:longint; procedure cal1(l:longint); begin fillchar(dd,sizeof(dd),0); for i:=0 to l-2 do dd[g[i,0,0] xor g[l-1-i,0,1]]:=1; for i:=0 to oo do if dd[i]=0 then begin g[l,0,0]:=i; exit; end; end; procedure cal2(l:longint); begin fillchar(dd,sizeof(dd),0); for i:=0 to l-2 do begin dd[g[i,0,0] xor g[l-1-i,1,1]]:=1; if i>0 then dd[g[i,0,1] xor g[l-1-i,0,1]]:=1; end; for i:=0 to oo do if dd[i]=0 then begin g[l,0,1]:=i; exit; end; end; procedure cal3(l:longint); begin fillchar(dd,sizeof(dd),0); for i:=1 to l-2 do begin dd[g[i,1,1] xor g[l-1-i,0,1]]:=1; dd[g[i,0,1] xor g[l-1-i,1,1]]:=1; end; for i:=0 to oo do if dd[i]=0 then begin g[l,1,1]:=i; exit; end; end; procedure init; var l:longint; begin g[2,0,0]:=1; g[2,0,1]:=1; for l:=3 to MAXN do begin cal1(l); cal2(l); cal3(l); end; end; begin openF; init; read(f1,test); for test:=1 to test do begin read(f1,n); if g[n,0,0]=0 then writeln(f2,'Y') else writeln(f2,'X'); end; closeF; end.
Code mẫu của hieult
#include <iostream> #include <cstdio> #include <set> //#include <conio.h> using namespace std; int dx[] = {0,0,1,1}; int dy[] = {0,1,0,1}; int triomino[1000][2][2],test,n; int main() { memset(triomino,0,sizeof(triomino)); for(int i = 1;i<=800;i++) { for(int j = 0;j<4;j++) { set <int> bo; set <int>::iterator it; if(dx[j]==0) bo.insert(triomino[i-1][1][dy[j]]); if(dy[j]==0) bo.insert(triomino[i-1][dx[j]][1]); for(int k = 0;k+2<=i;k++) { bo.insert(triomino[k][dx[j]][1]^triomino[i-k-2][0][dy[j]]); bo.insert(triomino[k][dx[j]][0]^triomino[i-k-2][1][dy[j]]); } for(int k = 0;;k++) if(bo.find(k)==bo.end()) { triomino[i][dx[j]][dy[j]]=k; break; } } } scanf("%d",&test); for(int i = 1;i<=test;i++) { scanf("%d",&n); if(triomino[n][1][1]) printf("X\n"); else printf("Y\n"); } // getch(); }
Code mẫu của ll931110
program TRIOMINO; const maxn = 800; maxv = 1000; var l: array[0..maxn,0..2,0..2] of integer; ex: array[0..maxv] of boolean; res: array[0..maxn] of boolean; procedure calc(x: integer); var i,q,t: integer; begin //Calc l[x,0,0] fillchar(ex, sizeof(ex), false); for i := 1 to x - 1 do begin q := l[i - 1,0,0] xor l[x - i,1,0]; ex[q] := true; end; t := 0; while ex[t] do inc(t); l[x,0,0] := t; //Calc l[x,0,1] fillchar(ex, sizeof(ex), false); for i := 1 to x - 1 do begin q := l[i - 1,0,0] xor l[x - i,2,1]; ex[q] := true; end; for i := 1 to x - 2 do begin q := l[i - 1,0,0] xor l[x - i,1,1]; ex[q] := true; end; for i := 2 to x - 1 do begin q := l[i - 1,0,2] xor l[x - i,0,1]; ex[q] := true; end; t := 0; while ex[t] do inc(t); l[x,0,1] := t; l[x,1,0] := t; l[x,0,2] := t; l[x,2,0] := t; //Calc l[x,1,1] fillchar(ex, sizeof(ex), false); for i := 2 to x - 2 do begin q := l[i - 1,1,0] xor l[x - i,1,1]; ex[q] := true; end; for i := 2 to x - 1 do begin q := l[i - 1,1,0] xor l[x - i,2,1]; ex[q] := true; end; t := 0; while ex[t] do inc(t); l[x,1,1] := t; l[x,2,2] := t; //Calc l[x,1,2] fillchar(ex, sizeof(ex), false); for i := 2 to x - 1 do begin q := l[i - 1,1,0] xor l[x - i,1,2]; ex[q] := true; end; for i := 2 to x - 2 do begin q := l[i - 1,1,0] xor l[x - i,2,2]; ex[q] := true; end; t := 0; while ex[t] do inc(t); l[x,1,2] := t; l[x,2,1] := t; end; procedure solve; var i,j: integer; begin fillchar(l, sizeof(l), 0); l[2,0,0] := 1; l[2,0,1] := 1; l[2,1,0] := 1; l[2,0,2] := 1; l[2,2,0] := 1; for i := 3 to maxn do calc(i); res[1] := false; res[2] := true; for i := 3 to maxn do if l[i,0,0] = 0 then res[i] := false else res[i] := true; end; procedure printresult; var i,k,n: integer; begin readln(k); for i := 1 to k do begin readln(n); if res[n] then writeln('X') else writeln('Y'); end; end; begin solve; printresult; end.
Code mẫu của skyvn97
#include<cstdio> const int res[]={1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; int n,c,t; int main(void) { scanf("%d",&t); for (c=1;c<=t;c=c+1) { scanf("%d",&n); printf("%c\n",res[n-1]+'X'); } return 0; }
Comments