Петя и Вадим гуляли по лесу и наткнулись на речку. На речке было N бегемотов
25 Просмотров
Задание:
Петя и Вадим гуляли по лесу и наткнулись на речку. На речке было 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))
Объяснение:
- Функция
solve
принимает параметрыn
,s
,a
иb
. - Внутри функции мы сначала подсчитываем начальное количество бегемотов на берегу (
shore_count
). - Затем мы вычисляем максимальное и минимальное количество бегемотов, которые могут остаться на берегу по версии Пети (
min_petya
иmax_petya
). - Аналогично мы вычисляем максимальное и минимальное количество бегемотов, которые могут остаться на берегу по версии Вадима (
max_vadim
иmin_vadim
). - Наконец, мы сравниваем минимальные значения для обоих друзей и возвращаем соответствующий ответ.
Сложность:
- Время: O(n)
- Память: O(1)