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:

1. Jar Jar Binks leads the Gungan army in a diversionary battle against the Trade Federation's droid army on the plains of Naboo.
2. Queen Amidala and her security force storm the palace in Theed in an attempt to locate and arrest Viceroy Nute Gunray.
3. Obi-Wan Kenobi and Qui-Gon Jinn have a lightsaber duel against the Sith lord Darth Maul.
4. 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 S_i (0 ≤ S_i ≤ 4). If S_i = 0, then the scene is currently unassigned, and if S_i > 0, then the scene must observe setting S_i.

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).

Input Format

The first line of input consists of a single integer N.
The second line consists of N space-separated integers S₁ to S_N.

Output Format

Output on a single line the numeric representation of your finalized scenes.

Sample Input

8
0 4 1 0 0 1 3 0

Sample Output

14123131

All Submissions
Best Solutions

Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 12, 2015
Author: SourSpinach

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

Comments (Search)

During the contest, I couldn't ask for clarification because I had to solve "A + B".

... my bad. I could have sworn I tested that.

Will be fixed for next contest.