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.

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

Please read the guidelines before commenting.


There are no comments at the moment.