Длинный плакат - задача по информатике Юный художник Вася нарисовал плакат с очень большим числом и решил повесить его на самую длинную стену школы. К сожалению, даже самая длинная стена оказалась недостаточно длинной, поэтому ему придется укорачивать плакат до нужной длины. Вася — максималист, поэтому он хочет, чтобы число, получившееся после всех правок, было как можно больше. Васе нужно вырезать из плаката любые K цифр, но он ни за что не согласится переставлять получившиеся кусочки местами, так как это нарушит цветовой баланс плаката Васе переделать плакат.
Входные данные
В первой строке входных данных записано целое число N, записанное на изначальном длинном плакате. Гарантируется, что в N не менее двух и не более 200 000 цифр (10 ≤ N < 10200 000).
Во второй строке содержится целое число K — количество цифр, которые необходимо вырезать из плаката. Гарантируется, что K не меньше одного и строго меньше количества цифр числа N (1 ≤ K, 10K ≤ N).
Выходные данные
Выведите максимальное число, которое может получиться на плакате после его укорачивания.
Система оценки
Решения, верно работающие для N < 109, будут оцениваться в
Решения, верно работающие для N < 101000, будут оцениваться в
Пример
Ввод:
2023
1
Вывод:
223
Пояснения:
На плакате записано число 2023, из него нужно вырезать одну цифру. Максимально число, которое можно при этом получить, равно 223.
Ответы на вопрос:
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)
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)
Объяснение:
Реши свою проблему, спроси otvet5GPT
-
Быстро
Мгновенный ответ на твой вопрос -
Точно
Бот обладает знаниями во всех сферах -
Бесплатно
Задай вопрос и получи ответ бесплатно
Популярно: Информатика
-
dasha19080016.02.2022 21:17
-
мария238201.06.2020 19:06
-
sasha1341011.01.2022 18:21
-
ShkolnikN1509.09.2021 11:03
-
polinapoluunaa03.03.2022 18:01
-
klemiatoeva13.04.2022 01:42
-
koliakhotyn28.06.2020 02:00
-
lime89cc18.09.2020 22:52
-
Sakura17111.04.2022 00:46
-
Зоромдед26.08.2022 16:13
Есть вопросы?
-
Как otvet5GPT работает?
otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса. -
Сколько это стоит?
Проект находиться на стадии тестирования и все услуги бесплатны. -
Могу ли я использовать otvet5GPT в школе?
Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое! -
В чем отличия от ChatGPT?
otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.