EllysBounceGame

2016 TCO NYC Regional · 2016-03-24 · by espr1t

2016 TCO NYC Regional · 2016-03-24 · by espr1t · Search, Simulation

Show categories

Class Name: EllysBounceGame

Return Type: long

Method Name: getScore

Arg Types: (vector<int>)

Problem Statement

Elly plays a computer game. In the game, N tiles are arranged in a row from the left to the right. A positive integer is written on each tile. At the beginning of the game, the player chooses a starting tile and a direction (either left or right). She then places her hero onto the chosen tile, facing the chosen direction. This is the only interaction the player has with the game. From this point on, the game proceeds on its own as described in the next paragraph.

At the beginning of the game the score is zero. The game plays itself in turns. Each turn plays out as follows:

The hero reads the number on her current tile and adds it to the score.
If the number on the tile is odd, the hero adds 1 to the number and then she reverses her direction. (For example, if the hero is facing right and just stepped onto a 19, she will increment it to a 20 and then turn around to face left.)
The hero will take a step forward: onto the next cell in her current direction. If this makes her step off the board, the game ends.

You are given the int[] tiles. The elements of tiles are the integers currently written on the tiles, from the left to the right. Return the largest possible score that can be achieved by choosing the optimal starting tile and direction.

Constraints

tiles will contain between 1 and 2,000 elements, inclusive.
Each element of tiles will be between 1 and 1,000,000,000, inclusive.

Examples

{42, 13, 17, 17}
Returns: 139

In this game Elly should start by placing her hero onto the cell number 2 (i.e., the cell that contains the left occurrence of the number 17). The hero should initially face right. The game will then proceed as follows: The hero adds the 17 to the score. The score is now 17. The number 17 is odd, so the hero increments it to an 18 and turns around to face left. The hero moves leftwards from cell 2 to cell 1. The hero reads the number 13 and adds it to the score. The score is now 30. The number 13 is odd, so the hero increments it to a 14 and turns around to face right. The hero moves rightwards from cell 1 to cell 2. The hero reads the number 18 (remember that we incremented it before) and adds it to the score. The score is now 48. The number 18 is even, so the hero does nothing. The number remains the same and her direction does not change. The hero moves rightwards from cell 2 to cell 3. In the fourth turn of the game the hero adds 17 to the score (new score: 65), changes the 17 to a 18, turns around, and takes a step left. In the fifth turn of the game the hero adds 18 to the score (new score: 83) and takes a step left. In the sixth turn of the game the hero adds 14 to the score (new score: 97) and takes a step left. In the seventh turn of the game the hero adds 42 to the score (new score: 139) and takes a step left. This step causes the hero to leave the board, so the game ends with the final score of 139 points.

{1337}
Returns: 1337

As there is only one cell, the game will end after its first turn. Our final score will be the number initially written in the cell.

{2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}
Returns: 4094

All the numbers on this board are even. Elly has two optimal strategies: she can either place the hero onto the leftmost cell facing right, or she can place her onto the rightmost cell facing left. Either way, the final score will simply be the sum of all the numbers on the board.

{1, 2, 2, 2, 2, 1, 2, 2, 2, 2}
Returns: 36

{
795755685, 581869303, 404620563, 708632712, 545404205, 133711906, 372047868, 949333986, 579004999, 323567404,
418932836, 944672732, 196140741, 809094427, 946129058, 30574577, 182506778, 15198493, 150802600, 138749191,
676943010, 177512688, 126303054, 81133258, 183966551, 471852627, 84672537, 867128744, 857788837, 275731772,
609397213, 20544910, 811450930, 483031419, 361913171, 547204602, 892462744, 522136404, 173978710, 131752569,
478582453, 867889991, 153380496, 551745921, 647984700, 910208077, 283496852, 368550363, 379821990, 712568903,
40498239, 113911604, 103237637, 39073007, 684602223, 812852787, 479711181, 746745228, 735241235, 296707007,
262522458, 870676136, 136721027, 359573809, 189375153, 547914047, 198304613, 640439653, 417177802, 25475624,
758242872, 764919655, 310701088, 537655880, 361931892, 14685971, 213794688, 107063881, 147944789, 444803289,
884392679, 540721924, 638781100, 902841101, 7097711, 219972874, 879609715, 156513984, 802611721, 755486970,
103522060, 967048445, 913778155, 94092596, 519074050, 884870761, 248268555, 339840186, 53612697, 826647953,
185518682, 263689968, 375666519, 12105076, 481342795, 242517397, 698412072, 529176049, 511091142, 958646068,
140457297, 971018539, 172898400, 830709769, 461945557, 529322873, 781261465, 823879998, 961264979, 76338301,
68299843, 767742622, 95625158, 769482974, 121898334, 257380088, 292455642, 772389186, 468566955, 817480336,
174842016, 799777367, 944694477, 678852157, 595387439, 23356646, 641212875, 988512771, 105989509, 817183892,
684114203, 49299351, 92133643, 427854501, 797640594, 287767371, 45931780, 58150107, 303810412, 933029416,
503168826, 397865509, 844370146, 650825879, 78396939, 193198052, 649075580, 949627106, 32760104, 53860494,
510366104, 290319952, 726585506, 886491639, 781277163, 741593945, 933922382, 147620738, 355650504, 308964799,
227669234, 375163529, 42817073, 685003585, 57725501, 883096448, 634002468, 893645501, 856191918, 29924130,
325791710, 736062367, 231714001, 515103007, 15209164, 748808127, 948469521, 530490811, 283421979, 150468288,
557942924, 663307953, 851888285, 696117850, 16017443, 663423247, 51119002, 172720542, 447930742, 668894616
}
Returns: 4760067425204

Watch out for overflow!

Submissions are judged against all 105 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EllysBounceGame with a public method long long getScore(vector<int> tiles) · 105 test cases · 2 s / 256 MB per case