TwentyOne

PROBLEM STATEMENT:

TwentyOne is a counting game where the goal is to avoid saying 21.  The game
goes as follows:
* Assume N people are playing and the N people are numbered 0 through N - 1.
* Each player counts one, two, or three consecutive integers starting with 
  the number one greater than the last number said by the previous player, 
  or starting with 1 if it is the first turn of the game.
* Play starts with an arbitrary Player p and the number 1.  Play proceeds to
  Player (p + 1) % N, then Player (p + 2) % N, etc...
* The player who counts 21 loses.

For example, suppose there are three people playing and play starts with Player
0.  The game may go on like this:
Player 0 says "1, 2, 3"
Player 1 says "4, 5"
Player 2 says "6"
Player 0 says "7, 8, 9"
Player 1 says "10, 11, 12"
Player 2 says "13"
Player 0 says "14"
Player 1 says "15, 16"
Player 2 says "17, 18"
Player 0 says "19, 20"
Player 1 says "21" and loses.

You have become overly obsessed with TwentyOne and go around challenging your
friends to the game to prove you are smarter than them. It is thus very
important that you do not lose.  To help in your quest to be the TwentyOne
champion, you have decided to write a program which recommends to you which
numbers you should say on your turn.

Before playing a game, you determine the skill levels of your competitors. The
competitors either have a skill level of 0 or 1:
* A skill level of 0 implies the player always chooses how many numbers to
  say at random.  That is, there is a 1/3 chance the player will say one 
  number, a 1/3 chance the player will say two numbers, and a 1/3 chance 
  the player will say three numbers.  Even if saying two or three numbers
  involves saying 21 or counting past 21, the chances of the player saying
  one, two, or three numbers are all 1/3.
* A skill level of 1 implies the player always says the number of numbers
  that minimizes his chances of losing.  The player determines which
  numbers to say using the same technique your program should use.

You are player 0 and your skill level is 1.  

Your program assumes it is your turn, inputs the last number said by the
previous player, and the skill levels of all players and outputs the numbers
you should say on the current turn to minimize your chances of losing.

DEFINITION:
Class Name: TwentyOne
Method Name: getBestOption
Parameters: int, int[]
Returns: int[]
Method Signature (be sure your method is public): 
  int[] getBestOption(int lastNumber, int[] skillLevels);

TOPCODER WILL ENSURE:
* lastNumber is between 0 and 20, inclusive.
* skillLevels contains between 2 and 10 elements, inclusive, and all 
  elements are either 0 or 1.
* skillLevels[0] = 1.  (Your skill level is 1).

NOTES:
* The number of elements in skillLevels is the number of players.
* skillLevels[i] corresponds to the skill level of player number i.
* When other players with skill level 1 are calculating what they 
  will say, they use the same values for the skills of the other 
  players as you.  They all know your skill level is 1.
* lastNumber = 0 implies you are going first and must start counting
  with the number 1.
* If more than one option yields the same chance of losing, you 
  (and the other players with skill levels 1) always say the fewest
  numbers corresponding with this lowest repeated chance of losing.  
* If a player with skill level 0 must start counting at 19, 20 or 21,
  there is still a 1/3 chance they will say 1 number, a 1/3 chance they
  will say 2 numbers, and a 1/3 chance they will say 3 numbers.  That 
  is, they may count past 21.

EXAMPLES:

EXAMPLE 1:
If lastNumber = 17, and skillLevels = {1, 0, 0}

If you say 1 number, 18:
There is a 1/3 chance player 1 will say 19.  If this occurs, there is a 1/3
chance player 2 will say 20 (in which case you would have to say 21 and lose).
There is a 1/3 chance player 1 will say 19, 20 in which case you will not lose.
And there is a 1/3 chance player 1 will say 19, 20, 21 in which case you will
not lose.
Thus there is a 1/3 * 1/3 = 1 / 9 chance of you losing if you say 1 number.

If you say 2 numbers, 18 and 19, there is no chance you will lose because
either player 1 or player 2 will be forced to say 21.

If you say 3 numbers, there is no chance you will lose.

Saying 2 or 3 numbers yields the same results, so the program outputs {18, 19}.

EXAMPLE 2:
If lastNumber = 16, and skillLevels = {1, 0, 1}

If you say 1 number, 17:
There is a 1/3 chance player 1 will say 18.  In this case, player 2 will not
lose if he says 1 or two numbers, so he says 19 and you can say 20 forcing
player 1 to lose.
There is a 1/3 chance player 1 will say 18, 19.  In this case, player 2 will
say 20, and you will lose.
There is a 1/3 chance player 1 will say 18, 19, 20.  In this case, player 1
will lose.
Thus there is a 1/3 * 1/3 = 1/9 chance of your losing if you say 1 number.

If you say 2 numbers, 17, 18:
There is a 1/3 chance player 1 will say 19.  In this case, player 2 will say
20, and you will lose.
There is a 1/3 chance player 1 will say 19, 20.  In this case player 2 will lose.
There is a 1/3 chance player 1 will say 19, 20, 21.  In this case player 1 will
lose.
Thus there is a 1/3 * 1/3 = 1/9 chance of you losing if you say 2 numbers.

If you say 3 numbers, 17, 18, 19:
There is no chance of your losing.

Thus you the program outputs {17, 18, 19}

EXAMPLE 3:
If lastNumber = 1, and skillLevels = {1, 1, 0, 0, 1}, the program outputs {2}.

EXAMPLE 4:
If lastNumber = 18, and skillLevels = {1, 0}.
If you say 19, there is a 1/3 chance Player 1 will say 20, in which case you
lose.
  there is a 1/3 chance Player 1 will say 20, 21, in which case he loses.
there is a 1/3 chance Player 1 will say 20, 21, 22, in which case he also
loses.
Thus there is a 1/3 chance of your losing.
If you say 19, 20, Player 1 will lose.  If you say 19, 20, 21, you lose.
Thus, the program outputs: {19, 20}.

EXAMPLE 5:
If lastNumber = 3, and skillLevels = {1, 1, 1, 1, 1, 1, 1, 1, 1, 0}, the
program outputs {4}.

EXAMPLE 6:
If lastNumber = 2, and skillLevels = {1, 0, 0, 1, 1, 1}, the program outputs
{3, 4, 5}.

EXAMPLE 7:
If lastNumber = 15, and skillLevels = {1, 0, 1, 0, 0}, the program outputs {16,
17}.