codeforces-scrape

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

980B.md (1644B)


      1 Source: https://codeforces.com/problemset/problem/980/B
      2 
      3 B. Marlin
      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 The city of Fishtopia can be imagined as a grid of $4$ rows and an odd number of columns. It has two main villages; the first is located at the top-left cell $(1,1)$, people who stay there love fishing at the Tuna pond at the bottom-right cell $(4, n)$. The second village is located at $(4, 1)$ and its people love the Salmon pond at $(1, n)$.
     22 
     23 The mayor of Fishtopia wants to place $k$ hotels in the city, each one occupying one cell. To allow people to enter the city from anywhere, hotels should not be placed on the border cells.
     24 
     25 A person can move from one cell to another if those cells are not occupied by hotels and share a side.
     26 
     27 Can you help the mayor place the hotels in a way such that there are equal number of shortest paths from each village to its preferred pond?
     28 
     29 Input
     30 
     31 The first line of input contain two integers, $n$ and $k$ ($3 \leq n \leq 99$, $0 \leq k \leq 2\times(n-2)$), $n$ is odd, the width of the city, and the number of hotels to be placed, respectively.
     32 
     33 Output
     34 
     35 Print "YES", if it is possible to place all the hotels in a way that satisfies the problem statement, otherwise print "NO".
     36 
     37 If it is possible, print an extra $4$ lines that describe the city, each line should have $n$ characters, each of which is "#" if that cell has a hotel on it, or "." if not.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 7 2
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 YES  
     51 .......  
     52 .#.....  
     53 .#.....  
     54 .......
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 5 3
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 YES  
     67 .....  
     68 .###.  
     69 .....  
     70 .....
     71 ```