Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1356
Question Name: Last Number In Circle
Question Description: N persons are standing in a circle. We are removing the one from the circle every M persons, until only one person is in its original position. Find out the last person.
Input: the input might contain multiple test cases. One single line is a test case. Each line may contain one or two integers. If it contain one integer 0, we are exiting the program. If the line include two integers N (0 <= N <= 1000000) and M (1 <= M <= 1000000). N is the number of persons. And persons are numbers from 1. M is the interval.
Output: print the ID number of the last person in the circle.
1 2 3 4 5 6 7 8 | Input: 1 10 8 5 6 6 Output: 1 3 4 |
This question is the Josephus problem. The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/11/2014 * Last updated: 09/11/2014 * * Filename: LastNumberInCircle.java * Compilation: javac LastNumberInCircle.java * Execution: java LastNumberInCircle * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * There are N people standing in a circle. We remove every K persons out of * the circle. Find the last one in the circle. * @author Sheng Yu codesays.com */ public class LastNumberInCircle { /** * There are N people standing in a circle. We remove every K persons out of * the circle. Find the last one in the circle. * This is the Josephus problem. * http://en.wikipedia.org/wiki/Josephus_problem * @param n the number of persons in the circle. * @param k the interval between two removal. * @return */ public static int lastOne(int n, int k){ int last = 0; for (int i = 2; i <= n; ++i) { last = (last + k) % i; } return last + 1; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int n = 0; int k = 0; while (st.nextToken() != StreamTokenizer.TT_EOF) { n = (int) st.nval; if (n == 0) break; st.nextToken(); k = (int) st.nval; System.out.println(lastOne(n, k)); } } } |