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.
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:
No comments:
Post a Comment