You are fascinated by the game 2048 and have been playing it for more than 24 hours consecutively! However, because of the complexity of the game, you could hardly win the game. After many frustrating tries, you realised that it would probably be better to write a program to play it.
The game 2048 is played on a 4x4 board. At the start, two of the grids are filled with the number 2. On each of your move, you can slide in four different directions, namely, left, right, up and down, to move the grids that are filled with numbers. The movement of the grids follow these rules:
- The grids closer to the edge of the board that you are sliding towards move first, i.e., if you slide leftwards, the grids in the leftmost row move first, followed by the grids in the second left row, the third left row, and the rightmost row;
- Only grids that are filled with numbers move;
- A grid moves toward your direction until it hits the edge of the board or another grid that is filled with a number. In the second case, if the two numbers are the same, and the number in the grid that is hit has not been doubled in this turn, the number in the grid that is hit will be doubled, while the number in the grid that is moving disappears, and you are awarded score that is equal to the sum of the two numbers;
- If a slide towards a direction does not cause any change to the board, then you are not allowed to slide towards that direction in this turn(unless there is no legal move; in that case, the game ends);
- After each of your turn, a new number is generated in a random empty grid. The new number has a 75% chance to be 2, and a 25% chance to be 4. If after one of your turn there is no empty grid, then the game ends.
Your aim, however, is not to obtain the maximum score, but to make the largest number on the board as large as possible when the game ends. For example, a score of 2000 with the largest number 512 is considered superior to a score of 10000 with the largest number only 256. In the original game, you would have won once you made a 2048 in one of the grids; but since you are cheating by writing a program, you will naturally aim for as high as possible.
There are 20 test cases. For each test case, you are given an award according to the following scheme:
- 120; if M > 2048
- 100; if M = 2048
- 60; if M = 1024
- 35; if M = 512
- 10; if M = 256
- 0; if M <= 128
Let S be the average of your awards. Your final score is then given by the following formula:
- 100; if S >= 92
- 4*(25(S-20)/72); if 20 <= S < 92
- 0; if S < 20
Functions that you must implement:
void init(int r1, int c1, int r2, int c2);
This function will be called once before anything else is called. It is for you to initialise any global variables you might need. (r1,c1) and (r2,c2) are the positions of the two starting 2s(0-based indexing).((r,c) refers to row r column c)
void generate(int r, int c, int x);
This function will be called after each of your move to generate a new number x in a random empty grid (r,c).The number has a 75% chance to be 2 and a 25% chance to be 4.
This function will be called when it is your turn to slide. Your return must be an integer between 1 and 4, representing upward(1), rightward(2), downward(3) and leftward(4) respectively.
No sample is provided. If you are still unsure about any of the rules, simply google 2048 and click on the first result.