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.

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

Please read the guidelines before commenting.


There are no comments at the moment.