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.

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

Please read the guidelines before commenting.


There are no comments at the moment.