{"problem":{"name":"G. Game \"Minesweeper\"","description":{"content":"This is interactive problem. Rules of the Minesweeper game are simple: given a grid 16 × 16. Each cell in the grid either is empty or contains a mine. Goal of the game is to label all mines with the ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10091G"},"statements":[{"statement_type":"Markdown","content":"This is interactive problem.\n\nRules of the Minesweeper game are simple: given a grid 16 × 16. Each cell in the grid either is empty or contains a mine. Goal of the game is to label all mines with the flags and open all empty cells. If player opens empty cell, it contains one integer — number of mines in neighbor cells. Two cells are neighbors, if their borders have at least one common point (so each internal cell have 8 neighbors). If a cell, containing an integer 0 is opened (by player or automatically), all neighbors of this cell are opened automatically.\n\nPlayer can do the following operations:\n\nIf after the end of game all empty cells are opened and all cells with mines are labeled, player wins, otherwise game is lost.\n\nYou are given coordinates of cell, which does not contain a mine. Moreover, it's guaranteed that it's possible to win the game without any nondeterministic situation (where guessing is needed). Your goal is to win.\n\nAt the beginning of interaction your program must read two integers — row r and column c of the safe cell (1 ≤ r, c ≤ 16). \n\nThen on each your request you receive next information: \n\nFirst line of the answer contains one integer N — number of cells with changed status. Each of next N lines contain two integers ri and ci — row and column of the cell, and si — status of the cell: digit between 0 and 8, if the cell is empty, '_*_', if the cell was labeled or '_-_', if label from cell was removed. \n\nIf you want to finish the game, print (\"_4_\") and end of the line. Otherwise print three space-separated integers: type of operation, row and column (1-based) of the cell to which it is applied. Do not forget to add end of the line character and flush the output buffer.\n\nSample in the statement contains example of the interaction protocol for board 3 × 3.\n\n## Input\n\nAt the beginning of interaction your program must read two integers — row r and column c of the safe cell (1 ≤ r, c ≤ 16). Then on each your request you receive next information: First line of the answer contains one integer N — number of cells with changed status. Each of next N lines contain two integers ri and ci — row and column of the cell, and si — status of the cell: digit between 0 and 8, if the cell is empty, '_*_', if the cell was labeled or '_-_', if label from cell was removed. \n\n## Output\n\nIf you want to finish the game, print (\"_4_\") and end of the line. Otherwise print three space-separated integers: type of operation, row and column (1-based) of the cell to which it is applied. Do not forget to add end of the line character and flush the output buffer.\n\n[samples]\n\n## Note\n\nSample in the statement contains example of the interaction protocol for board 3 × 3.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G $ be a $ 16 \\times 16 $ grid. Each cell $ (i,j) \\in \\{1,\\dots,16\\}^2 $ has state $ s_{i,j} \\in \\{0,1,2,3,4,5,6,7,8, \\text{mine}, \\text{flag}, \\text{hidden}\\} $.  \nLet $ M \\subseteq \\{1,\\dots,16\\}^2 $ be the set of mine locations (unknown initially).  \nLet $ S \\subseteq \\{1,\\dots,16\\}^2 $ be the set of safe (non-mine) cells.  \n\n**Given**  \nA safe cell $ (r_0, c_0) \\in S $ is revealed initially: $ s_{r_0,c_0} = n_0 \\in \\{0,1,\\dots,8\\} $.  \nIt is guaranteed that the board is solvable deterministically (no guesses required).  \n\n**Constraints**  \n1. Each cell has up to 8 neighbors (Moore neighborhood).  \n2. Opening a cell with value 0 triggers automatic opening of all its neighbors.  \n3. Operations:  \n   - Type 1: Open cell $ (r,c) $ — only allowed if $ s_{r,c} = \\text{hidden} $ and $ (r,c) \\notin M $.  \n   - Type 2: Toggle flag on cell $ (r,c) $ — only allowed if $ s_{r,c} = \\text{hidden} $.  \n4. Game ends when all non-mine cells are opened and all mine cells are flagged.  \n\n**Objective**  \nDetermine a sequence of operations (open or flag) such that:  \n- All cells in $ S $ are opened (state becomes digit $ \\in \\{0,\\dots,8\\} $),  \n- All cells in $ M $ are flagged,  \n- No cell is opened that contains a mine.  \n\n**Interaction Protocol**  \n- Read initial safe cell $ (r_0, c_0) $.  \n- For each query:  \n  - Output: `1 r c` (open) or `2 r c` (toggle flag).  \n  - Receive:  \n    - Integer $ N $: number of state-changed cells.  \n    - $ N $ lines: $ r_i, c_i, s_i $, where $ s_i \\in \\{0,\\dots,8, \\text{'*'}, \\text{'-'}\\} $.  \n- To finish: output `4`.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10091G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}