ccf1202-游戏

发表于 | 更新于 | 分类于

问题描述

有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。

游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。

例如，当n=5, k=2时：

1号小朋友报数1；

2号小朋友报数2淘汰；

3号小朋友报数3；

4号小朋友报数4淘汰；

5号小朋友报数5；

1号小朋友报数6淘汰；

3号小朋友报数7；

5号小朋友报数8淘汰；

3号小朋友获胜。

给定n和k，请问最后获胜的小朋友编号为多少？

输入格式

输入一行，包括两个整数n和k，意义如题目所述。

输出格式

　　输出一行，包含一个整数，表示获胜的小朋友编号。

样例输入

5 2

样例输出

3

样例输入

7 3

样例输出

4

数据规模和约定

对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。

问题分析

用队列比较简单

代码

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
package oj;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class ccf1 {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int n, k;
		int tmp=1;//记录下一个要数的数
		int result=-1;
       Scanner sc = new Scanner(System.in);
        n = sc.nextInt();//
        k =sc.nextInt();
		Queue<Integer> cf=new LinkedList<Integer>();
		for (int i = 0; i < n; i++) {
			cf.offer(i+1);
//			tmp++;
		}
		if(n==1){
			result=cf.peek();
			System.out.println(result);
			
			
		}else{
		while(cf.size()>1){//循环往复的问题,,这里第一轮忘记淘汰了
//			System.out.println(cf.size());
			if(tmp%k==0||tmp%10==k){//可以被淘汰
				cf.poll();
				tmp++;}
			else{
				result=cf.poll();
				cf.offer(result);//不淘汰
				tmp++;
			}
			
		}
		System.out.println(cf.peek());//最后这里开始输的是result  TAT,所以细心很，很，很重要
		}
	}

}