Hướng dẫn giải của Kruska
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận