루미 알고리즘

#1305플래티넘Grid Volleyball

PO 2012 결선코딩영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Grid Volleyball is played with two players in each team (like beach volleyball) but the players can only hit the ball when standing on a grid point. When a player is to hit the ball, they must be “close enough” to where the ball is supposed to land, move there, and then hit it. Only the player who is going to hit the ball is allowed to move. The player decides on a grid point to which they will hit the ball, either on their own side of the net (a “pass”) or on the opposing team's (a “smash”). The ball always lands on that grid point and can not be intercepted on the way. If there is no player who can move to the grid point to where it was aimed, the team on whose side the ball lands loses. As in beach volleyball, the ball may be hit at most three times before crossing the net (two passes and a smash) and the same person may not hit the ball twice in a row. The first hit (the serve) must always be made from one of the corners of the field and be a smash. It's decided that the first player (A1) of team A serves.

Write a program that, given the size of the playing field and the four players' properties, computes which team wins if playing optimally. If no team can force a win, the ball will be live forever which we consider a tie.

The net is transparent, so the players know where the opponents are before hitting (but remember a player may not move unless it's to hit the ball). The game starts in the following way. First team A assumes their positions: A1 in a corner and A2 on an arbitrary position. Afterwards, B1 and B2 assumes arbitrary positions, while A may not move. Finally, A serves and the game is afoot. The players move independently of each other, and may be on the same grid point. However, they may not step outside of the field or into the opponent's half of the field.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: A possible game sequence of example 4, with optimal play from both teams, i.e. team A plays in such a way that they have a forced win with at most 5 smashes in total while team B players in such a way that team A can't win after less than 5 smashes. There are several other optimal ways to play. To the left the field is shown with the grid points marked by crosses and the two possible serve points with squares around the crosses. Also, an optimal starting position is displayed for the teams. Furthermore the path of the ball is showed with red arrows, while the players' movements are showed with blue arrows. For clarity, the play has been split into two pictures so that the left one shows the play up to and including the third smash, while the right figure shows the remainder of the game, including A hitting the final smash that no player of team B can catch.

Input

The first line contains the integers x (2 ≤ X ≤ 4) and y (2 ≤ Y ≤ 3), the number of grid points on the x- and y-axis on each half of the field (see the figure).

Then four lines follow describing the players in the order A1, A2, B1 and B2. Each line consists of two integers F (0 ≤ F ≤ 25) and S (0 ≤ S ≤ 5), where √F is the greatest distance a player can hit the ball and √S is the maximum distance the player can run to make a hit, i.e. the maximum distance the player can be from where the ball will land to reach it on time.

Output

First output the result for team A: win, loss or tie. If team A wins, output the minimum number of smashes (for both teams) that team A needs before it can win (this will be odd). If team A loses, instead output the minimum number of smashes (for both teams) that team B needs before it can win (this will be even). For a tie, no number should be output.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

Note: if your program only computes the result correctly but outputs an incorrect number of smashes you will receive 30 points for a group.

GroupPoint valueConstraints
150One of the teams has a forced win.
250No additional constraints.

예제

예제 1

입력
2 2
8 0
3 0
1 0
2 0
출력
loss
2

예제 2

입력
3 2
10 1
6 2
7 1
5 1
출력
tie

예제 3

입력
3 2
8 5
10 2
7 1
5 1
출력
loss
0

예제 4

입력
4 3
20 1
15 2
15 1
15 1
출력
win
5

출처 표기

출처: Programmeringsolympiaden 2012년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.