VMKEY - Thế giới năm 1000003

Tác giả: RR

Ngôn ngữ: C++

// 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;
}

Download