Editorial for Kruska


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

#include<iostream>
#include<algorithm>
#define maxm 10010
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;
struct rec
{
      int x,y,z,d,k;
};
int n,k,m,nq,a[222][222],b[maxm][7],dx[4],dy[4],d[222][222][4][7];
rec q[1200000];
long long re;

void push(int i,int x,int y,int z,int day,int turn)
{
     q[i].x=x; q[i].y=y; q[i].z=z; q[i].d=day; q[i].k=turn;
}

int main()
{
    dx[0]=-1; dx[1]=0; dx[2]=1; dx[3]=0;
    dy[0]=0; dy[1]=1; dy[2]=0; dy[3]=-1;
    int i,x,j,y,day=0,z=1,turn=0;
    char ch;
    cin >> n >> k >> m;
    fr(j,1,m)
    {
          scanf("%d%d%c",&x,&y,&ch);
          a[x][y]=j;
          fr(i,0,6) 
          {
             scanf("%c",&ch);
             if (ch=='R') b[j][i]=1;
             if (ch=='L') b[j][i]=3;
          }
          scanf("\n");
    }
    d[1][1][1][0]=1; i=1; x=1; y=1; 
    push(1,1,1,1,0,0); 
    while (1)
    {
        if (a[x][y])
        {
            int w=a[x][y];
            if (b[w][day%7])
            {
               turn++; z=(z+b[w][day%7])%4;
            }
        }
        if (!(x+dx[z] && y+dy[z] && x+dx[z]<=n && y+dy[z]<=n)) 
        {
           z=(z+2)%4; turn++;
        }
        if (turn>=k) 
        {
            re=day; break;
        }
        x+=dx[z]; y+=dy[z]; day++; i++;   
        if (d[x][y][z][day%7])
        {
            int t=d[x][y][z][day%7],u=i-t,v=turn-q[t].k;
            long long vv;
            re=q[t].d; k-=q[t].k;
            vv=k/v; k%=v;
            re+=vv*u;
            k+=q[t].k;
            if (k>q[t].k)
            {
               fr(j,t+1,i)
                  if (q[j].k>=k) break;
               re+=j-t-1;
            }
            break;
        }
        d[x][y][z][day%7]=i;
        push(i,x,y,z,day,turn);  
    }
    cout << re << endl;
    return 0;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       222;
  MAXM          =       10111;
  di            :       array[1..4] of longint=(0,0,-1,1);
  dj            :       array[1..4] of longint=(1,-1,0,0);
  turnl         :       array[1..4] of longint=(3,4,2,1);
  turnr         :       array[1..4] of longint=(4,3,1,2);
  turnb         :       array[1..4] of longint=(2,1,4,3);
var
  f1,f2         :       text;
  n,m,k         :       longint;
  kq            :       int64;
  wizard        :       array[1..MAXM] of string[7];
  desert        :       array[1..MAXN,1..MAXN] of longint;
  day,turned    :       array[1..MAXN,1..MAXN,1..7,1..4] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    var
      i,u,v:longint;
      ch:char;
    begin
      readln(f1,n,k);
      readln(f1,m);
      for i:=1 to m do
        begin
          read(f1,u,v); desert[u,v]:=i;
          read(f1,ch);
          readln(f1,wizard[i]);
        end;
    end;
function outside(u,v:longint):boolean; inline;
    begin
      exit( (u<1) or (v<1) or (u>n) or (v>n) );
    end;
procedure solve;
    var
      count,turn,u,v,d,h,uu,vv,dd,hh,dir:longint;
      chuky:int64;
    begin
      fillchar(day,sizeof(day),0);
      u:=1; v:=1; d:=1; h:=1; count:=0; turn:=0;
      while day[u,v,d,h]=0 do
        begin
          count+=1;
          day[u,v,d,h]:=count; turned[u,v,d,h]:=turn;
          uu:=u+di[h]; vv:=v+dj[h];
          dd:=d+1; if dd=8 then dd:=1;
          hh:=h;
          if desert[uu,vv]<>0 then
            case wizard[desert[uu,vv]][dd] of
              'L': begin hh:=turnl[h]; inc(turn); end;
              'R': begin hh:=turnr[h]; inc(turn); end;
            end;
          if outside(uu+di[hh],vv+dj[hh]) then begin hh:=turnb[hh]; inc(turn); end;
          u:=uu; v:=vv; d:=dd; h:=hh;
          if turn>=k then
            begin
              writeln(f2,kq+count);
              closeF; halt;
            end;
        end;
      chuky:=(k-turned[u,v,d,h]) div (turn-turned[u,v,d,h]);
      kq:=chuky*(count-day[u,v,d,h]+1);
      k-=chuky*(turn-turned[u,v,d,h]);
    end;

begin
  openF;
  inp;
  solve;
  solve;
end.

Code mẫu của hieult

#include <cstdio>
#include <cstring>
//#include <conio.h>

const int hr[4] = {0, 1, 0, -1};
const int hc[4] = {1, 0, -1, 0};

int N,K,M;
char a[220][220][8];
long long tg[220][220][4][8];
int lan[220][220][4][8];

int main()
{
   // freopen("kruska.in.1","r",stdin);
    scanf("%d %d %d",&N,&K,&M);
    memset(a,'S',sizeof(a));

    for(int i = 0;i<M;i++)
    {
        int r,c;
        scanf("%d %d",&r,&c);
        r--; c--;
        scanf("%s",a[r][c]);
    }

    long long kq = 0;
    int r = 0, c = 0, h = 0, t = 0, k = 0;
    while(true)
    {
        if(a[r][c][t] == 'R') {   h = (h+1)%4; k++;}
        if(a[r][c][t] == 'L') {   h = (h+3)%4; k++;}
        if( r+hr[h] < 0 || r+hr[h] >= N || c+hc[h] < 0 || c+hc[h] >= N)
        {  h = (h+2)%4; k++;}

        if(tg[r][c][h][t]>0)
        {

             int qua = k - lan[r][c][h][t];
             int con = K-k;
             kq += (con/qua)*(kq - tg[r][c][h][t]);
             k += (con/qua) * qua; 
        }

        tg[r][c][h][t] = kq;
        lan[r][c][h][t] = k;

        if(k>=K) break;

        r += hr[h];
        c += hc[h];
        kq++;
        t = (t+1)%7; 

    }

    printf("%lld",kq);
   //getch();

}

Code mẫu của ll931110

program KRUS;
const
  input  = '';
  output = '';
  maxn = 200;
  maxm = 10000;
  dx: array[1..4] of integer = (-1,0,1,0);
  dy: array[1..4] of integer = (0,1,0,-1);
  l: array[1..4] of integer = (4,1,2,3);
  r: array[1..4] of integer = (2,3,4,1);
  o: array[1..4] of integer = (3,4,1,2);
var
  pos: array[1..maxn,1..maxn] of integer;
  ac: array[1..maxm] of string[8];
  Fd,Fk: array[1..maxn,1..maxn,1..7,1..4] of longint;
  n,m: integer;
  k,nd: longint;
  res: int64;
  u,v,md,way,nturn: longint;

procedure init;
var
  fi: text;
  i,x,y: integer;
begin
  assign(fi, input);
    reset(fi);

  readln(fi, n, k);
  readln(fi, m);
  for i := 1 to m do
    begin
      read(fi, x, y);
      readln(fi, ac[i]);
      delete(ac[i],1,1);
      pos[x,y] := i;
    end;

  close(fi);
end;

function outside(way: integer): boolean;
begin
  if (way = 1) and (u = 1) then exit(true);
  if (way = 2) and (v = n) then exit(true);
  if (way = 3) and (u = n) then exit(true);
  if (way = 4) and (v = 1) then exit(true);
  outside := false;
end;

procedure update;
begin
  if Fd[u,v,md,way] = 0 then
    begin
      Fd[u,v,md,way] := nd;
      Fk[u,v,md,way] := nturn;
    end;
end;

procedure cycle;
var
  cday,td: int64;
  tt,cturn: longint;
begin
  td := Fd[u,v,md,way];
  tt := Fk[u,v,md,way];

  cday := nd - td;
  cturn := nturn - tt;
  k := k - tt;

  cday := int64(cday * (k div cturn));
  k := k mod cturn;
  res := td + cday;
  md := (res mod 7) + 1;
  nturn := 0;
end;

procedure solve;
var
  tmp: integer;
begin
  u := 1;
  v := 1;
  way := 2;
  nturn := 0;
  nd := 0;
  md := 1;

  while nturn < k do
    begin
      if pos[u,v] <> 0 then
        begin
          tmp := pos[u,v];
          if ac[tmp][md] = 'L' then
            begin
              inc(nturn);
              way := l[way];
              update;
            end
          else if ac[tmp][md] = 'R' then
            begin
              inc(nturn);
              way := r[way];
              update;
            end;
        end;

      if outside(way) then
        begin
          way := o[way];
          inc(nturn);
          update;
        end;

      if nturn >= k then
        begin
          res := nd;
          exit;
        end;

      if (Fd[u,v,md,way] <> 0) and (Fd[u,v,md,way] <> nd) then
        begin
          cycle;
          u := u + dx[way];
          v := v + dy[way];
          inc(res);
          inc(md);
          if md = 8 then md := 1;
          break;
        end;

      u := u + dx[way];
      v := v + dy[way];
      inc(nd);
      inc(md);
      if md = 8 then md := 1;
    end;

  nturn := 0;
  while nturn < k do
    begin
      if pos[u,v] <> 0 then
        begin
          tmp := pos[u,v];
          if ac[tmp][md] = 'L' then
            begin
              inc(nturn);
              way := l[way];
            end
          else if ac[tmp][md] = 'R' then
            begin
              inc(nturn);
              way := r[way];
            end;
        end;

      if outside(way) then
        begin
          way := o[way];
          inc(nturn);
        end;

      if nturn >= k then exit;
      u := u + dx[way];
      v := v + dy[way];
      inc(res);
      inc(md);
      if md = 8 then md := 1;
    end;
end;

procedure printresult;
var
  fo: text;
begin
  assign(fo, output);
    rewrite(fo);

  writeln(fo, res);
  close(fo);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

const int MAX = 1120000 * 2;

int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

int n, K;
int w;
char a[10010][10];
int pt[202][202];

int st[MAX];
int F[202][202][4][7];

bool inside(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < n;
}

int main() {
    scanf("%d%d%d", &n, &K, &w);
    memset( pt, -1, sizeof(pt));
    for(int i=0;i<w;++i) {
        int u, v;
        scanf("%d%d%s", &u, &v, a[i]);
        pt[u-1][v-1] = i;
    }
    int x, y, h;
    int turn = 0;
    x = y = 0;
    h = 1;
    memset( F, -1, sizeof(F));
    F[x][y][h][0] = 0;
    for(int z=0;;++z) {
        int quanh = 0;
        if(pt[x][y]!=-1) {
            char c = a[pt[x][y]][z%7];
            if(c=='L') { h = (h+3) % 4; ++ quanh; ++ turn; }
            else if(c=='R') { h = (h+1) % 4; ++ quanh; ++ turn; }
        }
        if(turn>=K) {
            cout << z << endl;
            return 0;
        }
        int nx = x + dx[h];
        int ny = y + dy[h];
        if(!inside(nx,ny)) {
            h = (h+2)%4;
            ++turn;
            ++quanh;
            if(turn>=K) {
                cout << z << endl;
                return 0;
            }
            nx = x + dx[h];
            ny = y + dy[h];
        }
        x = nx;
        y = ny;
        st[z] = quanh;
        int & ff = F[x][y][h][(z+1) % 7];

        if( ff != -1 ) {
            int ct = z - ff + 1;
            int need = K - turn;
            int total = 0;
            for(int i=ff;i<=z;++i) total += st[i];
            long long kq = z + need / total * 1LL * ct;
            need %= total;
            if(need == 0) {
                kq -= ct;
                need = total;
            }
            for(int i=ff;i<=z;++i) {
                ++ kq;
                need -= st[i];
                if(need <= 0) {
                    cout << kq << endl;
                    return 0;
                }
            }
        }
        else
            ff = z + 1;
    }
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.