Problem Statement The galaxy contains an unlimited supply of habitable planets. These are numbered 0, 1, 2, ... in decreasing order of terraformation. Planet 0 is the origin of life in the galaxy, and it is still the planet best suitable for life. There are multiple colonies in the galaxy. Their current state is described by the int[]s planet and colonySize. For each i, there is a colony on planet planet[i] with population colonySize[i]. At any moment, there can be multiple colonies on each planet (including planet 0). As soon as a colony becomes empty, it ceases to exist completely. For some unspecified reason it became necessary to relocate all colonists back to planet 0. It is unclear whether this is the responsibility of the Galactic High Command (below called "player A") or the Galactic Colonization Authority ("player B"). The two organizations discussed this and came to an agreement that they will issue alternating relocation orders. Each relocation order must move some positive number of colonists towards planet 0, using one of the moves described below. The player after whose move all colonists are on the home planet will be celebrated as the one who successfully completed the relocation. (Equivalently, the player unable to make a valid move loses.) Both players are trying to reach this goal and play optimally. There are three types of allowed moves: A normal move. Select a colony on some planet P > 0 and another (currently existing, non-empty) colony on planet P-1. Select a positive number X up to and inclusive the population of the first colony. Move X colonists from the first colony to the second one. A slow move. Select a colony on some planet P > 0. Select a positive number X up to and inclusive the population of that colony. Build a new colony on planet P-1. While you do so, take X colonists from the old colony and move them slowly to the new one. As the move is slow, the colonists will multiply along the way and exactly 2*X of them will arrive to their destination. A fast move. Select a colony on some planet P > 0 such that P is an odd prime (3, 5, 7, 11, ...) and the population of the colony is at least P. Relocate the entire colony to planet P-2 (as a new colony on that planet). While adapting the colony to the new, different environment, P of the colonists will die. (If the original colony had X colonists, the new one will have X-P.) A less precise but shorter version of the same rules: Move any positive number of people from a colony on planet P to an existing colony on planet P-1. Take X people from a colony on planet P, create a new colony on planet P-1 with 2*X people. Take an entire colony of X people from planet P, where P is an odd prime, and create a new colony on planet P-2 with X-P people. Two moves are different if you make different selections during the move. For example, suppose there are four colonies: colony A and colony B on planet 4 with 1 person in each of them, colony C on planet 5 with 1 person, and colony D on planet 5 with 7 people. Then, the possible moves look as follows: There are 16 ways to make a normal move. Three of them are "move 1 person from C to A", "move 1 person from C to B" and "move 4 people from D to B". There are 10 ways to make a slow move. Two of them are "move 1 person from colony A (which ceases to exists) and create a new colony E on planet 3 with 2 people" and "take 4 people from colony D and create a new colony E on planet 4 with 8 people". There is only 1 way to make a fast move: "take the entire colony D and instead create a new colony E on planet 3 with just 7-5 = 2 people". Player A is the one to make the first move. Return the count of different winning first moves they can make. (In particular, return 0 if the current position is losing for them.) Definition Class: Colonists Method: countMoves Parameters: int[], int[] Returns: long Method signature: long countMoves(int[] planet, int[] colonySize) (be sure your method is public) Limits Time limit (s): 2.000 Memory limit (MB): 256 Stack limit (MB): 256 Notes - As shown in an example in the statement, relocating one colonist slowly produces two new colonists. Don't make any human-based assumptions about how the colonists multiply, just accept that their number always doubles during a slow move :) Constraints - planet will have between 1 and 100 elements, inclusive. - colonySize will have the same number of elements as planet. - Each element of planet will be between 0 and 10^6, inclusive. - At least one element of planet will be positive. - Each element of colonySize will be between 1 and 10^9, inclusive. Examples 0) {2, 2, 3, 3, 5, 5, 12, 12} {12, 12, 5, 5, 8, 8, 3, 3} Returns: 0 The second player has a fairly trivial winning strategy based on symmetry, so this is a losing position for the player whose turn it is. 1) {1} {470} Returns: 1 Relocate everyone to planet 0 using a slow move and win. 2) {0, 1, 1} {30, 470, 420} Returns: 2 One possible winning move is to relocate 50 people slowly from colony 1 to a new colony on planet 0. After the move we will have: on planet 0 a colony of size 30 and a colony of size 100, on planet 1 two colonies of size 420 each. It can be shown that this is a losing position (for the player whose turn it then is). The other possible winning move is to relocate 50 people quickly from colony 1 (on planet 1) to colony 0 (on planet 0). After the move we will have: on planet 0 a colony of size 80, and on planet 1 two colonies of size 420 each. 3) {3, 4, 5, 11} {1, 7, 2, 14} Returns: 2 One of the two winning moves here is a fast move. 4) {17} {17} Returns: 2 One of the two winning moves is to relocate the entire colony to planet 15 using a fast move. During this move all 17 colonists perish, and so the colony on planet 15 immediately stops existing. As there are now no colonists on planets other than planet 0, the game is now over. This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.