codeforces-scrape

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

1327C.md (2345B)


      1 Source: https://codeforces.com/problemset/problem/1327/C
      2 
      3 C. Game with Chips
      4 
      5 time limit per test
      6 
      7 1 second
      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 Petya has a rectangular Board of size $n \times m$. Initially, $k$ chips are placed on the board, $i$-th chip is located in the cell at the intersection of $sx_i$-th row and $sy_i$-th column.
     22 
     23 In one action, Petya can move all the chips to the left, right, down or up by $1$ cell.
     24 
     25 If the chip was in the $(x, y)$ cell, then after the operation:
     26 
     27 * left, its coordinates will be $(x, y - 1)$;
     28 * right, its coordinates will be $(x, y + 1)$;
     29 * down, its coordinates will be $(x + 1, y)$;
     30 * up, its coordinates will be $(x - 1, y)$.
     31 
     32 If the chip is located by the wall of the board, and the action chosen by Petya moves it towards the wall, then the chip remains in its current position.
     33 
     34 Note that several chips can be located in the same cell.
     35 
     36 For each chip, Petya chose the position which it should visit. Note that it's not necessary for a chip to end up in this position.
     37 
     38 Since Petya does not have a lot of free time, he is ready to do no more than $2nm$ actions.
     39 
     40 You have to find out what actions Petya should do so that each chip visits the position that Petya selected for it at least once. Or determine that it is not possible to do this in $2nm$ actions.
     41 
     42 Input
     43 
     44 The first line contains three integers $n, m, k$ ($1 \le n, m, k \le 200$) — the number of rows and columns of the board and the number of chips, respectively.
     45 
     46 The next $k$ lines contains two integers each $sx_i, sy_i$ ($ 1 \le sx_i \le n, 1 \le sy_i \le m$) — the starting position of the $i$-th chip.
     47 
     48 The next $k$ lines contains two integers each $fx_i, fy_i$ ($ 1 \le fx_i \le n, 1 \le fy_i \le m$) — the position that the $i$-chip should visit at least once.
     49 
     50 Output
     51 
     52 In the first line print the number of operations so that each chip visits the position that Petya selected for it at least once.
     53 
     54 In the second line output the sequence of operations. To indicate operations left, right, down, and up, use the characters $L, R, D, U$ respectively.
     55 
     56 If the required sequence does not exist, print -1 in the single line.
     57 
     58 Examples
     59 
     60 Input
     61 
     62 ```
     63 3 3 2
     64 1 2
     65 2 1
     66 3 3
     67 3 2
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 3
     74 DRD
     75 ```
     76 
     77 Input
     78 
     79 ```
     80 5 4 3
     81 3 4
     82 3 1
     83 3 3
     84 5 3
     85 1 3
     86 1 4
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 9
     93 DDLUUUURR
     94 ```