Задача №114895. Московские числа
Скорее всего, вы знакомы с римскими числами. А также наверняка слышали фразу, что Москва — это третий Рим. Поэтому мы решили по аналогии с римскими числами придумать их продвинутую версию — московские числа .
Цифрами московского числа являются заглавные английские буквы от A до Z. Числом является строка из нескольких цифр. Каждой цифре сопоставим значение:
| A | \(1\) | H | \(5 \cdot 10 ^ {3}\) | O | \(10 ^ {7}\) | V | \(5 \cdot 10 ^ {10}\) |
| B | \(5\) | I | \(10 ^ {4}\) | P | \(5 \cdot 10 ^ {7}\) | W | \(10 ^ {11}\) |
| C | \(10\) | J | \(5 \cdot 10 ^ {4}\) | Q | \(10 ^ {8}\) | X | \(5 \cdot 10 ^ {11}\) |
| D | \(50\) | K | \(10 ^ {5}\) | R | \(5 \cdot 10 ^ {8}\) | Y | \(10 ^ {12}\) |
| E | \(100\) | L | \(5 \cdot 10 ^ {5}\) | S | \(10 ^ {9}\) | Z | \(5 \cdot 10 ^ {12}\) |
| F | \(500\) | M | \(10 ^ {6}\) | T | \(5 \cdot 10 ^ {9}\) | ||
| G | \(10 ^ {3}\) | N | \(5 \cdot 10 ^ {6}\) | U | \(10 ^ {10}\) |
Значение числа равно сумме вкладов цифр, из которых оно состоит. Вклад цифры бывает как положительным, так и отрицательным. Если правее цифры в числе нет строго большей цифры, то вклад этой цифры равен её значению. Иначе вклад равен её значению, взятому со знаком минус.
Например,
- BBA имеет значение \(5+5+1=11\);
- BBBC имеет значение \(-5+(-5)+(-5)+10=-5\);
- ABC имеет значение \(-1+(-5)+10=4\);
- BAC имеет значение \(-5+(-1)+10=4\);
- ACA имеет значение \(-1+10+1=10\).
Вам даны несколько заготовок чисел. Каждая заготовка представляет собой строку из заглавных английских букв и знаков вопроса. Для каждой заготовки необходимо определить, какое максимальное число может получиться, если каждый знак вопроса заменить на цифру московского числа.
В первой строке дано одно целое число \(t\) — количество заготовок (\(1 \le t \le 50\,000\)).
В следующих \(t\) строках даны строки \(s_i\), состоящие из заглавных английских букв и символов « ? » — заготовки для чисел. Сумма длин строк \(s_i\) не превышает \(300\,000\).
Для каждой заготовки выведите две строки. В первой из них выведите в десятичной системе счисления максимальное значение числа, которое может получиться из этой заготовки. А во второй строке — саму заготовку, у которой знаки вопроса заменены на буквы английского алфавита таким образом, чтобы достигалось максимальное значение.
Обозначим сумму длин строк \(s_i\) как \(S\).
| Ограничения | |||||
| Подзадача | Баллы | \(S\) | дополнительно | Необх. подзадачи | Информация о |
| проверке | |||||
| 1 | 6 | \(S \le 1000\) | \(s_i\) не содержит ? | первая ошибка | |
| 2 | 9 | \(S \le 3 \cdot 10^5\) | \(s_i\) не содержит ? | 1 | первая ошибка |
| 3 | 40 | \(S \le 1000\) | \(s_i\) содержит не более трёх ? | 1 | первая ошибка |
| 4 | 20 | \(S \le 1000\) | – | У, 1, 3 | первая ошибка |
| 5 | 25 | \(S \le 3 \cdot 10^5\) | – | У, 1–4 | первая ошибка |
4 BBBC ???? A?B?C?D YYYYY?
-5 BBBC 20000000000000 ZZZZ 15000000000034 AZBZCZD 6000000000000 YYYYYY