Educational Codeforces Round 68 D.1-2-K Game

D. 1-2-K Game

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Alice and Bob play a game. There is a paper strip which is divided into n + 1 cells numbered from left to right starting from 0. There is a chip placed in the n-th cell (the last one).

Players take turns, Alice is first. Each player during his or her turn has to move the chip 1, 2 or k cells to the left (so, if the chip is currently in the cell i, the player can move it into cell i - 1, i - 2 or i - k). The chip should not leave the borders of the paper strip: it is impossible, for example, to move it k cells to the left if the current cell has number i < k. The player who can’t make a move loses the game.

Who wins if both participants play optimally?

Alice and Bob would like to play several games, so you should determine the winner in each game.

Input

The first line contains the single integer T (1 ≤ T ≤ 100) — the number of games. Next T lines contain one game per line. All games are independent.

Each of the next T lines contains two integers n and k (0 ≤ n ≤ 109, 3 ≤ k ≤ 109) — the length of the strip and the constant denoting the third move, respectively.

Output

For each game, print Alice if Alice wins this game and Bob otherwise.

Example

input

4
0 3
3 3
3 4
4 4

output

Bob
Alice
Bob
Alice

这题是一个博弈论题,意思大概为n米长,每次可以移动1,2,k米不能移动的人输。这题可以用sg函数进行打表得出规律。最后能够得出当k%3=0时会对原博弈结果产生影响。否则就是和只有能移动1,2米的结果相同,最终结果可以通过%k+1进行分类,能%3的k影响结果只是在k是能影响,其它的仍然可以通过%3来进行结果的判断。
AC代码java

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	static StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pr = new PrintWriter(new BufferedOutputStream(System.out));
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws NumberFormatException, IOException {
		int arr[] = new int[10000];
		int q = sc.nextInt();
		while (q-- > 0) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			if(k%3==0) {
				n %= k+1;
				if(n==k) {
					System.out.println("Alice");
				}else {
					if(n%3==0) {
						System.out.println("Bob");					
					}else {
						System.out.println("Alice");
					}
				}
			}else {
				if(n%3==0) {
					System.out.println("Bob");					
				}else {
					System.out.println("Alice");
				}
			}
			
		}

	}

	private static int nextInt() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int) st.nval;
	}
}

全部评论

相关推荐

风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
05-27 14:57
西北大学 golang
强大的社畜在走神:27届真不用急,可以搞点项目、竞赛再沉淀沉淀,我大二的时候还在天天打游戏呢
投递华为等公司10个岗位
点赞 评论 收藏
分享
07-18 18:45
已编辑
中山职业技术学院 Java
投递TP-LINK等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务