/
3053.test.cpp
48 lines (39 loc) · 880 Bytes
/
3053.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3053
#include <bits/stdc++.h>
using namespace std;
#define call_from_test
#include "../../tools/all_permutations.cpp"
#undef call_from_test
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n;
string s;
cin>>n>>s;
int c[10][10]={};
for(int i=0;i+1<n;i++){
int a=s[i]-'0',b=s[i+1]-'0';
c[a][b]++;
}
int ans=n*100;
vector<int> us;
auto f=
[&](auto vs){
int x[10],y[10];
for(int i=0;i<9;i++){
x[vs[i]+1]=i%3;
y[vs[i]+1]=i/3;
}
int res=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
res+=c[i][j]*(abs(x[i]-x[j])+abs(y[i]-y[j]));
if(res<ans) ans=res,us=vs;
};
all_permutations(9,f);
for(int i=0;i<9;i++){
cout<<us[i]+1;
if(i%3==2) cout<<endl;
}
return 0;
}