UVa 10015

From Algorithmist
Jump to navigation Jump to search

10015 - Joseph's Cousin[edit]


This problem involves primes and modular arithmetic, as well as a circular data structure.


The problem is poorly specified, but what it is asking you to do is move around a circle some number of times, and kill the person you stop on. You keep passing around the circle until there is only one person left, and this is the person you output.

The number of times you move around the circle is determined by the next prime number in the sequence .

What the problem intends you to do is start at the first person, and always start your count at . Then, move around the circle, counting up for each person you get to that's still alive. So at the very beginning, if you have people, then your sequence is (realizing that it is circular, so is next to ). Since the first prime number is 2, then you start at person , count up to by going to the next person, then kill person . Now you're effectively at person , because you've just killed person . The next prime number is , which means you're at person , then go to person , and end at person and so person gets killed. The next prime number is , and the sequence of people you traverse is . Since you end on person , that's who gets killed.

The thing that's important to note is that you don't have to simulate traversing through the people left, but you can do it with one big jump using addition and mod. You know you're jumping p people, where p = prime[i], where i is the person that's being killed. Then go back one since you start counting at , not . Then you mod the result by the number of people left, to make sure you stay in bounds.

Make sure to keep track of your current location, starting at 0, and always make your jumps from there, as well as keeping track of which person you're killing, incrementing after each person (which will increment the prime you jump by).

The best way to store the people is as a linked list, which gives constant insertion and linear removal, and keeps the size of the list stored nicely for you to mod by every time.

Also, you should use a prime sieve at the beginning to get the first 3501 primes (ends up needing up to about 32,650).