Have you heard of the Joseph Problem?
This is a slightly harder version of the problem!
N people stands in a circle, starting from the first person they are numbered
1, 2, 3, ... N clockwise.
There are also N-1 predetermined numbers: a1, a2, a3, ... aN-1.
Now the game starts. Starting from person one and going clockwise, they count
a1 people and the person that is counted last is "out". When a person is "out"
he simply moves out of the circle and the game continues with the rest people
closing in and forming a circle again. After that they continue from the next
person and count a2 people, then a3 people... etc.
After N-1 iterations, all poeple are "out" except one.
That person is called "Happy Joseph".
Given N, and the N-1 predetermined jumps,
who will be the "Happy Joseph"?
There are multiple testcases. The first line is an integer T indicating the number of testcases.
Each testcase begins with a number N, indicating the number of people in the circle. Then follows N-1 numbers denoting a1, a2, a3, ... aN-1.
T <= 100
N <= 20000
1 <= ai <= 100000000
For each testcase instance, output a single number in a line denoting the ID of "Happy Joseph".
2 4 4 3 1 6 1 200 3 400 5
2 3
Migrated from old NTUJ.
kelvin
| No. | Testdata Range | Score |
|---|