PGAME - Pheversos Game

no tags 

Pheverso's Game

Matheus Pheverso is a well-known rogue, as everyone knows he used to be very mean with the couple in love, Danilo Ghyei and Raphael Boboleta. But now he's trying to change into being a better person. In order to do that, he will call some friends over to play his newest game and throw a game party next year.

The game “Pheverso's Game” is played in rounds by two contestants in which each one must pick one cell from a MxN board, add its number to the group's total score and then throw it away. Also, in order to avoid cheating, each cell is previously chosen and no one is allowed to choose a cell if it isn't at the beginning or at the end of some row. You also have to notice that when one cell is dropped, the row from where the cell has been taken gets a new configuration, resulting in a new beginning or a new end.

Pheverso was playing that game with some friends and realized it's way too easy, so he decided to choose some rows and block their beginnings. When a row is blocked, a group is only able to choose a cell from the end of this row.

The goal of the game for each contestant is to hoard as much as they can, so the winner of the game is the one who holds the maximum amount of points in the end of the game. The game finishes when there are no remaining cells.

Assuming that they both plays optimally and given the N, M dimensions, the initial state of the board, the rows that are blocked, which player wins the game and what's the score of the winner.

Input

The input contains several test cases. A test case begins with a line containing integers N (1 ≤ N ≤ 1000), M (1 ≤ M ≤ 1000) and K (0 ≤ K < N), where N, M stands for the board dimensions and K for the total number of rows blocked. On the second line there are K integers, the rows that are blocked. Then follow N lines, each containing M integers representing the initial state of the board.

Every number in the board is a 32 bit signed integer. The last test case is followed by a line containing three zeros.

Output

For each test case, print a line containing “first” (without the quotes) if the first player will win the game or “second” (without the quotes) if the second player will win the game, followed by an integer representing the amount achieved by the winner when both of them plays optimally. The game always has a winner.

Example

Input
2 2 2
1 2
500 10
3 10
3 3 2
1 3
0 1 2
3 7 4
0 0 9
0 0 0

Output
second 503
first 17

Explanation:

First Case – At first the two rows are blocked, so both players aren't able to choose either cell A[1][1] = 500 or A[2][1] = 3. Thus, the first player isn't able to grab the cell A[1][2] either, cause he would unlock to his opponent the greatest piece in the board, A[1][1] = 500. So he choose the cell A[2][2] = 10. Afterward his opponent grabs the cell A[2][1] = 3, force the first player to choose A[1][2] and set free the greatest piece in the board, therefore the second player is the winner achieving 503 total points (A[1][1] + A[2][1]) against 20 from the first player.

Second Case – The game is as follows:

  • First player: 9
  • Second player: 2
  • First player: 1
  • Second player: 3
  • First player: 7
  • Second player: 4
  • First player: 17 (Winner)
  • Second player: 9

Remember, both contestants plays optimally.


hide comments
Oleg: 2023-12-21 09:21:15

my assertation catches case where blocked row is not from [1..N] range. if I ignore these blocks, solution passes.

Anyway... Nice one!

Last edit: 2023-12-21 09:21:45
[Rampage] Blue.Mary: 2023-08-24 10:22:47

This is not a NP-Hard Problem. You should consider more.

Ishan: 2022-12-30 03:47:08

This seems to be a NP-Hard Problem as any min max tree problems are. Is the expected solution some pseudo polynomial approximation algorithm.

Last edit: 2022-12-30 03:49:42

Added by:Mateus Dantas [ UFCG ]
Date:2013-02-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64