UVa 180

From Algorithmist
Jump to navigation Jump to search

This is the known josephus problem. The statement "Eeeny men...." is 15 letter, so we are in the circle and will kill some one each time we count 15...Usually dynamic programming solve josephus problem in faster time....There is a relation between a circle with size n Where you kill with count m=2 , then m+1, then m+2...until cycle = 15

n = size of circle, cycle the value we iterate with and kill here is 15

     for(i = 2; i <=num; i++) 
            x = (x + cycle) % i;

Now x represent the last surviver from the circle

This is the simplest josephus problem , but in this problem you will need bit work.

You can read the discussions on UVa Board for a better explaination. Appearently the judge data has some errors in that you should only output the position if p<=low/2, where p is the first safe valid position and low is the lower bound.