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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <ranges>
#include <set>
#include <sstream>
#include <string>
#include <string_view>
#include <vector>
using namespace std;
map<char, pair<int, int>> m_num = {
{'7', {0,0}}, {'8', {0,1}}, {'9', {0,2}},
{'4', {1,0}}, {'5', {1,1}}, {'6', {1,2}},
{'1', {2,0}}, {'2', {2,1}}, {'3', {2,2}},
{'x', {3,0}}, {'0', {3,1}}, {'A', {3,2}},
};
map<char, pair<int, int>> m_dir = {
{'x', {0,0}}, {'^', {0,1}}, {'A', {0,2}},
{'<', {1,0}}, {'v', {1,1}}, {'>', {1,2}},
};
map<pair<int, int>, char> rev_num;
map<pair<int, int>, char> rev_dir;
map<pair<char, char>, vector<string>> p;
vector<pair<pair<int, int>, char>> directions = {
{{1,0}, 'v'}, {{-1,0}, '^'}, {{0,1}, '>'}, {{0,-1}, '<'}
};
int distance(int cx, int cy, int dx, int dy) {
return abs(cx-dx) + abs(cy-dy);
}
vector<string> paths(char c, char d,
map<char, pair<int, int>>& m, map<pair<int, int>, char>& rev) {
if (p[make_pair(c, d)].size() != 0) return p[make_pair(c, d)];
if (c == d) return {""};
if (c == 'x') return {};
vector<string> v;
auto [cx, cy] = m[c];
auto [dx, dy] = m[d];
for (auto [dir, dirc] : directions) {
pair i = make_pair(cx+dir.first, cy+dir.second);
if (distance(cx, cy, dx, dy) < distance(i.first, i.second, dx, dy))
continue;
auto next = paths(rev[i], d, m, rev);
for (auto n : next)
v.push_back(dirc+n);
}
return p[make_pair(c, d)] = v;
}
string pushes_human(char c, char d) {
auto p = paths(c, d, m_dir, rev_dir);
auto shortest = numeric_limits<size_t>::max();
string ret;
for (auto path : p) {
if (path.size() + 1 < shortest) {
ret = path + 'A';
shortest = path.size() + 1;
}
}
return ret;
}
string pushes_dir1(char c, char d) {
auto p = paths(c, d, m_dir, rev_dir);
auto shortest = numeric_limits<size_t>::max();
string ret;
for (auto path : p) {
path = 'A' + path + 'A';
string pushes = "";
for (unsigned i = 0; i < path.size()-1; i++)
pushes += pushes_human(path[i], path[i+1]);
if (pushes.size() < shortest) {
ret = pushes;
shortest = pushes.size();
}
}
return ret;
}
string pushes_numpad(char c, char d) {
auto p = paths(c, d, m_num, rev_num);
auto shortest = numeric_limits<size_t>::max();
string ret;
for (auto path : p) {
path = 'A' + path + 'A';
string pushes = "";
for (unsigned i = 0; i < path.size()-1; i++)
pushes += pushes_dir1(path[i], path[i+1]);
if (pushes.size() < shortest) {
ret = pushes;
shortest = pushes.size();
}
}
return ret;
}
int64_t numeric(const string& code) {
return (code[0]-'0')*100 + (code[1]-'0')*10 + (code[2]-'0');
}
int main() {
for (auto [k, v] : m_num) rev_num[v] = k;
for (auto [k, v] : m_dir) rev_dir[v] = k;
string line;
int64_t tot = 0;
while (getline(cin, line)) {
string ppp;
int64_t num = numeric(line);
line = 'A' + line;
for (unsigned i = 0; i < line.size()-1; i++)
ppp += pushes_numpad(line[i], line[i+1]);
cout << ppp << endl;
tot += ppp.size() * num;
}
cout << tot << endl;
return 0;
}
|
