In this HackerEarth Costly Phone Number problem solution A cell phone company is trying out its new model of cell phone. Here's how its structure is:

The keypad has 11 buttons corresponding to digits from 0 to 9 and one additional button called Add. After pressing any button from 0 to 9, the corresponding digit appears on the screen. The Add button replaces the last two digits appearing on the screen with their sum taken modulo 10. (See sample test for more clarity). If there are less than two digits currently on the screen, pressing Add does nothing.

Each button has a non-negative cost of pressing associated with it. The cost of pressing Add button is always 0. Given the cost of pressing each button and the target phone number, find the minimum cost of feeding that number into the phone screen using a sequence of button presses.


HackerEarth Costly Phone Number problem solution


HackerEarth Costly Phone Number problem solution.

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int MAX_COST = 1000;
const int MAX_TEST = 1000;
const int MAX_LEN = 1000;

int main() {

//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);

int T, cost[10], ans, n;
string s;
bool ok;

scanf("%d", &T);
assert(T <= MAX_TEST && T);

while (T--) {

ok = true;
ans = 0;

for (int i = 0; i < 10; ++i) {
scanf("%d", cost + i);
assert(cost[i] <= MAX_COST);
}

while (ok) {
ok = false;
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 10; ++j) {
if (cost[(i + j) % 10] > cost[i] + cost[j]) {
cost[(i + j) % 10] = cost[i] + cost[j];
ok = true;
}
}
}
}

scanf("%d", &n);

cin >> s;

assert(s.size() == n && n <= MAX_LEN && n);

for (int i = 0; i < n; ++i) {
assert(s[i] >= '0' && s[i] <= '9');
ans += cost[s[i] - '0'];
}

printf("%d\n", ans);
}
return 0;
}