Задача №115371. Порядок во всём
Вася — очень порядочный мальчик, он любит порядок во всём.
У него в тетради есть столбик натуральных чисел, и он хочет изменить его так, чтобы числа шли по порядку, то есть по неубыванию. При этом Вася, естественно, ничего не хочет зачёркивать, поэтому единственное, что ему остаётся — это дописать цифры в конец некоторых чисел.
Вася хочет, чтобы после дописывания цифр последнее число в списке оказалось наименьшим возможным. Найдите это число.
Первая строка входных данных содержит целое число \(n\) (\(2 \le n \le 3 \cdot 10^{5}\)) — количество чисел в тетрадке у Васи.
Следующие \(n\) строк содержат \(n\) чисел, записанных в тетрадке, по одному в каждой строке. Все числа натуральные, не превосходящие \(10^9\).
Программа должна вывести наименьшее число, которое могло оказаться у Васи в конце списка.
Решения, верно работающие, когда \(n \le 5\) и при этом все числа в списке однозначные, будут оцениваться в 10 баллов.
Решения, верно работающие, когда \(n \le 5\) и при этом все числа в списке не превосходят \(999\), будут оцениваться в 20 баллов.
Решения, верно работающие, когда \(n \le 5\) без дополнительных ограничений на числа, будут оцениваться в 40 баллов.
Решения, верно работающие, когда \(n\le 1000\) без дополнительных ограничений на числа, будут оцениваться в 60 баллов.
В первом примере числа уже упорядочены, Васе не нужно ничего дописывать.
Во втором примере Васе можно приписать ко второму числу цифру 3, тогда числа станут равны 13, а значит, будут расположены по неубыванию. При этом 13 — это минимально возможное последнее число.
В третьем примере Вася может, например, получить числа 20, 25, 100. Возможны и другие варианты, но последнее число при любом способе дописывания цифр получится не меньше 100.
3 1 5 7
7
2 13 1
13
3 20 2 1
100