2199C.md (1719B)
1 Source: https://codeforces.com/problemset/problem/2199/C 2 3 C. Minesweeper 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You need to construct a field for the game "Minesweeper" consisting of $2$ rows and several columns. Each cell must either be empty or contain a mine. We say that two cells are neighboring if they share a side and/or a corner. 22 23 The field you are constructing must satisfy the following constraints: 24 25 * each empty cell must be neighboring at most one mine; 26 * the number of empty cells that have a neighboring cell with a mine is equal to $k$; 27 * among all suitable fields, the number of columns must be the minimum possible. 28 29 Construct such a field or report that it is impossible. 30 31 Input 32 33 The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. 34 35 Each test case consists of one line containing one integer $k$ ($1 \le k \le 100$) — the required number of empty cells which have a neighboring cell with a mine. 36 37 Output 38 39 For each test case, output the answer as follows: 40 41 * if it is impossible to construct a field that satisfies all constraints, print NO; 42 * otherwise, on the first line print YES, and on the second line print an integer $n$, where $n$ is the minimum number of columns in the field. On the third and fourth lines, print the description of the field itself. The description of each row of the field must consist of $n$ characters, each of which is either a dot "." (empty cell) or an asterisk "*" (mine). If there are multiple suitable fields, output any of them. 43 44 Example 45 46 Input 47 48 ``` 49 5 50 51 1 52 53 4 54 55 8 56 57 10 58 59 9 60 ``` 61 62 Output 63 64 ``` 65 YES 66 1 67 * 68 . 69 NO 70 YES 71 5 72 *.... 73 ...*. 74 YES 75 6 76 .*..*. 77 ...... 78 NO 79 ```