codeforces-scrape

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

2155B.md (2811B)


      1 Source: https://codeforces.com/problemset/problem/2155/B
      2 
      3 B. Abraham's Great Escape
      4 
      5 time limit per test
      6 
      7 1.5 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Abraham is a brave explorer who goes where no other programmer has gone before. For his next expedition, he plans to investigate a peculiar maze. He knows that the maze is an $n \times n$ grid with an arrow in each cell that points in one of four directions: up, down, left and right. Abraham also knows that if he stands on an arrow, he will be forced to follow the arrows starting from that cell. Each arrow moves Abraham exactly $1$ cell in the direction that it is pointing. If he reaches an arrow that points towards the outside of the maze, Abraham will escape the maze.
     22 
     23 Abraham doesn't know how the arrows are arranged, so he wants to plan for multiple scenarios. He tasks you with finding an arrangement of arrows in the grid such that there are exactly $k$ starting cells from which he can escape the maze.
     24 
     25 Input
     26 
     27 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.
     28 
     29 The only line of each test case contains two integers $n$, $k$ ($2 \le n \le 100$, $0 \le k \le n^2$) — the size of the grid and the number of cells from which Abraham should be able to escape.
     30 
     31 It is guaranteed that the sum of $n^2$ over all test cases does not exceed $10^5$.
     32 
     33 Output
     34 
     35 For each test case, do one of the following:
     36 
     37 * If there exists a grid satisfying the requirement, print YES and then print $n$ lines with $n$ characters in each line indicating the direction of the arrows. Each character should be one of U (up), R (right), L (left), or D (down).
     38 * Otherwise, declare that the task is impossible by printing NO.
     39 
     40 If there are multiple solutions, print any of them.
     41 
     42 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 3
     50 
     51 2 4
     52 
     53 3 5
     54 
     55 2 3
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 YES
     62 UU
     63 UU
     64 YES
     65 UUU
     66 RDR
     67 ULR
     68 NO
     69 ```
     70 
     71 Note
     72 
     73 In the first test case, no matter which cell Abraham stands in initially, he will eventually exit the maze as he will move upward successively; thus, he can escape from all $4$ cells, as required.
     74 
     75 In the second test case, Abraham eventually escapes if he stands on one of the following:
     76 
     77 * Any cell in the first row (all of which are U)
     78 * Any cell in the third column (one of which is U and the other two R)
     79 
     80 There is no other cell where he can stand and escape. We see that Abraham can escape from exactly $5$ cells in this arrangement, as required.
     81 
     82 In the third test case, it can be proved that there's no arrangement of arrows so that Abraham can escape from exactly $3$ cells.