列表

详情


NC19156. 石子游戏

描述

Alice和Bob在玩游戏,他们面前有n堆石子,对于这些石子他们可以轮流进行一些操作,不能进行下去的人则输掉这局游戏。
可以进行两种操作:
1. 把石子数为奇数的一堆石子分为两堆正整数个石子
2. 把两堆石子数为偶数的石子合并为一堆
两人都足够聪明,会按照最优策略操作。现在Alice想知道自己先手,谁能最后赢得比赛。

输入描述

第一行一个正整数n。(1<=n<=104)
接下来第二行n个正整数表示每堆石子的数量。每堆石子不超过105个。

输出描述

Alice或者Bob,表示谁能最后赢得游戏。

示例1

输入:

3
3 2 2

输出:

Alice

说明:

Alice只要现将两个石子数量为2的堆合并为一堆4个石子,Bob就只能把3分为两堆1和2,接下来Alice只要将2和4合并,Bob输掉了这局游戏。

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 504K, 提交时间: 2020-06-03 19:03:38

#include<bits/stdc++.h>
using namespace std;
int n2, n3, n, a;
int main()
{
	for(cin >> n; n--; )
	{
		cin >> a;
		if(a > 1)
			a % 2 ? n3++ : n2++;
	}
	puts(n2%2 || !n3 && !n2 ? "Bob" : "Alice");
}

C++ 解法, 执行用时: 5ms, 内存消耗: 596K, 提交时间: 2022-01-02 16:56:11

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,x,t=0;
    cin>>n;
	while(n--){
		cin>>x;
		if(x%2==0)t++;
	}
	if(t%2==0&&t)cout<<"Alice";
	else cout<<"Bob";
	return 0;
} 

Pascal(fpc 3.0.2) 解法, 执行用时: 3ms, 内存消耗: 256K, 提交时间: 2018-10-20 16:17:22

var n,i,x,s:longint;
begin
readln(n);
for i:=1 to n do
  begin
  read(x);
  if not odd(x) then s:=s+1;
  end;
s:=s-1;
if s mod 2=1 then writeln('Alice')
else writeln('Bob');
end.

pypy3(pypy3.6.1) 解法, 执行用时: 103ms, 内存消耗: 19688K, 提交时间: 2020-06-02 19:47:17

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in a:
    if i&1==0 :cnt+=1
if cnt==0 or cnt&1:print('Bob')
else:print('Alice')

Python3 解法, 执行用时: 54ms, 内存消耗: 7028K, 提交时间: 2021-07-27 22:07:35

input()

cnt = len([i for i in map(int,input().split()) if i % 2 == 0])

print('Bob') if cnt == 0 or cnt % 2 == 1 else print('Alice')

上一题