Editorial for Trò chơi vòng số
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
const fi=''; fo=''; var n,re:byte; a,b:array[1..100] of shortint; f:array[1..100,1..100] of shortint; procedure rf; var i:byte; j:integer; begin assign(input,fi); reset(input); readln(n); for i:=1 to n do begin read(j); if odd(j) then b[i]:=1 else b[i]:=0; end; close(input); end; function max(a,b:shortint):shortint; begin if a>b then max:=a else max:=b; end; function calc(l,r:byte):shortint; begin if l=r then calc:=a[l] else begin if f[l+1,r]=127 then f[l+1,r]:=calc(l+1,r); if f[l,r-1]=127 then f[l,r-1]:=calc(l,r-1); calc:=max(a[l]-f[l+1,r],a[r]-f[l,r-1]); end; end; procedure pr; var i,j,k,t:shortint; begin re:=0; for i:=1 to n do begin for j:=0 to n-1 do begin if i+j=n then t:=n else t:=(i+j) mod n; a[t]:=b[j+1]; end; for j:=1 to n do for k:=j to n do f[j,k]:=127; f[1,1]:=a[1]; f[2,n]:=calc(2,n); if a[1]>f[2,n] then inc(re); end; end; procedure wf; begin assign(output,fo); rewrite(output); write(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=100; var d:array[1..MAXN,1..MAXN] of longint; a,b:array[1..MAXN] of longint; n,kq:longint; procedure inp; var f:text; i:longint; begin assign(f,FINP); reset(f); read(f,n); for i:=1 to n do begin read(f,b[i]); b[i]:=b[i] mod 2; end; close(f); end; procedure ans; var f:text; begin assign(f,FOUT); rewrite(f); writeln(f,kq); close(f); end; function check(u:longint):boolean; var i,j,k:longint; begin for i:=1 to n-1 do if a[i]=1 then d[i,i]:=1 else d[i,i]:=0; for k:=1 to n-2 do for i:=1 to n-1-k do begin j:=i+k; d[i,j]:=max(a[i]-d[i+1,j],a[j]-d[i,j-1]); end; check:=b[u]-d[i,j]>0; end; procedure solve; var i,j,k:longint; begin kq:=0; for i:=1 to n do begin k:=0; for j:=i+1 to n do begin inc(k); a[k]:=b[j]; end; for j:=1 to i-1 do begin inc(k); a[k]:=b[j]; end; if check(i) then inc(kq); end; end; begin inp; solve; ans; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int max(int x,int y) { if(x>y) return x; return y; } main() { int n,a[206],le[206],f[106][206],KQ=0; scanf("%d",&n); le[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; if(a[i]%2==0) { le[i]=le[i-1]; f[i][i]=0; } else { le[i]=le[i-1]+1; f[i][i]=1; } } for(int i=n+1;i<=2*n;i++) le[i]=le[i-n]+le[n]; for(int i=1;i<=n-2;i++) { for(int j=1;j<=n-1;j++) f[j][i+j]=max(-f[j+1][i+j],-f[j][i+j-1])+le[i+j]-le[j-1]; f[n][n+i]=max(-f[1][i],-f[n][n+i-1])+le[n+i]-le[n-1]; } for(int i=1;i<=n;i++) { if(le[n]-f[i][i+n-2]>le[n]/2) KQ++; } printf("%d",KQ); //getch(); }
Code mẫu của ll931110
Program IVANA; Uses math; Const input = ''; output = ''; maxn = 100; Var n: integer; a: array[1..maxn] of integer; F: array[1..maxn,1..maxn,1..2] of integer; Procedure init; Var fi: text; i: integer; Begin Assign(fi, input); Reset(fi); Readln(fi, n); For i:= 1 to n do Begin Read(fi, a[i]); If odd(a[i]) then a[i]:= 1 else a[i]:= 0; End; Close(fi); End; Function incc(x: integer): integer; Begin inc(x); If x = n + 1 then exit(1) else exit(x); End; Function decc(x: integer): integer; Begin dec(x); If x = 0 then exit(n) else exit(x); End; Procedure solve; Var i,j,len: integer; Begin If odd(n) then For i:= 1 to n do Begin F[i,i,1]:= a[i]; F[i,i,2]:= a[i]; End else For i:= 1 to n do Begin F[i,i,1]:= -a[i]; F[i,i,2]:= -a[i]; End; For len:= 1 to n - 1 do For i:= 1 to n do Begin j:= i + len; If j > n then j:= j - n; If odd(len) <> odd(n) then Begin F[i,j,1]:= max(F[incc(i),j,1] + a[i],F[i,decc(j),2] + a[j]); F[i,j,2]:= max(F[incc(i),j,2] + a[i],F[i,decc(j),1] + a[j]); End else Begin F[i,j,1]:= min(F[incc(i),j,1] - a[i],F[i,decc(j),2] - a[j]); F[i,j,2]:= min(F[incc(i),j,2] - a[i],F[i,decc(j),1] - a[j]); End; End; End; Procedure printresult; Var fo: text; i,j,count: integer; Begin count:= 0; For i:= 1 to n do If min(F[incc(i),decc(i),1],F[incc(i),decc(i),2]) + a[i] > 0 then inc(count); Assign(fo, output); Rewrite(fo); Writeln(fo, count); Close(fo); End; Begin init; solve; printresult; End.
Comments