시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 134 | 46 | 26 | 28.571% |
Циклическим сдвигом строки s0s1…sn-1 на k позиций назовем строку sksk+1…sns1..sk-1. Например, циклическим сдвигом строки «abcde» на две позиции является строка «cdeab». В этой задаче далее будут рассматриваться только строки, состоящие из десятичных цифр от 0 до 9. Произвольной такой строке, первый символ которой не является нулем, можно сопоставить число, десятичной записью которого она является. Строкам, которые начинаются с нуля, никакое число сопоставляться не будет. Например, строке 123 сопоставляется число сто двадцать три, а строке 0123 не сопоставляется никакое число.
Пусть заданы две строки: s и t. Обозначим как S набор всех циклических сдвигов строки s, а как T – набор всех циклических сдвигов строки t. Например, если s = «1234», то S содержит строки «1234», «2341», «3412», «4123». Как NUM(A) обозначим набор чисел, соответствующих строкам из набора A.
Требуется написать программу, которая по строкам s и t определит, максимальное число, представимое в виде разности x – y, где x принадлежит NUM(S), а y принадлежит NUM(T).
Например, если s = «25», t = «12», то NUM(S) содержит числа 25 и 52, NUM(T) – числа 12 и 21, их попарные разности это 25 – 12 = 13, 25 – 21 = 4, 52 – 12 = 40, 52 – 21 = 31. Из этих разностей максимальной является 40.
Первая строка входного файла содержит строку s, вторая строка входного файла – строку t. Обе строки непусты, содержат только цифры, из которых хотя бы одна не является нулем, и имеют длину не более 3000 символов.
В выходной файл выведите искомое число без ведущих нулей.
25 12
40
100 1
99