Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Faruk Bulut, Prepared by Ibrahim Mesecan.
Hot Potato - Revisited
In
Hot potato game people sit around a circular table and a hot potato
is passed to every m person. To add more fun and some randomness,
computer engineering department students made a small change in
the game. Now every person is given a random number (ki)
between -2000 and +2000. The game starts from the first person.
And, instead of passing to every m person, for positive numbers,
the potato is passed to clockwise direction to
(ki)th person. For negative numbers,
it's passed to counter clockwise direction. After eliminating
the (ki)th person the next person according
to the current direction becomes the new head. Then, the program
continues until there leaves only one person in the game. Please
follow details given in the explanation.
Question:
Write a program which reads the information for n people and shows
the ID of the person who remains last.
Input specification
You will be given an integer n. And in the following n lines
you will be given n integers between -2000 and +2000 where
0 ≤ n ≤ 10,000.
Output specification
Show the ID of the person who still contines the game. Note:
ID's start from 1.
Sample Input I
5
2
-1
3
-2
1
|
Sample Output I
5
|
Explanation:
- 2 -1 3 -2 1: Starts from the first (1) person, goes 2 steps
CW and (3) leaves. The potato goes to the next person (4).
- -2 1 2 -1 The direction is CCW and goes two steps and stops
at (2). (2) leaves the game and the potato goes to
the next person (1).
- 1 -1 -2 Potato goes to (-1) and he leaves.
Then the potato goes to (-2).
- -2 1 Potato starts from (-2) and stops at (-2). And he leaves.
- (1) (5th person) remains in the game and wins.
Для отправки решений необходимо выполнить вход.
|