0393. Игра

Input file name: game.in
Output file name: game.out
Time limit: 2 s
Memory limit: 256 megabytes

На уроке физкультуры первоклассники Петя и Вася играют в увлекательную игру. Перед ребятами в ряд стоит n столбиков разной высоты. У мальчиков есть m колец, которые они по очереди кидают на столбики, причем если на столбике уже есть кольцо, то кидать кольцо на этот столбик нельзя. Петя кидает первым.

Ребята выяснили, что Петя может закинуть кольцо на столбик только, если высота этого столбика не меньше l1 и не больше r1. На слишком высокий или слишком низкий столбик он закинуть кольцо не может. Зато, если столбик имеет подходящую высоту, бросок гарантированно заканчивается успехом. Аналогично, Вася может закинуть кольцо только на столбики с высотой не меньше l2 и не больше r2 и гарантированно закидывает кольцо на любой такой столбик.

Физрук Андрей Сергеевич обещал поставить пятерку тому из ребят, кто по итогам игры закинет больше колец на столбики. Помогите ребятам выяснить, кто из них выиграет при оптимальной игре.

Формат входного файла

В первой строке входного файла находятся два целых числа n и m – количество столбиков и колец, соответственно (1 ≤ m ≤ n ≤ 105). Следующие две строки содержат числа l1, r1 и l2, r2 – минимальную и максимальную высоту столбиков, на которые могут кидать колечки Петя и Вася, соответственно (1 ≤ l1 ≤ r1 ≤ 109, 1 ≤ l2 ≤ r2 ≤ 109). В последней строке содержится n чисел, описывающих высоту столбиков, высота каждого столбика является целым положительным числом и не превышает 109.

Формат выходного файла

В выходной файл выведите <<Petya>>, если выиграет Петя, <<Vasya>>, если выиграет Вася, или <<Draw>>, если при оптимальной игре оба мальчика закинут на столбики равное число колец.

Пример:

game.ingame.out
4 3 1 2 2 4 1 2 3 4 Petya
4 4 1 4 1 4 1 2 3 4 Draw
4 4 1 2 1 4 1 2 3 4 Vasya

В первом примере Петя сначала кидает кольцо на столбик высоты 2. Вася может в ответ закинуть кольцо на столбики высотой 3 или 4, но какой бы из них он не выбрал, Петя закинет третье кольцо на столбик высотой 1 и выиграет – он закинул 2 кольца, а Вася только одно.

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

В третьем примере Петя первым ходом закидывает кольцо на один из двух доступных ему столбиков, а Вася вторым ходом закидывает кольцо на второй из этих столбиков. Теперь у Пети нет столбиков, на который он может закинуть кольцо, он кидает третье кольцо, но не попадает. Вася же закидывает последнее кольцо на любой из столбиков высоты 3 или 4.


Source: Karelian school team championship. November 2014.

Discuss       Submit a solution



Printable version