Welcome to ZOJ
72 - ZOJ Monthly, November 2008 - G
Golf Match

Time Limit: 1 Second      Memory Limit: 32768 KB

Golf is a sport in which a player, using many types of clubs including a driver and a putter, hits a ball into each hole on a golf course in the lowest possible number of strokes. Regarding golf, most people are familiar with stroke play, where the players are ranked according to the total strokes they use to finish the course. In this problem we just introduce and focus on an alternative basic form: match play.

In match play, two players (or two teams) play each hole as a separate contest against each other. The party with the lower score (number of strokes) wins that hole. If the scores of both parties are equal, the hole is "halved" (drawn). The game is won by the party that wins more holes than the other.

In each hole, the two players usually hit their balls in turn, so the players can feel free to watch how their opponents play. But the order is somewhat different. The player who wins the last hole will play first in this hole, and the other one will play next, except for the first hole where the first player is determined in other ways. If the last hole is halved, the player who plays first in the last hole will play first again. After the first two strokes, the player whose ball is further from the hole will play next. In case the distances from the hole to the two balls are strictly equal, the player who play first in this hole will play next.

To save the players' time, when a player can only lose the hole no matter how well he/she plays according to the current situation, he/she will give up and so the opponent will win the hole. For example, because of the hitting order specified above, sometimes when a player finishes the hole first with four strokes, his/her opponent may already have four or more strokes. The latter will give up this hole then. This also applies to the whole match: when a player is destined to lose the match, the match is deemed to be won by his/her opponent and there's no need to play the remaining holes (if any). For example, if a player already has a lead of six holes, and only five holes remain to be played on the course, the match is over and the player in lead is the winner. Note that when a player cannot win the match but can still make the match end in a tie, he/she will not give up. When the game is tied after the predetermined holes have been played, it may be continued until one player takes a one-hole lead (also known as sudden death).

In this problem, we treat the map of each hole as a two-dimensional plane with the position of tee (where the balls lie before the first hit, we assume that it is fixed for simplicity here) lies in the origin and the unit is yard. With the information of each hole and the displacement vector of each stroke given, your program should print the results of each hole and the whole match. There may be some special cases due to the lie of the ball, and here is a simple list of rules about how to deal with them (the full list is here):

  • When the player think his/her ball is unplayable in its current lie, he can declare that and place a substitute ball around the current lie at a penalty of one stroke.
  • When the ball is hit into a lake or river (water hazard), a substitute ball is dropped within two club lengths of where the ball last crossed the margin of the hazard, at a penalty of one stroke.
  • When a shot lands out of the boundaries of the course (out-of-bounds, or O.B. for short), the player must hit another shot from the position where the ball lies last, at a penalty of one stroke.

Where "at a penalty of one stroke" means the score the player increased by one in addition of any actual stroke. Another special thing is, to save the playing time, when a player's score exceeds a certain limit, he/she will stop hitting and is deemed to finish the hole with one more stroke. Here the limit is the six strokes in addition of the par of the hole (the number of strokes a skilled golfer should require to complete play of the hole). For example, if a player has played 10 strokes in a Par-3 hole while the ball is still outside the hole, he will stop hitting and is deemed to finish the hole with 11 strokes.


Each test case represents a match and begins with a line with a positive integer H, the number of holes in the course (H <= 18). The second line contains H integers Pi, the par of each hole in the course (3 <= Pi <= 5, 1 <= i <= H). The third line cotains 2H real numbers hxi and hyi, the coordinates of each hole (1 <= i <= H). The fourth line contains the names of the two players, and the first player will play first in the first hole. All the following lines represent the actions made by the players in sequence, and each line is of one of the following four formats:

  • "vx vy", indicates the displacement of the ball made by a normal stroke.
  • "Unplayable px py", indicates the player declare the current lie of ball is unplayable, and a substitute ball is placed in (px py).
  • "Water Hazard px py", indicates the player hits the ball into a water hazard, and a subsitute ball is placed in (px py).
  • "O.B.", indicates the player hits the ball ouf of bounds.

The actions end when the match finishes. The players' names contain only letters and the lengths are no more than 31. All real numbers in the input will contain at most two digits after the decimal point. You can assume that the distance between the hole and the tee is between 100 and 690 yards, inclusive. The length of displacement made by any normal stroke is no more than 350 yards. And the substitute balls are always placed according to the above rules.

There's a blank line between every two successive cases. Processing to the end of file.


For each match, first print a line "Match K", where K is the index of this case starts from 1.

For each finished hole, print a a line of the format "WinnerName wins (WinnerScore:LoserScore)" where WinnerName is the name of the winner of the hole, WinnerScore and LoserScore are the scores of the winner and the loser, respectively. If a player gives up a hole, print a line of the format "LoserName gives up (CurrentStrokes:WinnerScore)" instead, where LoserName is the name of the player who gives up, CurrentStrokes is the score of the loser when he/she gives up, and WinnerScore is the score of the winner. If a hole is halved, print a line "Halved (Score)", where Score is the score of both players.

When a match finishes, print a line of the format "WinnerName wins the match", where WinnerName is the name of the winner of the match. If the match is tied after all the holes in the course have been played, just print a line of "Tie", no sudden death is required here. Note you need not print anything for each unfinished hole. (If a player gives up the last played hole, the hole is also finished.)

Print a blank line between every two successive cases.

Sample Input

4 4 3
0.0 369.0 -36.2 327.1 12.0 137.4
Neil Ella
0.0 251.0
-18.7 227.2
24.4 120.5
0.0 118.0
-25.8 233.6
-20.8 187.9
-15.1 136.2
-10.4 99.3
0.0 -5.8
-0.3 3.0
11.8 135.5
24.8 109.2
-8.7 19.1
-4.1 9.1
0.2 1.9

Sample Output

Match 1
Ella gives up (2:2)
Halved (3)
Neil wins (2:3)
Neil wins the match

Author: XIAO, Dong
Submit    Status