Woburn Challenge 2017-18 Round 1 - Senior Division

Problem 2: Ride the Rocket

A certain TTC bus route involves a sequence of N (2 ≤ N ≤ 10⁹) bus stops, numbered from 1 to N.

Every P (1 ≤ P ≤ 100) minutes, starting at time 0, a new bus will arrive at stop 1. It will wait a brief moment to allow new passengers to board and/or existing passengers to disembark, and then proceed onwards to stop 2, reaching it after another B (1 ≤ B ≤ 100) minutes. There, it will similarly give passengers an opportunity to board/disembark, before continuing onwards and reaching stop 3 after another B minutes, and so on. In this manner, B * (N − 1) minutes after any given bus starts its route, it will arrive at stop N, drop off any remaining passengers, and then go out of service. Note that a new bus drives along the route described above every P minutes, meaning that there may be multiple buses on the road at any time.

Each bus has a maximum capacity of C (1 ≤ C ≤ 10⁵) passengers. If some passengers want to get off a bus while others simultaneously want to get on it, the former can happen first to make room for the new passengers. Note that buses take no extra time to pick up or drop off any number of passengers at a stop.

At time 0, your entire class of M (1 ≤ M ≤ 10⁵) students is waiting at stop 1, the i-th of whom wants to get to stop D_i (2 ≤ D_i ≤ N) as quickly as possible. At any moment, each student not currently on a bus may either wait at their current stop, walk to the next stop along the route in W (1 ≤ W ≤ 100) minutes, or board a bus (if there's a below-capacity bus at their current stop at that moment). Meanwhile, each student currently on a bus may get off the bus if it's currently at a stop.

Each student's "travel time" is the amount of time which goes by (after time 0) before they arrive at their destination stop. You're thinking it would be nice if the sum of all M students' travel times could be as small as possible. As such, you'd like to determine the minimum possible value this sum could have, assuming that all of the students work together to minimize it. Though, on second thought, getting everyone in your class to cooperate might be the more difficult part…

Please note that the answer may not fit into a 32-bit signed integer.

Subtasks

In test cases worth 4/22 of the points, N ≤ 10 and M ≤ 10.
In test cases worth another 11/22 of the points, N ≤ 10⁵ and M ≤ 1000.

Input Format

The first line of input consists of four space-separated integers, N, P, B, and C.
The next line consists of two space-separated integers, M and W.
M lines follow, the i-th of which consists of a single integer, D_i, for i = 1..M.

Output Format

Output a single integer, the minimum possible sum of travel times for all M students to reach their desired stops.

Sample Input 1

2 2 2 1
3 5
2
2
2

Sample Output 1

11

Sample Input 2

10 3 1 2
4 2
4
3
5
4

Sample Output 2

17

Sample Explanation 2

In the first case, one optimal strategy is as follows:

Student 1: Board the first bus immediately, and disembark at stop 2 (2 minutes)
Student 2: Wait for 2 minutes, board the second bus at time 2, and disembark at stop 2 (4 minutes)
Student 3: Walk to stop 2 (5 minutes)

In the second case, one optimal strategy is as follows:

Student 1: Board the first bus immediately, and disembark at stop 4 (3 minutes)
Student 2: Walk all the way to stop 3 (4 minutes)
Student 3: Board the first bus immediately, and disembark at stop 5 (4 minutes)
Student 4: Walk to stop 2, wait for 2 minutes, board the second bus at time 4, and disembark at stop 4 (6 minutes)

All Submissions
Best Solutions

Point Value: 11 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Jan 26, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)