Editorial for Cô gái chăn bò


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='';
      r:array[1..13] of longint=(0,1,2,4,5,8,9,10,16,17,18,20,21);
var num,i,m,n,re:longint;
    a:array[0..1,0..31] of longint;
    p:array[0..5] of longint;
    d:array[0..31,0..31] of byte;

procedure init;
var i,j,k,max:longint; k1,k2:boolean;
begin
     p[0]:=1;
     for i:=1 to m do p[i]:=p[i-1]*2;
     max:=p[m]-1;
     fillchar(d,sizeof(d),0);
     for i:=0 to max do
         for j:=0 to max do
         begin
              k1:=false; k2:=false;
              for k:=1 to 13 do
              begin
                   if i and j=r[k] then k1:=true;
                   if i or j=max-r[k] then k2:=true;
              end;
              if k1 and k2 then
              begin
                   d[i,j]:=1;
                   d[j,i]:=1;
              end;
         end;
end;

procedure pr;
var i,j,max,k,t:longint;
begin
     if m>n then
     begin
          i:=m; m:=n; n:=i;
     end;
     init;
     max:=p[m]-1;
     dec(m);
     t:=1;
     fillchar(a,sizeof(a),0);
     for i:=0 to max do a[1,i]:=1;
     for i:=2 to n do
     begin
          t:=i mod 2;
          for j:=0 to max do a[t,j]:=0;
          for j:=0 to max do
              for k:=0 to max do
                  if d[j,k]=1 then
                     a[t,j]:=a[t,j]+a[1-t,k];
     end;
     re:=0;
     for i:=0 to max do
         re:=re+a[t,i];
end;

begin
     assign(input,fi);
     reset(input);
     assign(output,fo);
     rewrite(output);
     readln(num);
     for i:=1 to num do
     begin
          readln(m,n);
          pr;
          writeln(re);
     end;
     close(input);
     close(Output);
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

int f[40][160], m, n;

bool ok( int mask, int mask2 ) {
    for(int i=1; i<n; ++i) {
        int a = (mask & (1<<i))!=0, b = (mask & (1<<(i-1)))!=0;
        int c = (mask2 & (1<<i))!=0, d = (mask2 & (1<<(i-1)))!=0;
        if(a==b&&b==c&&c==d) return 0;
    }
    return 1;
}

int main() {
    int tc; scanf("%d",&tc);
    while(tc--) {
        scanf("%d%d",&m,&n); if(m<n) swap(m,n);
        for(int mask = (1<<n)-1; mask >= 0; --mask) f[1][mask] = 1;
        for(int i = 2; i <= m; ++i) 
            for(int mask = (1<<n)-1; mask >= 0; --mask) {
                f[i][mask] = 0;
                for(int mask2 = (1<<n)-1; mask2 >= 0; --mask2) {
                    if(ok(mask,mask2)) f[i][mask] += f[i-1][mask2];
                    //printf("%d %d %d\n", mask, mask2, ok(mask,mask2));
                }
            }
        unsigned long long res = 0;
        for(int state = (1<<n)-1; state >= 0; --state) res += f[m][state];
        printf("%llu\n", res);
    }
    return 0;
}

Code mẫu của ladpro98

program cowgirl;
uses    math;

var     m,n,x:longint;
        f:array[0..30,0..32] of longint;
        check:array[0..32,0..32] of boolean;
        inp:text;
Function GetBit(a,k:longint):longint;
begin
        exit((a shr (k)) and 1);
end;


procedure init;
var     i,j,k:longint;
begin
        x:=1;
        for i:=1 to n do x:=x*2;
        for i:=0 to 32 do
        for j:=0 to 32 do  check[i,j]:=true;
        for i:=0 to x-1 do
        for j:=0 to x-1 do
        for k:=0 to n-2 do
        begin
                if (getbit(i,k) = getbit(j,k)) and (getbit(i,k+1) = getbit(j,k+1)) and (getbit(i,k)=getbit(i,k+1))
                then
                begin
                        check[i,j]:=false;
                end;

        end;
end;

function process:longint;
var     row,i,j,k,x2:longint;
        sum:int64;
begin
        sum:=0;
        x2:=1;
        for i:=1 to m do x2:=x2*2;

        if n=1 then exit(x2);
        fillchar(f,sizeof(f),0);
        for i:=0 to x do f[1,i]:=1;
        for row:=2 to m do
        for i:=0 to x-1 do
        for j:=0 to x-1 do
        begin
                if check[i,j] then inc(f[row,j],f[row-1,i]);
        end;
        for i:=0 to x do inc(sum,f[m,i]);
        exit(sum);
end;

procedure input;
var     t,sotest,i:longint;
begin
        readln(sotest);
        for i:=1 to sotest do
        begin
                read(m,n);
                if m<n then
                begin
                        t:=m;
                        m:=n;
                        n:=t;
                end;
                init;
                writeln(process);
        end;
end;

begin
        input;
end.

Code mẫu của RR

{$R+,Q+}
PROGRAM COWGIRL;
CONST
  maxn=30;
  fi='';
  fo='';
  lt2:array[0..5] of integer=(1,2,4,8,16,32);
VAR
  d:array[1..maxn,0..31] of longint;
  ok:array[0..31,0..31] of integer;
  m,n:integer;
  f1,f2:text;
Procedure OpenFiles;
Begin
  Assign(f1,fi); Reset(f1);
  Assign(f2,fo); Rewrite(f2);
End;
Procedure CloseFiles;
Begin
  Close(f1); Close(f2);
End;
Procedure WriteOutput;
Var
  i:integer;
  sl:longint;
Begin
  sl:=0;
  For i:=0 to lt2[m]-1 do
    sl:=sl+d[n,i];
  Writeln(f2,sl);
End;
Procedure Swap(var a,b:integer);
Var
  temp:integer;
Begin
  temp:=a; a:=b; b:=temp;
End;
Procedure Prepare;
Var
  i,j,k,u,v:integer;
  b:boolean;
Begin
  For i:=0 to lt2[m]-1 do
  For j:=0 to lt2[m]-1 do
    begin
      b:=true;
      For k:=0 to m-2 do
        begin
          u:=(i shr k) and 3;
          v:=(j shr k) and 3;
          If (u or v=0) or (u and v=3) then
            begin
              b:=false;
              break;
            end;
        end;
      If b then ok[i,j]:=1 else ok[i,j]:=0;
    end;
End;
Procedure Calculate;
Var
  i,j,k:integer;
Begin
  For j:=0 to lt2[m]-1 do
    d[1,j]:=1;
  For i:=2 to n do
    For j:=0 to lt2[m]-1 do
      begin
        d[i,j]:=0;
        For k:=0 to lt2[m]-1 do
          If ok[j,k]=1 then d[i,j]:=d[i,j]+d[i-1,k];
      end;
End;
Procedure Solve;
Var
  t,i:integer;
Begin
  Readln(f1,t);
  For i:=1 to t do
    begin
      Readln(f1,m,n);
      If m>n then Swap(m,n);
      Prepare;
      Calculate;
      WriteOutput;
    end;
End;
BEGIN
  OpenFiles;
  Solve;
  CloseFiles;
END.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <math.h>
int F(int m,int a,int b)
   {
   int A[6],B[6],i,t=1;
   for(int i=1;i<=m;i++)
     {
     A[i]=a%2;
     a=a/2;
     B[i]=b%2;
     b=b/2;
     }
   for(int i=1;i<m;i++)
     {
     if((A[i]==0&&B[i]==0&&A[i+1]==0&&B[i+1]==0)||(A[i]==1&&B[i]==1&&A[i+1]==1&&B[i+1]==1))        
     t=0;
     }
   return t;    
   }
main()
 {
 long T,n,m,KQ;
 scanf("%ld",&T);
 for(long i=0;i<T;i++)
   {
   KQ=0;       
   long f[33][33],thay,t;
   scanf("%ld %ld",&n,&m);
   if(n<m)
     {
     thay=n;
     n=m;
     m=thay;
     }  
   t=pow(2,m);   
   for(long i=0;i<t;i++)
     f[1][i]=1;
   for(long i=2;i<=n;i++)
     for(long j=0;j<t;j++)
       {
       f[i][j]=0;       
       for(long k=0;k<t;k++)
         if(F(m,j,k)==1)        
         f[i][j]+=f[i-1][k];
       }
   for(long i=0;i<t;i++)
     KQ+=f[n][i];
   printf("%ld\n",KQ);      
   }
 //getch();
 }

Code mẫu của ll931110

Program COWGIRL;
        Const
                input  = '';
                output = '';
                  maxn = 30;
                  maxd = 40;
        Var
                F: array[0..maxd,1..maxn] of longint;
              m,n: longint;
              t,i: longint;
            fi,fo: text;

Procedure openfile;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Assign(fo, output);
                        Rewrite(fo);
          End;

Procedure optimize;
          Var
                     i,j,k,res: longint;
                       a,b,c,d: longint;
                       x,y,tmp: longint;
                            ok: boolean;
          Begin
                Fillchar(F, sizeof(F), 0);

                Readln(fi, m, n);
                If m > n then
                   Begin
                      tmp:= m;
                      m:= n;
                      n:= tmp;
                   End;

                For i:= 0 to 1 shl m - 1 do F[i,1]:= 1;

                For i:= 2 to n do
                  For x:= 0 to 1 shl m - 1 do
                    For y:= 0 to 1 shl m - 1 do
                      Begin
                        ok:= true;
                        For k:= 0 to m - 2 do
                          Begin
                                If (x and (1 shl k)) = (1 shl k) then a:= 1 else a:= 0;
                                If (x and (1 shl (k + 1))) = (1 shl (k + 1)) then b:= 1 else b:= 0;

                                If (y and (1 shl k)) = (1 shl k) then c:= 1 else c:= 0;
                                If (y and (1 shl (k + 1))) = (1 shl (k + 1)) then d:= 1 else d:= 0;

                                tmp:= a + b + c + d;
                                If (tmp = 0) or (tmp = 4) then
                                  Begin
                                        ok:= false;
                                        break;
                                  End;
                          End;

                        If ok then F[x,i]:= F[x,i] + F[y,i - 1];
                      End;

                res:= 0;
                For i:= 0 to 1 shl m - 1 do res:= res + F[i,n];
                Writeln(fo, res);
          End;

Procedure closefile;
          Begin
                Close(fo);
                Close(fi);
          End;

Begin
        openfile;

        Readln(fi, t);
        For i:= 1 to t do optimize;

        closefile;
End.

Code mẫu của skyvn97

#include<stdio.h>
typedef unsigned long long ull;
ull res1[]={ 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, };
ull res2[]={ 14, 50, 178, 634, 2258, 8042, 28642, 102010, 363314, 1293962, 4608514, 16413466, 58457426, 208199210, };
ull res3[]={ 322, 2066, 13262, 85126, 546410, 3507314, 22512862, 144506294, };
ull res4[]={ 23858, 275690, 3185462, 36806846, };
ull res5[]={ 5735478, 119310334, };
int t,ct;
ull m,n,s;
int main(void)
{
    scanf("%d",&t);
    for (ct=1;ct<=t;ct=ct+1)
        {
            scanf("%llu",&m);
            scanf("%llu",&n);
            if (m>n)
                {
                    s=m;m=n;n=s;
                }
            if (m==1) printf("%llu\n",res1[n-1]);
            if (m==2) printf("%llu\n",res2[n-2]);
            if (m==3) printf("%llu\n",res3[n-3]);
            if (m==4) printf("%llu\n",res4[n-4]);
            if (m==5) printf("%llu\n",res5[n-5]);
        }
}

Code mẫu của khuc_tuan

def ok(a,b,c):
    for i in range(c-1):
        if (a&(1<<i))!=0 and (a&(1<<(i+1)))!=0 and (b&(1<<i))!=0 and (b&(1<<(i+1)))!=0:return False
        if (a&(1<<i))==0 and (a&(1<<(i+1)))==0 and (b&(1<<i))==0 and (b&(1<<(i+1)))==0:return False
    return True

f = [[[0 for xx in range(100)] for yy in range(10)] for zz in range(40)]
sum = [[0 for yy in range(10)] for zz in range(40)]
for i in range(1,31):
    for j in range(1,6):
         for bit in range(1<<j):
             if i==1:f[i][j][bit]=1
             else:
                 for b2 in range(1<<j):
                     if ok(bit,b2,j): f[i][j][bit] += f[i-1][j][b2]

for i in range(1,31):
    for j in range(1,6):
        for bit in range(1<<j):
            sum[i][j] += f[i][j][bit]
st=input()
for i in range(st):
    m,n=[int(xx) for xx in raw_input().split()]
    if m>n:
        t=m
        m=n
        n=t
    print sum[n][m]

Comments

Please read the guidelines before commenting.


There are no comments at the moment.