codeforces-scrape

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

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