Question

Длинный плакат - задача по информатике Юный художник Вася нарисовал плакат с очень большим числом и решил повесить его на самую длинную стену школы. К сожалению, даже самая длинная стена оказалась недостаточно длинной, поэтому ему придется укорачивать плакат до нужной длины. Вася — максималист, поэтому он хочет, чтобы число, получившееся после всех правок, было как можно больше. Васе нужно вырезать из плаката любые K цифр, но он ни за что не согласится переставлять получившиеся кусочки местами, так как это нарушит цветовой баланс плаката. Помогите Васе переделать плакат. Входные данные В первой строке входных данных записано целое число N, записанное на изначальном длинном плакате. Гарантируется, что в N не менее двух и не более 200 000 цифр (10 ≤ N < 10200 000). Во второй строке содержится целое число K — количество цифр, которые необходимо вырезать из плаката. Гарантируется, что K не меньше одного и строго меньше количества цифр числа N (1 ≤ K, 10K ≤ N). Выходные данные Выведите максимальное число, которое может получиться на плакате после его укорачивания. Система оценки Решения, верно работающие для N < 109, будут оцениваться в 30 баллов. Решения, верно работающие для N < 101000, будут оцениваться в 60 баллов. Пример Ввод: 2023 1 Вывод: 223 Пояснения: На плакате записано число 2023, из него нужно вырезать одну цифру. Максимально число, которое можно при этом получить, равно 223.

Answer 1

Ответ:

import math

import sys

def get_first_max(tree, idx, l, r, L, R):

 if r <= L or R <= l:

   return -1

 if l >= L and r <= R:

   return tree[idx]

 m = (l + r) // 2

 return max(get_first_max(tree, idx * 2 + 1, l, m, L, R), get_first_max(tree, idx * 2 + 2, m, r, L, R))

num = input()

k = int(input())

n = len(num)

N = 2**math.ceil(math.log2(n))

M1 = 10 ** 7

M2 = 10 ** 6

tree = [-1] * (2 * N)

for i in range(n):

 tree[N - 1 + i] = int(num[i]) * M1  + M2 - i

for i in range(N - 2, -1, -1):

 tree[i] = max(tree[2 * i + 1], tree[2 * i + 2])

i = 0

ans = ""

for _ in range(n - k):

 maximum = get_first_max(tree, 0, 0, N, i, i + k + 1)

 val = maximum // M1

 pos = M2 - maximum % M1

 ans += str(val)

 k -= pos - i

 i = pos + 1

 if k == 0:

   ans += num[i:]

   break

print(ans)

Answer 2

Для решения этой задачи вы можете использовать следующий алгоритм:

1. Считайте входные данные: число N и количество цифр, которые необходимо вырезать K.

2. Преобразуйте число N в строку, чтобы легче работать с его цифрами.

3. Создайте пустую стековую структуру данных (например, стек или список) для хранения цифр.

4. Пройдитесь по каждой цифре числа N (начиная с первой) и добавляйте ее в стек, при этом, если текущая цифра меньше предыдущей, удаляйте предыдущую цифру из стека и уменьшайте K на 1, пока K больше нуля или текущая цифра не меньше предыдущей.

5. Если K стало равным нулю, добавьте все оставшиеся цифры из числа N в стек.

6. Преобразуйте стек обратно в строку.

7. Выведите полученную строку как максимальное число.

Вот Python-код, реализующий этот алгоритм:

pythonCopy code
N = input()  # Считываем число N как строку
K = int(input())  # Считываем количество цифр, которые нужно удалить

stack = []  # Создаем стек для хранения цифр

for digit in N:
    # Пока стек не пуст и K больше нуля, и текущая цифра меньше предыдущей
    while K > 0 and stack and digit < stack[-1]:
        stack.pop()  # Удаляем последний элемент из стека
        K -= 1  # Уменьшаем K

    stack.append(digit)  # Добавляем текущую цифру в стек

# Если K осталось невырезанных цифр, удаляем их с конца стека
while K > 0:
    stack.pop()
    K -= 1

# Преобразуем стек обратно в строку и выводим результат
result = ''.join(stack)
print(result)

Этот код должен работать для чисел N с разными длинами в соответствии с ограничениями задачи.