Условие:
Вася — очень порядочный мальчик, он любит порядок во всём.
У него в тетради есть столбик натуральных чисел, и он хочет изменить его так, чтобы числа шли по порядку, то есть по неубыванию. При этом Вася, естественно, ничего не хочет зачёркивать, поэтому единственное, что ему остаётся — это дописать цифры в конец некоторых чисел.
Вася хочет, чтобы после дописывания цифр последнее число в списке оказалось наименьшим возможным. Найдите это число.
Входные данные
Первая строка входных данных содержит целое число n
(2≤n≤3⋅105
) — количество чисел в тетрадке у Васи.
Следующие n
строк содержат n
чисел, записанных в тетрадке, по одному в каждой строке. Все числа натуральные, не превосходящие 109
.
Выходные данные
Программа должна вывести наименьшее число, которое могло оказаться у Васи в конце списка.
Решение:
Чтобы решить задачу, давайте разберёмся с условиями и шагами, которые нам нужно предпринять.
Шаг 1: Понимание задачи
Вася хочет, чтобы числа в его тетрадке были упорядочены по неубыванию. Он может добавлять цифры к числам, но не может их изменять или удалять. Наша цель — сделать так, чтобы последнее число в списке было как можно меньше.Шаг 2: Входные данные
Мы получаем:1. Число
n — количество чисел.2. Последующие
n строк содержат сами числа.Шаг 3: Алгоритм
1. Прочитаем все числа и сохраним их в список.2. Начнём с последнего числа и будем проверять, может ли оно быть меньше или равно предыдущему числу в списке, добавляя к нему цифры.
3. Если текущее число больше предыдущего, мы будем добавлять к нему цифры, чтобы оно стало равным или меньше предыдущего.
4. Мы будем делать это до тех пор, пока не дойдём до первого числа.
Шаг 4: Реализация
Теперь давайте реализуем этот алгоритм на Python:1. Мы считываем количество чисел и сами числа. 2. Начинаем с последнего числа и проходим по списку в обратном порядке. 3. Если текущее число больше последнего, мы обновляем последнее число, добавляя к нему цифры, чтобы оно стало равным текущему. 4. В конце выводим последнее число, которое будет наименьшим возможным. Допустим, у нас есть числа: , , . - Начинаем с , проверяем — оно меньше, значит, остаётся. - Проверяем — оно меньше , значит, остаётся. - Ответ будет . Таким образом, мы можем получить наименьшее число, которое может оказаться в конце списка, следуя описанному алгоритму.