732B.md (2479B)
1 Source: https://codeforces.com/problemset/problem/732/B 2 3 B. Cormen — The Best Friend Of a Man 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 Recently a dog was bought for Polycarp. The dog's name is Cormen. Now Polycarp has a lot of troubles. For example, Cormen likes going for a walk. 22 23 Empirically Polycarp learned that the dog needs at least *k* walks for any two consecutive days in order to feel good. For example, if *k* = 5 and yesterday Polycarp went for a walk with Cormen 2 times, today he has to go for a walk at least 3 times. 24 25 Polycarp analysed all his affairs over the next *n* days and made a sequence of *n* integers *a*1, *a*2, ..., *a**n*, where *a**i* is the number of times Polycarp will walk with the dog on the *i*-th day while doing all his affairs (for example, he has to go to a shop, throw out the trash, etc.). 26 27 Help Polycarp determine the minimum number of walks he needs to do additionaly in the next *n* days so that Cormen will feel good during all the *n* days. You can assume that on the day before the first day and on the day after the *n*-th day Polycarp will go for a walk with Cormen exactly *k* times. 28 29 Write a program that will find the minumum number of additional walks and the appropriate schedule — the sequence of integers *b*1, *b*2, ..., *b**n* (*b**i* ≥ *a**i*), where *b**i* means the total number of walks with the dog on the *i*-th day. 30 31 Input 32 33 The first line contains two integers *n* and *k* (1 ≤ *n*, *k* ≤ 500) — the number of days and the minimum number of walks with Cormen for any two consecutive days. 34 35 The second line contains integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 500) — the number of walks with Cormen on the *i*-th day which Polycarp has already planned. 36 37 Output 38 39 In the first line print the smallest number of additional walks that Polycarp should do during the next *n* days so that Cormen will feel good during all days. 40 41 In the second line print *n* integers *b*1, *b*2, ..., *b**n*, where *b**i* — the total number of walks on the *i*-th day according to the found solutions (*a**i* ≤ *b**i* for all *i* from 1 to *n*). If there are multiple solutions, print any of them. 42 43 Examples 44 45 Input 46 47 ``` 48 3 5 49 2 0 1 50 ``` 51 52 Output 53 54 ``` 55 4 56 2 3 2 57 ``` 58 59 Input 60 61 ``` 62 3 1 63 0 0 0 64 ``` 65 66 Output 67 68 ``` 69 1 70 0 1 0 71 ``` 72 73 Input 74 75 ``` 76 4 6 77 2 4 3 5 78 ``` 79 80 Output 81 82 ``` 83 0 84 2 4 3 5 85 ```