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?
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 a single integer, the minimum total cost of stagehand tips required, in dollars.
6 3 4 5 3 2 2 1 2
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.
Point Value: 8 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 18, 2019
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3