Problem 1006
On Alice's last bank statement, the end of last month is at the top of the page. Then, on the lines that follow, 12 non-zero integers (1 per line) correspond to the operations of the month. The number is positive if it is a credit on the account, negative if it is an expense. Curiously, each number of lines 1 to 10 is strictly greater than the total of the two lines that follow. In addition, lines 11 and 12 are identical to lines 1 and 2.- 1A. How many positive numbers are there, at maximum, on lines 1 to 10?
- 2A. Knowing that the account is at 10 € at the end of the month and that the maximum of positive lines has been reached, what was the minimum balance at the end of last month?
For this problem, I performed a somewhat exhaustive search, noticing properties on small sizes (number of lines of the statement), and then enlarging the size with restrictions. In particular, we note very quickly that the values of the positive lines are always small and that the minimum negative values can not exceed -30. We also note, of course, that two consecutive lines can not be positive (which is also easily seen from conditions of the statement). Based on this, we can perform an exhaustive search for a size of 12 (but it still takes a while). For this size, we see the structure that is set up for all the larger sizes.
The code of the program can be found here.
Remark: for this problem, I did not have all the points since the program given above has an error. Indeed, it is assumed that the first line is positive (I made this assumption when I searched for the maximum number of positive lines and did not question it later). However, the minimum is reached when the second line is positive. This explains the result of 102 instead of 100.
The code of the program can be found here.
Remark: for this problem, I did not have all the points since the program given above has an error. Indeed, it is assumed that the first line is positive (I made this assumption when I searched for the maximum number of positive lines and did not question it later). However, the minimum is reached when the second line is positive. This explains the result of 102 instead of 100.
- 1A: There are at most 4 positive numbers on lines 1 to 10.
- 2A: The minimum balance at the end of last month is 100 €.