codeforces-scrape

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

1070D.md (1916B)


      1 Source: https://codeforces.com/problemset/problem/1070/D
      2 
      3 D. Garbage Disposal
      4 
      5 time limit per test
      6 
      7 3 seconds
      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 Enough is enough. Too many times it happened that Vasya forgot to dispose of garbage and his apartment stank afterwards. Now he wants to create a garbage disposal plan and stick to it.
     22 
     23 For each of next $n$ days Vasya knows $a_i$ — number of units of garbage he will produce on the $i$-th day. Each unit of garbage must be disposed of either on the day it was produced or on the next day. Vasya disposes of garbage by putting it inside a bag and dropping the bag into a garbage container. Each bag can contain up to $k$ units of garbage. It is allowed to compose and drop multiple bags into a garbage container in a single day.
     24 
     25 Being economical, Vasya wants to use as few bags as possible. You are to compute the minimum number of bags Vasya needs to dispose of all of his garbage for the given $n$ days. No garbage should be left after the $n$-th day.
     26 
     27 Input
     28 
     29 The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 2\cdot10^5, 1 \le k \le 10^9$) — number of days to consider and bag's capacity. The second line contains $n$ space separated integers $a_i$ ($0 \le a_i \le 10^9$) — the number of units of garbage produced on the $i$-th day.
     30 
     31 Output
     32 
     33 Output a single integer — the minimum number of bags Vasya needs to dispose of all garbage. Each unit of garbage should be disposed on the day it was produced or on the next day. No garbage can be left after the $n$-th day. In a day it is allowed to compose and drop multiple bags.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 3 2  
     41 3 2 1
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 3
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 5 1  
     54 1000000000 1000000000 1000000000 1000000000 1000000000
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 5000000000
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 3 2  
     67 1 0 1
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 2
     74 ```
     75 
     76 Input
     77 
     78 ```
     79 4 4  
     80 2 8 4 1
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 4
     87 ```