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