The Josephus problem is a classic, although it is also a little grim. The history of the problem is in its wikipedia entry, but our formulation of the problem differs subtly from most of the ones found on the net.
There are N soldiers trapped in a cave and hopelessly surrounded. They agree to kill each other to save themselves from what they are sure is a far more gruesome fate of capture. They agree to kill each other using the following method: the first soldier will kill the living person directly in front of them. Then, the next living person will kill the next living person in front of them. Then, the next living person will kill the next living person in front of them. And so on until there is only one peron left.
Your task is to simulate this process, provide an ordered listing of who kills whom, and then print out who survives after this bizarre suicide is complete. You should do this directly, by putting the soldiers in a circularly linked list and then progressively removing every other soldier.
The input you will be given will be formatted as an integer on its own line (representing the number of soldiers) and then every name on its own line, in order. The output should be N-1 lines, where each line says "x kills y", and then one last line saying "z lives!".
This is all pretty abstract, so I'll show you an actual input, followed by the actual output generated by my reference solution:
7 Bashful Doc Dopey Grumpy Happy Sleepy Sneezy
Bashful kills Doc Dopey kills Grumpy Happy kills Sleepy Sneezy kills Bashful Dopey kills Happy Sneezy kills Dopey Sneezy lives!
You should conform exactly to the input and output specification, as I will be using massive test cases and checking your output against the correct output with the diff command.
In order to verify O(N) timing, a much larger test case may be found here. On ix, using python, this example takes between 6 and 7 seconds to run (when I redirect the output to /dev/null so that I am not just timing the bandwidth of my network connection). If you find yours taking more than a minute, there's probably a problem. Also, in that example, bauxite lives.
| Grade Bucket | Count |
|---|---|
| 0 | |
| 10 | |
| 20 | |
| 30 | |
| 40 | |
| 50 | |
| 60 | |
| 70 | |
| 80 | |
| 90 | |
| 100 | |