HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Linear Data structures: Stacks, Queues, Linked Lists, etc > problem:


50780 - Hot Potato - Revisited

Guest
• Discussion of problem (1)

Section problems

• 50286 - Remove Duplicates
• 50775 - Balanced Parenthesis
• 50340 - Game 19
• 50877 - Friendly Queue
• 51086 - Top popular student
• 50774 - Hot Potato
• 50777 - Dwarfs Maze
• 50781 - ReversesreveR
• 50780 - Hot Potato - Revisited
• 50564 - Mother's Milk Buckets
• 50636 - Brackets
• 50776 - The number of different pa...
• 50779 - The shortest path in a maze

Feedback

If you notice incorrect translations in Contester, please let author know.

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.

Для отправки решений необходимо выполнить вход.

www.contester.ru