Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | monopoly.in, monopoly.out | Sursă | IIOT 2022-23 Runda I |
| Autor | Carlo Collodel, Davide Bartoli | Adăugată de |  Buca Mihnea-Vicentiu •UnknownPercentage |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Monopoly
You find an old game of monopoly in your attic and you decide to play it against Carlo. You don't like to lose, so you decide to use
your magic dice to cheat.
The game is played on a board, made of N cells arranged in a circle. The cells are numbered from 0 to N-1, with cells N-1 and 0 being adjacent.
Each cell has a tax value T i associated with it. Every time a player lands on a cell, he has to pay the tax value of that cell (the tax value can be negative, meaning that the player receives money).
Carlo starts on cell 0 and will play K turns of monopoly. Each turn he rolls two 6-sided dice and moves forward by the sum of the two values.
He then pays the tax value of the cell he lands on. If the two dice value are equal, after moving and paying, he must continue and roll the dice again.
Carlo can move at most 3 times in a single turn, then his turn automatically ends (even if the 2 dice values are equal).
You can control the outcomes of all the dice rolls, maximize the amount of money Carlo loses during the game.
Date de intrare
The first line contains the integers N and K (1 ≤ N ≤ 1000), (1 ≤ K ≤ 1000).
The second line contains N integers T i (-109 ≤ T i ≤ 109).
For tests worth 20 points, K = 1.
For tests worth 30 more points (1 ≤ N ≤ 100), (1 ≤ K ≤ 100).
Date de ieşire
You need to write a single line with an integer: the amount of money Carlo loses during the game.
Exemplu
| monopoly.in | monopoly.out |
|---|---|
| 11 1 0 5 4 12 6 3 15 7 2 20 5 | 47 |
| 12 1 -10 -20 -4 -6 -15 -20 -20 -20 -20 -20 -20 -20 | -6 |
| 2 2 999999999 1000000000 | 5999999998 |
Explicaţie
In the first sample case the answer is 47. A possible sequence of rolls is the following:
* Carlo rolls 3 and 3 and moves to cell 6, with tax value 15. Since the 2 dice values are equal he must throw again.
* Carlo rolls 4 and 4 and moves to cell 3, with tax value 12. Since the 2 dice values are equal he must throw again.
* Carlo rolls 3 and 3 and moves to cell 9, with tax value 20. He already moved 3 times, so his turn ends, even if the 2 dice values are equal.
