Минимальное число для Васи

@Phisfo · Регистрация: 15.12.2024

Студворк — интернет-сервис помощи студентам

Порядок во всём

Ограничение по времени: 1,5 секунды
Ограничение по памяти: 256 мегабайт

Вася — очень порядочный мальчик, он любит порядок во всём.

У него в тетради есть столбик натуральных чисел, и он хочет изменить его так, чтобы числа шли по порядку, то есть по неубыванию. При этом Вася, естественно, ничего не хочет зачёркивать, поэтому единственное, что ему остаётся — это дописать цифры в конец некоторых чисел.

Вася хочет, чтобы после дописывания цифр последнее число в списке оказалось наименьшим возможным. Найдите это число.

Формат входных данных

Первая строка входных данных содержит целое число n (2≤n≤3⋅10⁵) — количество чисел в тетрадке у Васи.

Следующие n строк содержат n чисел, записанных в тетрадке, по одному в каждой строке. Все числа натуральные, не превосходящие 10⁹.

Формат выходных данных

Программа должна вывести наименьшее число, которое могло оказаться у Васи в конце списка.

Система оценки

Решения, верно работающие, когда n≤5 и при этом все числа в списке однозначные, будут оцениваться в 10 баллов.
Решения, верно работающие, когда n≤5 и при этом все числа в списке не превосходят 999, будут оцениваться в 20 баллов.
Решения, верно работающие, когда n≤5 без дополнительных ограничений на числа, будут оцениваться в 40 баллов.
Решения, верно работающие, когда n≤1000 без дополнительных ограничений на числа, будут оцениваться в 60 баллов.

Замечание

В первом примере числа уже упорядочены, Васе не нужно ничего дописывать.
Во втором примере Васе можно приписать ко второму числу цифру 3, тогда числа станут равны 13, а значит, будут расположены по неубыванию. При этом 13 — это минимально возможное последнее число.
В третьем примере Вася может, например, получить числа 20, 25, 100. Возможны и другие варианты, но последнее число при любом способе дописывания цифр получится не меньше 100.

@LinFart · 16.12.2024, 18:53

Python
1
2
3
4
5
6
7
8
n = int(input())
numbers = [input().strip() for _ in range(n)]
 
for i in range(1, n):
    if numbers[i] < numbers[i - 1]:
        numbers[i] = numbers[i - 1]
 
print(numbers[-1])

@Creater321 · 12.09.2025, 12:11

Если очередное число уже больше или равно предыдущего числа (после дописывания цифр к предыдущему числу), то его нужно оставить без изменений. Если новое число является префиксом (началом) предыдущего числа, то нужно дописать цифры так, чтобы оно стало равно предыдущему числу. Во всех остальных случаях нужно дописывать нули, чтобы получить число такой же длины или на 1 большей длины.

Ответ:
48
50
67
300
820
820
6300
7010
54600
54600

Источник

@andrey_f · 16.09.2025, 10:45

так чтоль

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
n = int(input())
nums = [input().strip() for _ in range(n)]
 
def solve():
    res = [nums[0]]
    for i in range(1, n):
        prev, curr = res[-1], nums[i]
        
        if prev <= curr:
            res.append(curr)
            continue
            
        # Находим общий префикс
        j = 0
        while j < min(len(prev), len(curr)) and prev[j] == curr[j]:
            j += 1
        
        if j == len(curr):
            # curr - префикс prev
            suffix = prev[j:]
            if all(c == '9' for c in suffix):
                # Все девятки - нужно добавить разряд
                res.append(curr + '0' * (len(suffix) + 1))
            else:
                # Увеличиваем суффикс на 1
                new_suffix = str(int(suffix) + 1).zfill(len(suffix))
                res.append(curr + new_suffix)
        else:
            if j < len(prev) and prev[j] < curr[j]:
                res.append(curr)
            elif j < len(prev) and prev[j] > curr[j]:
                res.append(curr + '0' * (len(prev) - len(curr)))
            else:
                res.append(curr)
    
    return res[-1]
 
print(solve())

@drahvalov · 01.10.2025, 16:44

andrey_f, засёк, у меня по времени Ваш вариант не проходит (по памяти не мерил).

Как не проходит по времени и мой вариант:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input())
l = [int(input()) for _ in range(n)]
 
for i in range(1, n):
    if l[i] < l[i-1]:
        prev, curr = str(l[i-1]), str(l[i])
        if prev[:len(curr)] == curr:
            l[i] = l[i-1]
        else:
            while l[i] < l[i-1]:
                l[i] *= 10
 
print(l[-1])

Добавлено через 33 минуты
И такой вариант тоже не проходит по времени(

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
l = [int(input()) for _ in range(n)]
 
for i in range(1, n):
    if l[i] < l[i-1]:
        prev, curr = l[i-1], l[i]
                
        curr_dig = 0
        while curr // 10**curr_dig > 0:  #  ищем количество разрядов в текущем числе
            curr_dig += 1
 
        if prev // 10** (curr_dig + 1) == curr:
            l[i] = l[i-1]
        else:
            while l[i] < l[i-1]:
                l[i] *= 10
 
print(l[-1])

Новые блоги и статьи Все статьи Все блоги /
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .

@Phisfo 0 / 0 / 0 Регистрация: 15.12.2024 Сообщений: 1

	Минимальное число для Васи 15.12.2024, 11:09. Показов 2678. Ответов 4 Метки нет (Все метки) Порядок во всём Ограничение по времени: 1,5 секунды Ограничение по памяти: 256 мегабайт Вася — очень порядочный мальчик, он любит порядок во всём. У него в тетради есть столбик натуральных чисел, и он хочет изменить его так, чтобы числа шли по порядку, то есть по неубыванию. При этом Вася, естественно, ничего не хочет зачёркивать, поэтому единственное, что ему остаётся — это дописать цифры в конец некоторых чисел. Вася хочет, чтобы после дописывания цифр последнее число в списке оказалось наименьшим возможным. Найдите это число. Формат входных данных Первая строка входных данных содержит целое число n (2≤n≤3⋅10⁵) — количество чисел в тетрадке у Васи. Следующие n строк содержат n чисел, записанных в тетрадке, по одному в каждой строке. Все числа натуральные, не превосходящие 10⁹. Формат выходных данных Программа должна вывести наименьшее число, которое могло оказаться у Васи в конце списка. Система оценки Решения, верно работающие, когда n≤5 и при этом все числа в списке однозначные, будут оцениваться в 10 баллов. Решения, верно работающие, когда n≤5 и при этом все числа в списке не превосходят 999, будут оцениваться в 20 баллов. Решения, верно работающие, когда n≤5 без дополнительных ограничений на числа, будут оцениваться в 40 баллов. Решения, верно работающие, когда n≤1000 без дополнительных ограничений на числа, будут оцениваться в 60 баллов. Замечание В первом примере числа уже упорядочены, Васе не нужно ничего дописывать. Во втором примере Васе можно приписать ко второму числу цифру 3, тогда числа станут равны 13, а значит, будут расположены по неубыванию. При этом 13 — это минимально возможное последнее число. В третьем примере Вася может, например, получить числа 20, 25, 100. Возможны и другие варианты, но последнее число при любом способе дописывания цифр получится не меньше 100. 0

@Creater321 0 / 0 / 0 Регистрация: 12.09.2025 Сообщений: 1
	12.09.2025, 12:11
	Если очередное число уже больше или равно предыдущего числа (после дописывания цифр к предыдущему числу), то его нужно оставить без изменений. Если новое число является префиксом (началом) предыдущего числа, то нужно дописать цифры так, чтобы оно стало равно предыдущему числу. Во всех остальных случаях нужно дописывать нули, чтобы получить число такой же длины или на 1 большей длины. Ответ: 48 50 67 300 820 820 6300 7010 54600 54600 Источник 0