Editorial for Chỉnh đồng hồ
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=''; num:array[0..8] of longint=(4,3,4,3,5,3,4,3,4); max=262144; var b:array[0..8,1..5] of longint; p,d,c,a:array[0..9] of longint; f:array[0..max,0..9] of longint; procedure rf; var i,j:longint; c:char; begin assign(input,fi); reset(input); for i:=1 to 3 do begin for j:=1 to 3 do begin read(c); a[i*3+j-3]:=ord(c)-48; end; readln; end; close(input); end; procedure init; var i:longint; begin b[0,1]:=1; b[0,2]:=2; b[0,3]:=4; b[0,4]:=5; for i:=1 to 3 do b[1,i]:=i; b[2,1]:=2; b[2,2]:=3; b[2,3]:=5; b[2,4]:=6; for i:=1 to 3 do b[3,i]:=3*i-2; b[4,1]:=2; for i:=2 to 4 do b[4,i]:=i+2; b[4,5]:=8; for i:=1 to 3 do b[5,i]:=3*i; b[6,1]:=4; b[6,2]:=5; b[6,3]:=7; b[6,4]:=8; for i:=1 to 3 do b[7,i]:=6+i; b[8,1]:=5; b[8,2]:=6; b[8,3]:=8; b[8,4]:=9; p[0]:=1; for i:=1 to 9 do p[i]:=p[i-1] shl 2; end; procedure att(i:longint); var j,s,k:longint; begin for j:=0 to 3 do begin d[i]:=j; for k:=1 to num[i] do c[b[i,k]]:=(c[b[i,k]]+j) and 3; if i=8 then begin s:=0; for k:=0 to 8 do s:=s+d[k]*p[k]; for k:=1 to 9 do f[s,k]:=c[k]; f[s,0]:=0; for k:=0 to 8 do f[s,0]:=f[s,0]+d[k]; end else att(i+1); for k:=1 to num[i] do c[b[i,k]]:=(c[b[i,k]]+4-j) and 3; end; end; procedure pr; var i,j:longint; begin init; att(0); end; procedure wf; var re,i,j:longint; kt:boolean; begin assign(output,fo); rewrite(output); re:=100; for i:=0 to max do begin kt:=true; for j:=1 to 9 do if (f[i,j]+a[j]) and 3<>0 then begin kt:=false; break; end; if kt and (f[i,0]<re) then re:=f[i,0]; end; write(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N bool vst[1<<18]; char nx[] = {0x31,0x32,0x33,0x30}; int move[9][5] = { {0,1,3,4,9}, {0,1,2,9,9}, {1,2,4,5,9}, {0,3,6,9,9}, {1,3,4,5,7}, {2,5,8,9,9}, {3,4,6,7,9}, {6,7,8,9,9}, {4,5,7,8,9}}; int hash(const char * s) { int res = 0; repd(i,9) res = res * 4 + s[i] - 0x30; return res; } int next(int s, int * a) { for(int i = 0; i < 5 && a[i] != 9; ++i) s = (s&(~(3 << (a[i]+a[i]))))|(((((s&(3<<(a[i]+a[i])))>>(a[i]+a[i]))+1)%4)<<(a[i]+a[i])); return s; } char x[10]; int main() { scanf("%s%s%s",x,x+3,x+6); queue<int> qu; qu.push(hash(x)); vst[hash(x)]=1; for(int step = 0; !qu.empty(); step++) { rep(K,qu.size()) { int s (qu.front()); qu.pop(); if(s == 0) { printf("%d\n", step); return 0; } rep(i,9) { int ns = (next(s,move[i])); if(!vst[ns]) { vst[ns] = 1; qu.push(ns); } } } } return 0; }
Code mẫu của ladpro98
program CLOCK; uses math; const move:array[1..9,0..5] of longint = ( (4,1,2,4,5,0),(3,1,2,3,0,0),(4,2,3,5,6,0),(3,1,4,7,0,0), (5,2,4,5,6,8),(3,3,6,9,0,0),(4,4,5,7,8,0),(3,7,8,9,0,0),(4,5,6,8,9,0)); fi=''; var q,d:array[0..1 shl 19] of longint; chk:array[0..1 shl 19] of boolean; c:char;st:string; l,r,u,v,i,s:longint; inp:text; function get(x,m:longint):longint; var i,b:longint; begin for i:=1 to move[m,0] do begin b:=x shr (2*move[m,i]-2) and 3; x:=x-b*(1 shl (2*move[m,i]-2)); x:=x+((b+1) mod 4)*(1 shl (2*move[m,i]-2)); end; exit(x); end; begin assign(inp,fi);reset(inp); while not eof(inp) do begin read(inp,c); if c in ['0'..'3'] then st:=c+st; end; for i:=1 to 9 do s:=s*4+ord(st[i])-48; l:=1;r:=1; q[1]:=s;d[s]:=0;chk[s]:=true; while l<=r do begin u:=q[l];inc(l); for i:=1 to 9 do begin v:=get(u,i); if not chk[v] then begin inc(r); q[r]:=v; d[v]:=d[u]+1; if v=0 then begin write(d[v]);halt; end; chk[v]:=true; end; end; end; write(d[0]); end.
Code mẫu của RR
uses math; const next:array['0'..'3',0..3] of char=( ('0','1','2','3'), ('1','2','3','0'), ('2','3','0','1'), ('3','0','1','2')); var a:array[1..3,1..3] of char; kq:array[1..9] of longint; i,j,res:longint; procedure update(i,j:longint); procedure c(u,v:longint); begin a[u,v]:=next[a[u,v],j]; end; begin case i of 1: begin c(1,1); c(1,2); c(2,1); c(2,2); end; 2: begin c(1,1); c(1,2); c(1,3); end; 3: begin c(1,2); c(1,3); c(2,2); c(2,3); end; 4: begin c(1,1); c(2,1); c(3,1); end; 5: begin c(1,2); c(2,1); c(2,2); c(2,3); c(3,2); end; 6: begin c(1,3); c(2,3); c(3,3); end; 7: begin c(2,1); c(2,2); c(3,1); c(3,2); end; 8: begin c(3,1); c(3,2); c(3,3); end; 9: begin c(2,2); c(2,3); c(3,2); c(3,3); end; end; end; function check:boolean; var i,j:longint; begin for i:=1 to 3 do for j:=1 to 3 do if a[i,j]<>'0' then exit(false); exit(true); end; procedure duyet(i,sum:longint); var j:longint; begin for j:=0 to 3 do begin kq[i]:=j; update(i,j); if i<9 then duyet(i+1,sum+j) else if check then res:=min(res,sum+j); if j<>0 then update(i,4-j); end; end; begin for i:=1 to 3 do begin for j:=1 to 3 do read(a[i,j]); readln; end; res:=1000; duyet(1,0); writeln(res); end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int d[81]={1,1,0,1,1,0,0,0,0, 1,1,1,0,0,0,0,0,0, 0,1,1,0,1,1,0,0,0, 1,0,0,1,0,0,1,0,0, 0,1,0,1,1,1,0,1,0, 0,0,1,0,0,1,0,0,1, 0,0,0,1,1,0,1,1,0, 0,0,0,0,0,0,1,1,1, 0,0,0,0,1,1,0,1,1}; long a[10],min,l,t; void doi(int x,int y) { int i; for(i=1;i<=y;i++) a[x]=(a[x]+1)%4; } void thunhan(long x) { int ok,i; if(x<min) { ok=1; for(i=1;i<=9;i++) if(a[i]!=0) { ok=0; break; } if(ok==1) min=x; } } void xuli(long i,long tong) { int j,k; for(j=0;j<=3;j++) { tong=tong+j; for(k=1;k<=9;k++) if(d[9*(i-1)+k-1]==1) doi(k,j); if(i==9) thunhan(tong); else xuli(i+1,tong); tong=tong-j; for(k=1;k<=9;k++) if(d[9*(i-1)+k-1]==1) doi(k,4-j); } } main() { min=100000; for(l=1;l<=3;l++) { scanf("%ld",&t); a[3*(l-1)+1]=t/100; a[3*(l-1)+3]=t%10; a[3*(l-1)+2]=(t/10)%10; } xuli(1,0); printf("%ld",min); //getch(); }
Code mẫu của ll931110
program clock; const input = ''; output = ''; len: array[1..9] of longint = (4,3,4,3,5,3,4,3,4); adj: array[1..9,1..5] of longint = ((1,2,4,5,0),(1,2,3,0,0),(2,3,5,6,0),(1,4,7,0,0), (2,4,5,6,8),(3,6,9,0,0),(4,5,7,8,0),(7,8,9,0,0),(5,6,8,9,0)); type arr = array[1..9] of longint; var a,b,list: arr; fi,fo: text; res: longint; procedure openfile; begin assign(fi, input); reset(fi); assign(fo, output); rewrite(fo); end; procedure closefile; begin close(fo); close(fi); end; procedure init; var i,j: longint; ch: char; begin for i := 1 to 3 do begin for j := 1 to 3 do begin read(fi, ch); a[(i - 1) * 3 + j] := ord(ch) - ord('0'); end; readln(fi); end; end; operator <(x,y: arr) c: boolean; var i: longint; begin c := false; for i := 1 to 9 do if x[i] <> y[i] then begin c := x[i] > y[i]; exit; end; end; procedure update; var i,j,ss: longint; begin b := a; for i := 1 to 9 do for j := 1 to len[i] do b[adj[i,j]] := (b[adj[i,j]] + list[i]) mod 4; for i := 1 to 9 do if b[i] <> 0 then exit; ss := 0; for i := 1 to 9 do ss := ss + list[i]; if ss < res then res := ss; end; procedure att(i: longint); var j: longint; begin for j := 0 to 3 do begin list[i] := j; if i = 9 then update else att(i + 1); end; end; procedure solve; begin res := 100; att(1); writeln(fo, res); end; begin openfile; init; solve; closefile; end.
Code mẫu của skyvn97
#include<stdio.h> #include<queue> using namespace std; queue<int> q; int mv[9][9]={{1,1,0,1,1,0,0,0,0},{1,1,1,0,0,0,0,0,0},{0,1,1,0,1,1,0,0,0},{1,0,0,1,0,0,1,0,0},{0,1,0,1,1,1,0,1,0},{0,0,1,0,0,1,0,0,1},{0,0,0,1,1,0,1,1,0},{0,0,0,0,0,0,1,1,1},{0,0,0,0,1,1,0,1,1}}; int f; int c[262144]; int l[262144]; void init(void) { int i,j; int a[3][3]; char s[3]; for (i=0;i<3;i=i+1) { scanf("%s",s); for (j=0;j<3;j=j+1) a[i][j]=s[j]-48; } int tmp=1; f=0; for (i=2;i>=0;i=i-1) for (j=2;j>=0;j=j-1) { f=f+a[i][j]*tmp; tmp=tmp*4; } } int move(int s,int p) { int i,v; for (i=0;i<9;i=i+1) if (mv[p][i]==1) { v=((s|(1<<(17-2*i)))==s)*2+((s|(1<<(16-2*i)))==s); if (v<3) s=s+(1<<(16-2*i)); else s=s-(3<<(16-2*i)); } return (s); } void BFS(void) { q.push(f); c[f]=1; l[f]=0; int x,y,i; while (!q.empty()) { x=q.front(); q.pop(); if (x==0) { printf("%d",l[x]); return; } for (i=0;i<9;i=i+1) { y=move(x,i); if (c[y]==0) { c[y]=1; l[y]=l[x]+1; q.push(y); } } } printf("-1"); } int main(void) { init(); BFS(); return 0; }
Code mẫu của khuc_tuan
#include "iostream" #include "stdio.h" #include "string" using namespace std; int a[3][3]; int ht, result; int bit[9] = { 432, 448, 216, 292, 186, 73, 54, 7, 27 }; void duyet(int vt) { if(ht>result) return; if(vt==9) { bool ok = true; for(int i=0;i<3;++i) for(int j=0;j<3;++j) if(a[i][j]!=0) { ok = false; break; } if(ok) result = ht; return; } for(int sl=0;sl<4;++sl) { for(int i=0;i<3;++i) for(int j=0;j<3;++j) if( (bit[vt] & (1<<(i*3+j))) !=0 ) { a[i][j] = (a[i][j]+sl) % 4; } ht += sl; duyet(vt+1); ht -= sl; for(int i=0;i<3;++i) for(int j=0;j<3;++j) if( (bit[vt] & (1<<(i*3+j))) !=0 ) { a[i][j] = (a[i][j]+4-sl) % 4; } } } int main() { for(int i=0;i<3;++i) { string s; getline(cin,s); for(int j=0;j<3;++j) a[i][j] = s[j] - '0'; } ht = 0; result = 100000; duyet(0); printf("%d\n",result); return 0; }
Comments