Masala #KD4LYART5U
The first game
On the physical education class, first-graders Petia and Vasia are playing an exciting game. In front of the kids, there are \(n\) pillars of different heights. The boys have \(m\) rings, which they throw onto the pillars one by one, with Petia starting first. The boys found out that Petia can throw a ring onto a pillar only if the height of that pillar is not less than \(l_1\) and not greater than \(r_1\). He cannot throw a ring onto a pillar that is too high or too low. However, if the pillar has a suitable height, the throw is guaranteed to be successful. Similarly, Vasia can throw a ring only onto pillars with a height not less than \(l_2\) and not greater than \(r_2\), and he guarantees success on any such pillar. Phys-ed teacher Andrey Sergeevich promised to give an "A" grade to the one of the boys who throws more rings onto the pillars by the end of the game. Help the boys figure out who will win with optimal play.
There are two integers in the first line of the input file \(n\) и \(m\) — the number of columns and rings, respectively \((1 ≤ m ≤ n ≤ 10^5 )\). Сthe next two lines contain numbers \(l_1, r_1\) и \(l_2, r_2\) — the minimum and maximum height of the columns on which Petya and Vasya can throw rings, respectively\((1 ≤ l_1 ≤ r_1 ≤ 10^9 , 1 ≤ l_2 ≤ r_2 ≤ 10^9 )\). The last line contains \(n\) the numbers describing the height of the columns, the height of each column is a positive integer and does not exceed \(10^9\).
In the output file, output "Petya" if Petya wins, "Vasya" if Vasya wins, or "Draw" if, with optimal play, both boys throw an equal number of rings on the columns.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 3 1 2 2 4 1 2 3 4 |
Petya |
| 2 |
4 4 1 4 1 4 1 2 3 4 |
Draw |
| 3 |
4 4 1 2 1 4 1 2 3 4 |
Vasya |
In the first example, Petya first throws the ring onto a column of height 2. In response, Vasya can throw a ring on columns 3 or 4 high, but whichever one he chooses, Petya will throw a third ring on a column 1 high and win — he threw 2 rings, and Vasya only one. In the second example, each player can throw a ring on any column, so both will throw two rings and the game will end in a draw. In the third example, Petya throws the ring on one of the two columns available to him with the first move, and Vasya throws the ring on the second of these columns with the second move. Now Petya has no columns on which he can throw the ring, he throws the third ring, but does not hit. Vasya throws the last ring on any of the columns of height 3 or 4.
Telegram kanalimizga obuna bo'ling