codeforces-scrape

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

472B.md (2182B)


      1 Source: https://codeforces.com/problemset/problem/472/B
      2 
      3 B. Design Tutorial: Learn from Life
      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 One way to create a task is to learn from life. You can choose some experience in real life, formalize it and then you will get a new task.
     22 
     23 Let's think about a scene in real life: there are lots of people waiting in front of the elevator, each person wants to go to a certain floor. We can formalize it in the following way. We have *n* people standing on the first floor, the *i*-th person wants to go to the *f**i*-th floor. Unfortunately, there is only one elevator and its capacity equal to *k* (that is at most *k* people can use it simultaneously). Initially the elevator is located on the first floor. The elevator needs |*a* - *b*| seconds to move from the *a*-th floor to the *b*-th floor (we don't count the time the people need to get on and off the elevator).
     24 
     25 What is the minimal number of seconds that is needed to transport all the people to the corresponding floors and then return the elevator to the first floor?
     26 
     27 Input
     28 
     29 The first line contains two integers *n* and *k* (1 ≤ *n*, *k* ≤ 2000) — the number of people and the maximal capacity of the elevator.
     30 
     31 The next line contains *n* integers: *f*1, *f*2, ..., *f**n* (2 ≤ *f**i* ≤ 2000), where *f**i* denotes the target floor of the *i*-th person.
     32 
     33 Output
     34 
     35 Output a single integer — the minimal time needed to achieve the goal.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3 2  
     43 2 3 4
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 8
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 4 2  
     56 50 100 50 100
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 296
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 10 3  
     69 2 2 2 2 2 2 2 2 2 2
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 8
     76 ```
     77 
     78 Note
     79 
     80 In first sample, an optimal solution is:
     81 
     82 1. The elevator takes up person #1 and person #2.
     83 2. It goes to the 2nd floor.
     84 3. Both people go out of the elevator.
     85 4. The elevator goes back to the 1st floor.
     86 5. Then the elevator takes up person #3.
     87 6. And it goes to the 2nd floor.
     88 7. It picks up person #2.
     89 8. Then it goes to the 3rd floor.
     90 9. Person #2 goes out.
     91 10. Then it goes to the 4th floor, where person #3 goes out.
     92 11. The elevator goes back to the 1st floor.