Jolly Jumpers..~

Problem Statement
     
Nim is a game in which two players take turns removing stones from heaps. On each turn, a player must choose a single heap and remove one or more stones from that heap. The player who takes the last stone wins.  Alice and Bob are bored with playing Nim over and over again, so they've decided to create a new variation called Ordered Nim. Ordered Nim differs from regular Nim in the following way. The heaps are numbered 0 through n-1 (where n is the number of heaps), and a player can only remove stones from a heap if all the lower-numbered heaps are empty.  You are given a vector <int> layout, where the i-th element (0-indexed) is the number of stones in heap i at the beginning of the game. Alice will take the first turn. Determine who will win the game, assuming both players play optimally. Return "Alice" if Alice will win, or "Bob" if Bob will win (all quotes for clarity).
Definition
   
Class:
OrderedNim
Method:
winner
Parameters:
vector <int>
Returns:
string
Method signature:
string winner(vector <int> layout)
(be sure your method is public)
   
 
Constraints
-
layout will contain between 1 and 50 elements, inclusive.
-
Each element of layout will be between 1 and 1000000000, inclusive.
Examples
0)
 
   
{5}
Returns: "Alice"
Alice takes all 5 stones and wins.
1)
 
   
{1,2}
Returns: "Bob"
According to the rules of the game, Alice is not allowed to take stones from heap 1 because heap 0 is not empty. Her only option is to take the one stone from heap 0. Heap 0 will then be empty, so Bob can take both stones from heap 1 to win the game.
2)
 
   
{2,1}
Returns: "Alice"
 
3)
 
   
{10,9,8,7,6,5,4,3,2,1}
Returns: "Alice"
 
4)
 
   
{1,1,1,1}
Returns: "Bob"
 
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.

Problem Statement
     
As a serious strategy-games player, you know how important it is for your country to have a strong economy. In order to make this happen, you've just built n factories and hired k specialists. Unfortunately, you now have no gold left, and you must figure out the fastest way to raise target units of gold.  In a single round, you earn F*S units of gold, where F is the number of factories and S is the number of specialists you currently have. At the end of each round, you can build more factories and hire more specialists. Building one new factory or hiring one new specialist costs price units of gold. As long as you can afford them, there is no limit to the number of factories and specialists you have. Return the minimum number of rounds required to earn at least target units of gold.
Definition
   
Class:
StrongEconomy
Method:
earn
Parameters:
long long, long long, long long, long long
Returns:
long long
Method signature:
long long earn(long long n, long long k, long long price, long long target)
(be sure your method is public)
   
 
Constraints
-
n, k, price and target will each be between 1 and 10^12, inclusive.
Examples
0)
 
   
2
1
2
10
Returns: 4
In the first round you will earn 2*1 = 2 units of gold and must spend them on hiring a new specialist. In each of the rounds that follow, you will earn 2*2 = 4 units of gold. You need 3 more rounds in order to earn at least 10 units of gold.
1)
 
   
2
1
2
9
Returns: 3
In the first round you will earn 2*1 = 2 units of gold and must spend them on hiring a new specialist. In the second round you will earn 2*2 = 4 units of gold and must spend them on building a factory and hiring another specialist. In the third round you will earn 3*3 = 9 units of gold.
2)
 
   
1
1
500000
1000002
Returns: 1000001
Wait 500000 rounds in order to earn 500000*1*1 = 500000 units of gold. At the end of the 500000th round, spend all your money to build a factory (or to hire a specialist). In each of the rounds that follow, you will earn 2*1 = 2 units of gold, so you need 500001 more rounds in order to earn the required 1000002 units of gold.
3)
 
   
5
4
15
100
Returns: 5
Don't spend your gold at all.
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.

Problem Statement
     
The RowGame is a one-player game in which a single piece is moved across a board. The board consists of N squares arranged in a row, numbered 1 through N, from left to right. Each square has an associated value.  Initially, the piece is on square 1, and the current direction is right. On each turn, the player moves zero or more squares in the current direction. The direction is then reversed for the next turn. Scoring works as follows. Initially the player's score is 0. Each time the player moves from square A to square B, the sum of the values of each square between A and B, inclusive, is added to his score. Values can be negative, and the player is never allowed to make a move that will cause his score to drop below zero.  You are given a vector <int> board, where the i-th element (0-indexed) is the value of square (i+1). Return the maximum score that can be attained if the player is allowed to make at most k moves.
Definition
   
Class:
RowGame
Method:
score
Parameters:
vector <int>, int
Returns:
long long
Method signature:
long long score(vector <int> board, int k)
(be sure your method is public)
   
 
Constraints
-
board will contain between 1 and 50 elements, inclusive.
-
Each element of board will be between -400000000 and 400000000, inclusive.
-
k will be between 1 and 400000000, inclusive.
Examples
0)
 
   
{2,-2,4,3,-10}
3
Returns: 21
Move 1: Move to square 4. You receive 2-2+4+3 = 7 points. Move 2: Move to square 3. You receive 3+4 = 7 points. Move 3: Move to square 4. You receive 4+3 = 7 points.
1)
 
   
{-6,5}
10
Returns: 0
There is no way to get a non-negative score after the first move, so you should make no moves at all.
2)
 
   
{5,-6}
10
Returns: 50
In each move you can stay in square 1 and earn 5 more points.
3)
 
   
{10,-100,80}
3
Returns: 30
1. On the first move, you cannot move to either of the other squares because it would cause your score to drop below zero, so you must stay on square 1 and get 10 points. 2. On the second move, your direction changes to left, but since there are no squares to the left of square 1, your only option is to stay on the same square and get 10 more points. 3. Finally, on the last move, your direction changes back to right, and this time, you have two options: stay on square 1 or move to square 3. Moving to square 3 would make you lose 10 points, for a total score of 10, while staying on square 1 would get you 10 points, for a total score of 30. You choose to stay on square 1.
4)
 
   
{10,-100,80}
4
Returns: 90
 
5)
 
   
{-100,1,2,3,4,5,6,7,8,9,10,11,12,13,14}
400000000
Returns: 41999999900
 
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.