Woburn Challenge 2015-16 Round 2 - Senior Division
Problem I: The Phantom Menace
“There is no doubt. The mysterious coder was a Sith.”
“Always two there are, no more, no less. A master and a n00b.”
“But which was destroyed, the master or the n00b?”
The exciting climax of the highly-anticipated 1999 Star Wars prequel features four distinct action sequences occurring simultaneously:
- Jar Jar Binks leads the Gungan army in a diversionary battle against the Trade Federation's droid army on the plains of Naboo.
- Queen Amidala and her security force storm the palace in Theed in an attempt to locate and arrest Viceroy Nute Gunray.
- Obi-Wan Kenobi and Qui-Gon Jinn have a lightsaber duel against the Sith lord Darth Maul.
- Anakin Skywalker pilots a Naboo starfighter into orbit amidst a massive dogfight, attempting to take out the Trade Federation's droid control ship.
During this time, the film needs to cut back and forth between these settings. In particular, there are N (1 ≤ N ≤ 10,000) scenes to fill, with each scene observing one of the 4 settings. Additionally, no two consecutive scenes may be assigned to the same setting.
Some of the scenes have already been assigned to settings, while others haven't been. The status of the i-th scene is indicated by the value of Si (0 ≤ Si ≤ 4). If Si = 0, then the scene is currently unassigned, and if Si > 0, then the scene must observe setting Si.
Your job is to assign each of the unassigned scenes to one of the 4 settings, such that no two consecutive scenes are assigned to the same one. It's guaranteed that this will be possible. However, it may be possible in multiple ways, in which case you must choose the one that minimizes the "numeric representation" of the scenes. The numeric representation consists of concatenating the values of the N scenes' assigned settings, in order from 1 to N, and treating the result as an integer (with each digit in the range 1..4).
The first line of input consists of a single integer N.
The second line consists of N space-separated integers S1 to SN.
Output on a single line the numeric representation of your finalized scenes.
8 0 4 1 0 0 1 3 0
Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 12, 2015
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3