All Tracks Math Problem

Billy's Game

Game Theory, Mathematics, Sprague–Grundy Theorem


Billy and Bob are best friends but when it comes to playing a game they do not let it go easily. They fight neck and neck, be it Chess, Go, etc. They are bored with playing old, classical games that involves standard opening theories. They have got their hands on some new game which is described as follows.

There are \(N +\ 1\) buckets in a row. First \(N\) buckets contain \(1\) or more balls and the last bucket is empty. In a turn, a player can draw \(1\) or more balls from a bucket such that a maximum of \(floor(\sqrt{X})\) balls are left in that bucket where \(X\) is the number of balls present in that bucket at that point of time. A player will lose if there is nothing left to draw.

Bob is going to start the game but we want Billy to win. So, what is the minimum number of balls that need to be added to the \((N\ +\ 1)^{th}\) bucket, so that our favorite Billy wins. Needless to say, both players will be playing optimally.

Input format

  • First line: An integer \(T\) denoting the number of test cases
  • In each test case:
    • First line: Integer \(N\) as described in the problem statement
    • Second line: \(N\) integers denoting the number of balls in each bucket

Output format

Print the minimum number of balls that have to be put in the \((N\ +\ 1)^{th}\) bucket.


\(1 \le T \le 10\)

\(1 \le N \le 10^{5}\)

The number of balls in the input buckets do not exceed \(10^{9}\)

1 1 1
1 1 1 1

First test case:
In each turn, one of the buckets will be getting empty. We just need to have a nonempty bucket so that the last bucket is emptied by Billy.

Second test case:
In each turn, one of the buckets will be getting empty. The last bucket will  be emptied by Billy then all the buckets will have 0 balls in them.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications