## DMOPC '14 Contest 8 P5 - Aurora

View as PDF

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The Aurora is an aircraft-carrying aviation submersible.

The Aurora.

soldiers in para-mails (you can think of these as aircraft) are being deployed to one of stations on the main continent. To travel to their respective stations, soldiers may either fly there directly with their para-mail or hitch a ride on the Aurora, which will make one journey from station to station to station … all the way to station . Coincidentally, this is the only route to travel between stations; that is, if a soldier wanted to travel via their own para-mail instead, they would also have to take the same route as the Aurora (because flying too far from the main route is unsafe). For each station from to , it takes exactly seconds to travel to station via para-mail or seconds via the Aurora . Whenever one or more soldiers reach their station and are flying via the Aurora, the Aurora must make a stop to let all soldiers who are deployed at that station get off. The total time the Aurora stops is , where is the number of soldiers that get off at that station. The soldiers get off one by one, so if three soldiers get off, the first soldier waits for seconds, the second soldier waits for seconds, and the last soldier waits for seconds. All soldiers and the Aurora will start at station .

The battle is beginning soon, and it is vital that each soldier arrives at their station as fast as possible. What is the minimum total time for all the soldiers to arrive at their stations?

#### Input Specification

The first line of input will contain and , separated by a single space.
The second line of input will contain , , and , separated from each other by single spaces.
The third line of input will contain integers, the assigned stations of each of the soldiers. They will be integers from to . At least one soldier will be deployed to station .

For all cases, .

#### Output Specification

The first and only line of output should contain the minimum total time for all the soldiers to arrive at their stations.

#### Sample Input 1

5 6
1 2 1
4 5 3 6 2

#### Sample Output 1

21

#### Explanation of Output for Sample Input 1

Soldier 3 and 5 should fly directly to their stations. The rest of the soldiers should use the Aurora. The total time is .

#### Sample Input 2

10 4
1 100000 1
4 3 4 2 3 2 4 3 1 4

#### Sample Output 2

56

• commented on July 24, 2017, 5:52 p.m. edited

If only one soldier gets off at say, station 1, will that cause another soldier going to station 2 to have to wait another C seconds (assuming they both take the Aurora)?

EDIT: I'm stupid. The Aurora will stop for x*c seconds for x soldiers

• commented on April 28, 2017, 11:28 p.m.

Can someone please explain sample input 2 for me, I dont see how 56 is obtained

• commented on April 29, 2017, 2:43 p.m.

Para-mail is too expensive, so all of the soldiers have to hitch a ride on the Aurora.

The total time (from left to right) is:

Note that Soldier #9 is already at the destination, so it takes seconds to get there.

• commented on May 5, 2015, 4:54 p.m.

Lets say a soldier 1 gets off before soldier 2. Will soldier 1's get-off Aurora time affect soldier 2's time?

• commented on May 5, 2015, 5:02 p.m.

Assuming they both take the Aurora, yes.

• commented on May 5, 2015, 4:38 p.m.

If soldiers 3 and 5 go to their stations, (22 = 4 minutes for soldier 3, and 12 = 2 minutes for soldier 5), where does the other numbers come from?

• commented on May 5, 2015, 4:40 p.m.

The other soldiers board the Aurora. Their time is calculated as described in the problem statement.

• commented on May 5, 2015, 4:48 p.m.

Why let the two soldiers go by themselves? Isn't it better just to take all the soldiers on the aurora? To get from 1 to 6, it is 5 minutes, and then each soldiers leaves, so 5 minutes. This would be 10 minutes no?

• commented on May 5, 2015, 5:03 p.m.

The waiting time of soldiers increases if other soldiers get off before them.

• commented on May 5, 2015, 4:28 p.m.

If soldiers 1-4 took the aurora, then why does soldier 3 take more time than soldier 1 if she is getting off at station 3 compared to 4?

• commented on May 5, 2015, 4:32 p.m.

Sorry, soldiers 3 and 5 (in input order) should be the ones flying.

• commented on May 5, 2015, 5:16 p.m.

Oh, that makes sense. I just spent a long time trying to figure that out. I guess that's what I get for not refreshing the page...

• commented on May 5, 2015, 4:13 p.m. edited

Is there some restriction on when/how the soldiers can fly themselves in? Reading the problem, I thought that the soldiers could all para-mail in in tandem (and independent of the Aurora), but that definitely doesn't make sense in the context of the sample input.

• commented on May 5, 2015, 4:29 p.m. edit 5

Your thought is correct (as far as I understand it). Which part of the sample input is unclear? I'll try to explain it.

EDIT: The explanation has been updated. I change the sample a bit, but forgot to change the explanation. Sorry!

• commented on May 5, 2015, 4:42 p.m.

I'm still in the dark a little, sorry...

If all the soldiers can just para-mail in without regard to each other or the Aurora, could they not all reach their stations within 10 units (in sample input 1)? Since B = 2, M = 6.