{"problem":{"name":"E. Minesweeper","description":{"content":"Have you ever played Minesweeper? It’s a cute little game that originates from the 1960s, and has been written for many computing platforms in use today. The game consists of a two dimensional grid, ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":15000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10191E"},"statements":[{"statement_type":"Markdown","content":"Have you ever played Minesweeper? It’s a cute little game that originates from the 1960s, and has been written for many computing platforms in use today.\n\nThe game consists of a two dimensional grid, and there are two types of cells in it.\n\nA mined cell, and an empty cell, which contains a single digit that indicates how many adjacent cells contain mines. Eech cell has at most 8 adjacent cells. \n\nIn this version of the game, you are going to build a level with the following rules: \n\n \n\nFor instance, the following is 4 * 5 valid grid with 12 mines (which are represented by an '*' character) and the maximum number for the empty cells is M = 3 :\n\n* * * * 2\n\n* * * * 2\n\n3 * * 3 1 \n\nWe are interested in the maximum number of mines that a grid with those properties can contain, can you find the answer for us?\n\nThe first line contains a single integer T denoting the number of test cases.\n\nEach test case consists of one line which contains three space separated integers:\n\nThe number of the rows in the grid r. (2 ≤ r ≤ 6).\n\nThe number of the columns in the grid c. (2 ≤ c ≤ 6).\n\nThe maximum number that any empty cell can contain. (1 ≤ M ≤ 8).\n\nFor each test print one line containing one integer, the maximum number of mines that a grid can contain.\n\nThe grid in the statement is a valid grid for the first sample.\n\n## Input\n\nThe first line contains a single integer T denoting the number of test cases.Each test case consists of one line which contains three space separated integers:The number of the rows in the grid r. (2 ≤ r ≤ 6).The number of the columns in the grid c. (2 ≤ c ≤ 6).The maximum number that any empty cell can contain. (1 ≤ M ≤ 8).\n\n## Output\n\nFor each test print one line containing one integer, the maximum number of mines that a grid can contain.\n\n[samples]\n\n## Note\n\nThe grid in the statement is a valid grid for the first sample.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ A \\in [0, 359] \\cap \\mathbb{Z} $ be the rotation angle (in degrees).  \nLet $ W, H \\in \\mathbb{Z}^+ $, $ W, H \\leq 10^9 $, be the width and height of the window.  \nLet $ N \\in \\mathbb{Z} $, $ 3 \\leq N \\leq 10^5 $, be the number of vertices.  \nLet $ P = \\{(x_i, y_i) \\in \\mathbb{Z}^2 \\mid 0 \\leq x_i, y_i \\leq 10^9, i \\in \\{1, \\dots, N\\} \\} $ be the input polygon.\n\n**Transformations**  \n1. **Rotation**: Rotate each point $ (x_i, y_i) $ counterclockwise by angle $ A $ degrees:  \n   $$\n   (x_i', y_i') = \\left( x_i \\cos \\theta - y_i \\sin \\theta,\\ x_i \\sin \\theta + y_i \\cos \\theta \\right), \\quad \\theta = \\frac{A \\pi}{180}\n   $$\n\n2. **Scaling and Translation**:  \n   Let $ x_{\\min} = \\min_i x_i' $, $ x_{\\max} = \\max_i x_i' $,  \n   $ y_{\\min} = \\min_i y_i' $, $ y_{\\max} = \\max_i y_i' $.  \n   Scale and translate to fit the window:  \n   $$\n   \\hat{x}_i = W \\cdot \\frac{x_i' - x_{\\min}}{x_{\\max} - x_{\\min}}, \\quad\n   \\hat{y}_i = H \\cdot \\frac{y_i' - y_{\\min}}{y_{\\max} - y_{\\min}}\n   $$\n\n**Objective**  \nOutput the transformed points $ (\\hat{x}_i, \\hat{y}_i) $ for $ i = 1, \\dots, N $, with absolute or relative error $ \\leq 10^{-6} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10191E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}