21 Rolls of Gimbap
InterviewTime limit1sMemory limit128 MB
Simulate a Connect Four style game on a 6x7 board from 21 alternating moves and report who first got four in a row and on which of their throws.
- Level
Medium5 of 10
- Topics
- Simulation, Matrix, Implementation
- Solved
- No attempts yet
Problem
Sanggeun and Jeongin play a game by throwing gimbap onto a board with 6 rows and 7 columns. They alternate turns, and Sanggeun always throws first. Sanggeun uses tuna gimbap, and Jeongin uses kimchi gimbap.
A gimbap roll enters an empty cell in the chosen column, then immediately falls until there is no empty cell below it in that column. Both players are skilled enough that one roll never covers two or more cells, always occupies exactly one cell, and is never thrown into a full column.
A player wins when four of that player's rolls become consecutive horizontally, vertically, or diagonally. However, the players kept throwing all remaining rolls even after the winner was decided, and Changyoung recorded the columns hit on every turn.
Given the record, determine who first made four consecutive rolls and on which numbered roll by that player the win was first decided. There may be no winner.
Input
The input consists of 21 lines. The i-th line contains two integers Si and Ji. Si is the column number hit by Sanggeun's i-th roll, and Ji is the column number hit by Jeongin's i-th roll.
Columns are numbered from 1 to 7 from left to right.
Output
If Sanggeun wins, output sk M. If Jeongin wins, output ji M. Here, M is the number of the winning player's roll on which the win was first decided.
If four consecutive rolls are never formed, output ss.