MWC '15 #8 P3: Draw Down

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

atarw

Problem type

One of Hypnova's favourite pastimes is to play a card game named Draw Down. In this game, each card is decorated with one of three colours, with each colour denoted by integers 1, 2 and 3. $N$ ~N~ $(1 \le N \le 10^5)$ ~(1 \le N \le 10^5)~ players are lined up (not including Hypnova), waiting to receive a card at the front of the line.

The card distribution is dictated as follows: the person at the front of the line will either be given a card of random colour for all to see, or will be secretly given a card of unknown card colour.

However, Hypnova has been playing this game for a while and knows that the card given out secretly will have the colour which has been given out the least to players in line so far. If there is a tie for which card colour has been given out least, the player could receive any of those colours.

For example, if the first two players in line both receive a random card of colour 1, the next player who receives a card secretly could receive a card of colour 2 or 3, as zero players have been given a card with one of those colours. Note that the player cannot receive a card of colour 1 secretly, as less players have a card of colour 2 or 3.

Knowing Hypnova is the last player to receive a card and that his card will be given out secretly, help him determine all the possible card colours he could get!

Input Specification

On the first line will be one integer $N$ ~N~, denoting the number of players in front of Hypnova. On the second line will be $N$ ~N~ characters. Each character will either be an integer $c$ ~c~ $(1 \le c \le 3)$ ~(1 \le c \le 3)~, representing the card colour that the $n^\text{th}$ ~n^\text{th}~ player got, or ~, representing a secret distribution.

Output Specification

Output all the possible card colours that Hypnova could get, one per line in ascending order.

Sample Input 1

3
1~2

Sample Output 1

1
2
3

Explanation of Sample Output 1

The second person in line will get the colour 2 or 3. If they get colour 2, then Hypnova will get a card with colour 1 or 3.

If the second person in line gets colour 3, then Hypnova can get colours 1, 2 or 3.

Sample Input 2

14
2222~~1~~~12~3

Sample Output 2

Comments

0

andi_g commented on Aug. 15, 2016, 4:40 p.m.

When I submit my code on Python 3, I get an Invalid Return on case 4, but when I submit the same code on PyPy3 I get Invalid Return on case 5 instead. Is there an error in my code that's causing this or is it the judge?

1

atarw commented on Aug. 15, 2016, 7:06 p.m.

your code exceeded pythons recursion limit

0

andi_g commented on Aug. 15, 2016, 9:22 p.m. ← edited →

Oh I should've thought of that. Thanks!