Editorial for VM 13 Bài 11 - Thế giới năm 1000003
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 happyboy99x
#include<cstdio> #include<climits> #include<cstring> #include<algorithm> using namespace std; const int N = 4e5; char s[N+1]; int n, f[10][10], pos[10][2], rpos[10][2]; void enter() { scanf("%s", s); n = strlen(s); for(int i = 1; i < n; ++i) { ++f[s[i-1]-0x30][s[i]-0x30]; ++f[s[i]-0x30][s[i-1]-0x30]; } } void backtrack(const int &p, const int &mask, const int &now, int &res) { if(now >= res) return; if(p == 10) { res = now; memcpy(rpos, pos, sizeof pos); } else for(int v = 0; v < 10; ++v) if(~mask & 1 << v) { pos[v][0] = p / 3; pos[v][1] = p % 3; int add = 0; for(int u = 0; u < 10; ++u) if(mask & 1 << u) add += f[u][v] * (abs(pos[u][0] - pos[v][0]) + abs(pos[u][1] - pos[v][1])); backtrack(p+1, mask | 1 << v, now + add, res); } } int main() { enter(); int res = INT_MAX; backtrack(0, 0, 0, res); printf("%d\n", res); for(int i = 0; i < 10; ++i) fprintf(stderr, "%d %d\n", rpos[i][0] + 1, rpos[i][1] + 1); return 0; }
Code mẫu của ladpro98
program vmkey; uses math; const fi=''; lim=10; var s:ansistring; a,px,py:array[0..10] of longint; check:array[0..10] of boolean; //row[0..9,0..9,0..9] of boolean; f:array[0..10,0..10] of longint; res:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,s); close(inp); res:=high(longint); for i:=2 to length(s) do inc(f[min(ord(s[i]),ord(s[i-1]))-48,max(ord(s[i]),ord(s[i-1]))-48]); end; procedure update; var i,j,m,t:longint; begin m:=1; //row[a[1],a[2],a[3]]:=true; for i:=1 to 3 do for j:=1 to 3 do begin px[a[m]]:=i; py[a[m]]:=j; inc(m); end; px[a[m]]:=4;py[a[m]]:=1; t:=0; for i:=0 to 8 do for j:=i+1 to 9 do begin inc(t,f[i,j]*(abs(px[i]-px[j])+abs(py[i]-py[j]))); if t>=res then exit; end; res:=min(res,t); end; procedure back(i:longint); var j:longint; begin if i>lim then begin update; exit; end; for j:=0 to 9 do if not check[j] then begin check[j]:=true; a[i]:=j; back(i+1); check[j]:=false; end; end; begin input; back(1); write(res); end.
Code mẫu của RR
// Author: RR. Expected score: 100 #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <sstream> #include <fstream> #define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i) #define REP(i,a) for(int i=0,_a=(a); i < _a; ++i) using namespace std; char s[500111]; int cnt[11][11]; int a[11], dist[11][11]; int main() { gets(s); REP(i,strlen(s)-1) { cnt[s[i]-'0'][s[i+1]-'0']++; } REP(i,10) REP(j,10) { int u = i / 3, v = i % 3; int x = j / 3, y = j % 3; dist[i][j] = abs(u - x) + abs(v - y); } REP(i,10) a[i] = i; int res = 1000111000; do { int now = 0; REP(i,10) REP(j,10) now += dist[i][j] * cnt[a[i]][a[j]]; res = min(res, now); } while (next_permutation(a, a+10)); cout << res << endl; return 0; }
Code mẫu của skyvn97
#include<cstring> #include<cstdio> #include<queue> using namespace std; typedef pair<int,int> ii; const ii loc[]={ii(0,0),ii(0,1),ii(0,2),ii(1,0),ii(1,1),ii(1,2),ii(2,0),ii(2,1),ii(2,2),ii(3,0)}; const ii inf[]={ii(0,1),ii(0,2),ii(0,3),ii(0,4),ii(0,5),ii(0,6),ii(0,7),ii(0,8),ii(0,9), ii(1,2),ii(1,3),ii(1,4),ii(1,5),ii(1,6),ii(1,7),ii(1,8),ii(1,9), ii(2,3),ii(2,4),ii(2,5),ii(2,6),ii(2,7),ii(2,8),ii(2,9), ii(3,4),ii(3,5),ii(3,6),ii(3,7),ii(3,8),ii(3,9), ii(4,5),ii(4,6),ii(4,7),ii(4,8),ii(4,9), ii(5,6),ii(5,7),ii(5,8),ii(5,9), ii(6,7),ii(6,8),ii(6,9), ii(7,8),ii(7,9), ii(8,9)}; int x[11]; int f[55]; int log2[2222]; char s[400400]; int best,n; int abs(const int &x) { if (x<0) return (-x); else return (x); } int min(const int &x,const int &y) { if (x<y) return (x); else return (y); } int max(const int &x,const int &y) { if (x>y) return (x); else return (y); } int dis(const int &a,const int &b) { return (abs(loc[x[a]].first-loc[x[b]].first)+abs(loc[x[a]].second-loc[x[b]].second)); } int add(const ii &a) { if (a.first==0) return (a.second-1); if (a.first==1) return (a.second+7); if (a.first==2) return (a.second+14); if (a.first==3) return (a.second+20); if (a.first==4) return (a.second+25); if (a.first==5) return (a.second+29); if (a.first==6) return (a.second+32); if (a.first==7) return (a.second+34); if (a.first==8) return (a.second+35); } void init(void) { int i; scanf("%s",s); n=strlen(s); for (i=0;i<45;i=i+1) f[i]=0; for (i=0;i<n-1;i=i+1) if (s[i]!=s[i+1]) f[add(ii(min(s[i],s[i+1])-48,max(s[i],s[i+1])-48))]++; for (i=0;i<11;i=i+1) log2[1<<i]=i; best=(int)1e9; } void update(void) { int i; int sum=0; for (i=0;i<45;i=i+1) { sum=sum+dis(inf[i].first,inf[i].second)*f[i]; if (sum>=best) return; } if (sum<best) best=sum; } void backtrack(const int &i,const int &s) { int ts=(1<<10)-1-s; while (ts>0) { x[log2[ts&(-ts)]]=i; if (i==9) update(); else backtrack(i+1,s|(ts&(-ts))); ts=ts-(ts&(-ts)); } } void process(void) { backtrack(0,0); printf("%d",best); } int main(void) { init(); process(); return 0; }
Comments