| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 97 | 31 | 24 | 40.000% |
Скорее всего, вы знакомы с римскими числами. А также наверняка слышали фразу, что Москва --- это третий Рим. Поэтому мы решили по аналогии с римскими числами придумать их продвинутую версию --- московские числа.
Цифрами московского числа являются заглавные английские буквы от 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$.
Для каждой заготовки выведите две строки. В первой из них выведите в десятичной системе счисления максимальное значение числа, которое может получиться из этой заготовки. А во второй строке --- саму заготовку, у которой знаки вопроса заменены на буквы английского алфавита таким образом, чтобы достигалось максимальное значение.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $S \le 1000$, $s_i$ не содержит << |
| 2 | 9 | $S \le 3 \cdot 10^5$, $s_i$ не содержит << |
| 3 | 40 | $S \le 1000$ & $s_i$ содержит не более трёх << |
| 4 | 20 | $S \le 1000$ |
| 5 | 25 | $S \le 3 \cdot 10^5$ |
4 BBBC ???? A?B?C?D YYYYY?
-5 BBBC 20000000000000 ZZZZ 15000000000034 AZBZCZD 6000000000000 YYYYYY