codeforces-scrape

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

509B.md (1970B)


      1 Source: https://codeforces.com/problemset/problem/509/B
      2 
      3 B. Painting Pebbles
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 There are *n* piles of pebbles on the table, the *i*-th pile contains *a**i* pebbles. Your task is to paint each pebble using one of the *k* given colors so that for each color *c* and any two piles *i* and *j* the difference between the number of pebbles of color *c* in pile *i* and number of pebbles of color *c* in pile *j* is at most one.
     22 
     23 In other words, let's say that *b**i*, *c* is the number of pebbles of color *c* in the *i*-th pile. Then for any 1 ≤ *c* ≤ *k*, 1 ≤ *i*, *j* ≤ *n* the following condition must be satisfied |*b**i*, *c* - *b**j*, *c*| ≤ 1. It isn't necessary to use all *k* colors: if color *c* hasn't been used in pile *i*, then *b**i*, *c* is considered to be zero.
     24 
     25 Input
     26 
     27 The first line of the input contains positive integers *n* and *k* (1 ≤ *n*, *k* ≤ 100), separated by a space — the number of piles and the number of colors respectively.
     28 
     29 The second line contains *n* positive integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 100) denoting number of pebbles in each of the piles.
     30 
     31 Output
     32 
     33 If there is no way to paint the pebbles satisfying the given condition, output "NO" (without quotes) .
     34 
     35 Otherwise in the first line output "YES" (without quotes). Then *n* lines should follow, the *i*-th of them should contain *a**i* space-separated integers. *j*-th (1 ≤ *j* ≤ *a**i*) of these integers should be equal to the color of the *j*-th pebble in the *i*-th pile. If there are several possible answers, you may output any of them.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 4 4  
     43 1 2 3 4
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 YES  
     50 1  
     51 1 4  
     52 1 2 4  
     53 1 2 3 4
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 5 2  
     60 3 2 4 1 3
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 NO
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 5 4  
     73 3 2 4 3 5
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 YES  
     80 1 2 3  
     81 1 3  
     82 1 2 3 4  
     83 1 3 4  
     84 1 1 2 3 4
     85 ```