10015 - Joseph's Cousin

I used the hints from the Algorithmist. (http://www.algorithmist.com/index.php/UVa_10015)

I still have a high run time ~ 9sec but it was accepted since the limit is 10sec. 

(1) Prime Number: Represents the number of steps you will take

(2) If Prime Number > n, you will naturally do prime%n to get the actual number of steps since it’s a circle

(3) You will perform/walk the steps from where you were before, so you need to add the previous position (i + prime%n)

(4) take 1 point off since we are already standing on position i and we don’t want to count it twice. (i + prime%n) – 1

(4) Again you need to mod since it’s a circle ((i + prime%n) - 1) %n

(5) Kill the person standing at i+1 since we were counting from i=0.

Person:

1

2

3

4

5

6

Prime = 2

Total = n = 6

Position = i = 0 (Start value)

Person to kill is at position: i + 1 where:

i = ( i + prime % n ) – 1 ) % n

 i = (0 + 2 % 6) – 1) % 6 = 1

 Kill person at position i+1 = 2

Person:

1

3

4

5

6

Prime = 3

n = 5

Position = i = 1

i = (1 + 3 % 5) – 1) % 5 = 3

Kill person at position = i + 1 = 4

Person:

1

3

4

6

Prime = 5

n = 4

Position = i = 3

i = (3 + 5 % 4) – 1) % 5 = 3

Kill person at position = i + 1 = 4

Person:

1

3

4

Prime = 7

n = 3

Position = i = 3

i = (3 + 7 % 3) – 1) % 3 = 1

Kill person at position = i + 1 = 1

Person:

3

4

Prime = 11

n = 2

Position = i = 1

i = (1 + 11 % 2) – 1) % 2 = 1

Kill person at position = i + 1 = 1

4 survived!

Source Code: