| Problem Description The Joseph\\\\\\\'s problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy. |
| Input The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14. |
| Output The output file will consist of separate lines containing m corresponding to k in the input file. |
| Sample Input 340 |
| Sample Output 530 |
View Code pay attention
firstly, get result form in advance will take less time than according input to get the result.
secondly, form a habit of recall the method to get the result, I think you will have more clear mind.
thirdly, think in detailly.case in point: you must judge whether index is equal to zero or not, even though you will use get only one "if" to get the answer, but you can't. because the dividend is changed!!
forthly, ok, I must acknowledge that I forget the & and EOF, I really must work hard.
last but not the least, you need not care about which number is counted, just care about whether the counted number is smaller than k or not.
my programme is designed that the number is from 1 to 2 * k
if the number is from 0 to 2 * k - 1, then the code is as follow
View Code 1 int joseph(int k, int m) 2 { 3 int n, index, i; 4 n = 2 * k; 5 index = 0; 6 //circulate k time, if every time the index is bigger than k, then return true 7 for (i = 0; i < k; i++) 8 { 9 index = (index + m - 1) % n;10 n--;11 if (index < k)12 return 0;13 }14 return 1;15 }