36 Просмотров

Задание:

Петя и Вадим гуляли по лесу и наткнулись на речку. На речке было N бегемотов. Некоторые из них были в воде, а некоторые — на берегу. Петя и Вадим пошли гулять дальше и услышали несколько всплесков. Петя услышал A всплесков и решил, что при каждом всплеске какой-то из бегемотов нырнул в воду (при чём нырнуть мог как кто-то с берега, так и тот, кто уже был в воде). Вадим же услышал B всплесков и считает, что каждый из них означает, что либо какой-то бегемот из реки вышел на берег, либо какой-то бегемот с берега нырнул в воду. Каждый из друзей начал считать, какое минимальное число бегемотов могло остаться на берегу. Определите, кто из них мог получить наименьший результат.

Формат ввода
В первой строке дано целое число N — количество бегемотов (1≤N≤10^5 ).
Во второй строке дана строка длины N, состоящая из нулей и единиц. Если на i позиции стоит единица, то i-й бегемот изначально находился на берегу, иначе — в воде.
В третьей строке дано целое неотрицательное число A (0≤A≤10^5).
В четвёртой строке дано целое неотрицательное число B (0≤B≤10^5 ).

Формат вывода
Выведите «Petya» (без кавычек), если Петя может получить наименьшее число бегемотов на берегу, «Vadim», если его может получить Вадим, и «Draw», если никто из них не может получить наименьшее число.

Язык программирования Python.

Ответ на задание:

</pre>
def solve(n, s, a, b):
"""
Решает задачу о бегемотах.

Args:
n: Количество бегемотов.
s: Строка, где 1 - бегемот на берегу, 0 - в воде.
a: Количество всплесков по версии Пети.
b: Количество всплесков по версии Вадима.

Returns:
"Petya", "Vadim" или "Draw".
"""
# Подсчитаем начальное количество бегемотов на берегу.
shore_count = sum(1 for c in s if c == '1')

# Максимальное и минимальное количество бегемотов,
# которые могут остаться на берегу по версии Пети.
min_petya = max(0, shore_count - a)
max_petya = min(shore_count, n - a)

# Максимальное и минимальное количество бегемотов,
# которые могут остаться на берегу по версии Вадима.
max_vadim = min(shore_count + b, n)
min_vadim = max(0, shore_count + b - n)

# Определим, кто может получить наименьшее число бегемотов.
if min_petya < min_vadim:
return "Petya"
elif min_vadim < min_petya:
return "Vadim"
else:
return "Draw"

# Считываем входные данные.
n = int(input())
s = input()
a = int(input())
b = int(input())

# Выводим ответ.
print(solve(n, s, a, b))

Объяснение:

1. Функция solve принимает параметры n, s, a и b.
2. Внутри функции мы сначала подсчитываем начальное количество бегемотов на берегу (shore_count).
3. Затем мы вычисляем максимальное и минимальное количество бегемотов, которые могут остаться на берегу по версии Пети (min_petya и max_petya).
4. Аналогично мы вычисляем максимальное и минимальное количество бегемотов, которые могут остаться на берегу по версии Вадима (max_vadim и min_vadim).
5. Наконец, мы сравниваем минимальные значения для обоих друзей и возвращаем соответствующий ответ.

Сложность:

• Время: O(n)
• Память: O(1)