首页 > 专题系列 > Java解POJ > POJ 3517 And Then There Was One [解题报告] Java
2013
11-12

POJ 3517 And Then There Was One [解题报告] Java

And Then There Was One

问题描述 :

Let’s play a stone removing game.

Initially, n stones are arranged on a circle and numbered 1, …, n clockwise (Figure 1). You are also given two numbers k and m. From this state, remove stones one by one following the rules explained below, until only one remains. In step 1, remove stone m. In step 2, locate the k-th next stone clockwise from m and remove it. In subsequent steps, start from the slot of the stone removed in the last step, make k hops clockwise on the remaining stones and remove the one you reach. In other words, skip (k − 1) remaining stones clockwise and remove the next one. Repeat this until only one stone is left and answer its number. For example, the answer for the case n = 8, k = 5, m = 3 is 1, as shown in Figure 1.


Initial state

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Final state

Figure 1: An example game

Initial state: Eight stones are arranged on a circle.

Step 1: Stone 3 is removed since m = 3.

Step 2: You start from the slot that was occupied by stone 3. You skip four stones 4, 5, 6 and 7 (since k = 5), and remove the next one, which is 8.

Step 3: You skip stones 1, 2, 4 and 5, and thus remove 6. Note that you only count stones that are still on the circle and ignore those already removed. Stone 3 is ignored in this case.

Steps 4–7: You continue until only one stone is left. Notice that in later steps when only a few stones remain, the same stone may be skipped multiple times. For example, stones 1 and 4 are skipped twice in step 7.

Final State: Finally, only one stone, 1, is on the circle. This is the final state, so the answer is 1.

输入:

The input consists of multiple datasets each of which is formatted as follows.

n k m

The last dataset is followed by a line containing three zeros. Numbers in a line are separated by a single space. A dataset satisfies the following conditions.

2 ≤ n ≤ 10000, 1 ≤ k ≤ 10000, 1 ≤ mn

The number of datasets is less than 100.

输出:

For each dataset, output a line containing the stone number left in the final state. No extra characters such as spaces should appear in the output.

样例输入:

8 5 3
100 9999 98
10000 10000 10000
0 0 0

样例输出:

1
93
2019

解题代码:

//* @author: 82638882@163.com
import java.io.*;
class Main
{
 static int n,k,m;
 public static void main(String[] args) throws IOException
 {
	InputStreamReader is=new InputStreamReader(System.in);
	BufferedReader in=new BufferedReader(is);
	while(true)
	{
        String[] ss=in.readLine().split(" ");
	 n=Integer.parseInt(ss[0]);
	 k=Integer.parseInt(ss[1]);
	 m=Integer.parseInt(ss[2]);
	 if(n==0) break;
	 System.out.println((f(n-1)+m)%n+1);
	}
   }

 static int f(int num)
 {
	if(num==1) return 0;
	else return (k+f(num-1))%num;
 }
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。