Woburn Challenge 2018-19 Finals Round - Senior Division

Problem 1: Behind the Scenes

The cows and monkeys of Scarberia, their long-standing conflicts well behind them at last, have banded together to produce a historical drama documenting their past battles. With the Head Monkey as writer and producer, and the director's chair occupied by the cows' leader, Bo Vine, this will be a collaborative masterpiece to remember!

Today, a full day of filming is set to take place at the monkeys' and cows' joint studios. The studios feature three sound stages, numbered from 1 to 3, and there are initially Ei (0 ≤ Ei ≤ 1000) pieces of filmmaking equipment on stage i.

A sequence of N (1 ≤ N ≤ 1000) shots will be filmed, one after another, with the i-th one taking place on stage Si (1 ≤ Si ≤ 3). Whenever a shot is filmed on a certain stage, there must be no equipment present on that stage at the time. Right before each shot, Bo Vine may choose 0 or more pieces of equipment to be moved. Each such piece will be moved from its current stage to a different stage of Bo's choice, at the cost of tipping a stagehand $1, and will remain there until potentially moved again later.

What's the minimum total cost of stagehand tips which Bo Vine will need to dispense such that each of the N shots will have no equipment present on its stage at filming time?

Input Format

The first line of input consists of three space-separated integers, E1, E2, and E3.
The next line consists of a single integer, N.
N lines follow, the i-th of which consists of a single integer, Si, for i = 1..N.

Output Format

Output a single integer, the minimum total cost of stagehand tips required, in dollars.

Sample Input

6 3 4
5
3
2
2
1
2

Sample Output

17

Sample Explanation

One possible optimal strategy for Bo Vine is as follows:

  • Before the 1st shot, move all 4 pieces of equipment from stage 3 to stage 2.
  • Before the 2nd shot, move all 6 pieces of equipment from stage 1 to stage 3, and all 7 pieces of equipment from stage 2 to stage 3.

This requires $4 + $6 + $7 = $17 in stagehand tips.

All Submissions
Best Solutions


Point Value: 8 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 18, 2019
Author: SourSpinach

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

Comments (Search)

It's quiet in here...