codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```