IOI '15 P1 - Boxes with Souvenirs

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type
Allowed languages
C, C++

The last act of the IOI 2015 opening ceremony is in progress. During the opening ceremony, each team was supposed to receive a box with a souvenir from the host. However, all volunteers are so fascinated by the ceremony that they completely forgot about the souvenirs. The only person who remembers about the souvenirs is Aman. He is an enthusiastic volunteer and he wants the IOI to be perfect, so he wants to deliver all the souvenirs in the least amount of time.

The venue of the opening ceremony is a circle divided into L identical sections. The sections around the circle are numbered consecutively from 0 to L-1. That is, for 0 \le i \le L - 2, sections i and i+1 are adjacent, and also sections 0 and L-1 are adjacent. There are N teams at the venue. Each team is sitting in one of the sections. Each section may contain arbitrarily many teams. Some sections may even be empty.

There are N identical souvenirs. Initially, both Aman and all of the souvenirs are in section 0. Aman should give one souvenir to each team, and after delivering the last souvenir he must return to section 0. Note that some teams may be sitting in section 0.

At any moment, Aman can only carry at most K souvenirs. Aman must pick up souvenirs in section 0, and this takes him no time. Each souvenir must be carried until it is delivered to one of the teams. Whenever Aman carries one or more souvenirs and reaches a section with a team that has not received a souvenir yet, he may give that team one of the souvenirs he carries. This also happens instantly. The only thing that takes time is movement. Aman can move around the circular venue in both directions. Moving to an adjacent section (either clockwise or counterclockwise) takes him exactly one second, regardless of how many souvenirs he carries.

Your task is to find the smallest number of seconds Aman needs to deliver all souvenirs and then return to his initial position.

Example

In this example we have N=3 teams, Aman's carrying capacity is K=2, and the number of sections is L=8. The teams are located in sections 1, 2, and 5.

One of the optimal solutions is shown in the picture above. In his first trip Aman takes two souvenirs, delivers one to the team in section 2, then the other to the team in section 5, and finally he returns to section 0. This trip takes 8 seconds. In his second trip Aman brings the remaining souvenir to the team in section 1 and then returns to section 0. He needs another 2 seconds to do this. Thus, the total time is 10 seconds.

Task

You are given N, K, L, and the positions of all teams. Compute the smallest number of seconds Aman needs to deliver all the souvenirs and to return to section 0. You need to implement the function delivery:

long long delivery(int N, int K, int L, int positions[]);
  • This function will be called by the grader exactly once.
  • N: the number of teams.
  • K: the maximum number of souvenirs Aman can carry at the same time.
  • L: the number of sections in the venue of the opening ceremony.
  • positions: an array of length N. positions[0], ..., positions[N-1] give the section number of all teams. The elements of positions are in non-decreasing order.

The function should return the smallest number of seconds in which Aman can complete his task.

Subtasks

subtask points N K L
1 10 1 \le N \le 1\,000 K = 1 1 \le L \le 10^9
2 10 1 \le N \le 1\,000 K = N 1 \le L \le 10^9
3 15 1 \le N \le 10 1 \le K \le N 1 \le L \le 10^9
4 15 1 \le N \le 1\,000 1 \le K \le N 1 \le L \le 10^9
5 20 1 \le N \le 10^6 1 \le K \le 3\,000 1 \le L \le 10^9
6 30 1 \le N \le 10^7 1 \le K \le N 1 \le L \le 10^9

Comments

There are no comments at the moment.