Gym 100952G&&2015 HIAST Collegiate Programming Contest G. The jar of divisors【简单博弈】

G. The jar of divisors

time limit per test:2 seconds

memory limit per test:64 megabytes

input:standard input

output:standard output

Alice and Bob play the following game. They choose a number N to play with. The rules are as follows:

- They write each number from 1 to N on a paper and put all these papers in a jar.

- Alice plays first, and the two players alternate.

- In his/her turn, a player can select any available number M and remove its divisors including M.

- The person who cannot make a move in his/her turn wins the game.

Assuming both players play optimally, you are asked the following question: who wins the game?

Input

The first line contains the number of test cases T (1  ≤  T  ≤  20). Each of the next T lines contains an integer (1  ≤  N  ≤  1,000,000,000).

Output

Output T lines, one for each test case, containing Alice if Alice wins the game, or Bob otherwise.

Examples

Input

2
5
1

Output

Alice
Bob

题目链接:http://codeforces.com/gym/100952/problem/G

题意:有一个容器里装着1-n n个数,A和B每次任意说一个数m,那么他要拿走容器里m的所有因子,如果谁拿空了容器,那么他输了,求先手赢还是后手赢

思路:只有1是后手赢,因为1只能拿一次,大于1的情况,假设a和b都不是聪明的,假设先手出x,后手出y,结果是后手赢,那么现在a和b都是聪明的,先手可以直接出x*y(即先手可以复制后手的操作,先手的操作可以包括后手的操作),则可以赢后手,所以大于1的情况一定是先手赢!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 inline int read()
 4 {
 5     int x=0,f=1;
 6     char ch=getchar();
 7     while(ch<'0'||ch>'9')
 8     {
 9         if(ch=='-')
10             f=-1;
11         ch=getchar();
12     }
13     while(ch>='0'&&ch<='9')
14     {
15         x=x*10+ch-'0';
16         ch=getchar();
17     }
18     return x*f;
19 }
20 inline void write(int x)
21 {
22     if(x<0)
23     {
24         putchar('-');
25         x=-x;
26     }
27     if(x>9)
28         write(x/10);
29     putchar(x%10+'0');
30 }
31 int main()
32 {
33     int T;
34     T=read();
35     while(T--)
36     {
37         int n;
38         n=read();
39         if(n>1)
40             printf("Alice\n");
41         else printf("Bob\n");
42     }
43     return 0;
44 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1212: [HNOI2004]L语言

1212: [HNOI2004]L语言 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 643  Solved...

2945
来自专栏积累沉淀

JavaScript面向对象与原型

javaScript有两种开发模式:1.函数式(过程化),2.面向对象(OOP)。面向对象的语言有一个标志,那就是类的概念,而通过类可以创建任意多个具有相同属性...

23710
来自专栏简书专栏

Numpy入门2

标题中的英文首字母大写比较规范,但在python实际使用中均为小写。 2018年7月26日笔记

1303
来自专栏技术沉淀

Python: 函数式编程

1654
来自专栏杂七杂八

numpy科学计算包的使用1

Numpy是Python的一个科学计算的库,提供了矩阵运算的功能,其一般与Scipy、matplotlib一起使用。其实,list已经提供了类似于矩阵的表示形...

4215
来自专栏数据结构与算法

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

762
来自专栏小樱的经验随笔

UVA 11636-Hello World!(水题,猜结论) UVA11636-Hello World!

UVA11636-Hello World! Time limit: 1.000 seconds When you first made the computer ...

3634
来自专栏数据结构与算法

1191 数轴染色

1191 数轴染色 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 在一条数轴...

3719
来自专栏mathor

位与进制

 这里我假设读者有二进制的思维,知道(3)~10~=(011)~2~将十进制转换为二进制的方法

541
来自专栏Play & Scala 技术分享

酷炫的一行代码 - Scala就是这么任性!

3677

扫码关注云+社区

领取腾讯云代金券