首页 > 代码库 > UVA - 11892 ENimEN （推理）

UVA - 11892 ENimEN （推理）

2024-07-19 23:04:31   221人阅读

Description

Download as PDF


  ENimEN 

In deterministic games no chance is involved, meaning that the final result can be predicted from the initial arrangement assuming players play optimal. These games are so boring.

piloop and poopi are professional gamers. They play games only to study their algorithmic properties. Their field of expertise is boring games. One of the boring games they often play is Nim. Nim is a two-player game which is played using distinct heaps, each containing a number of objects (e.g. stones). Players take turns removing non-zero number of objects from a heap of their choice. The player who removes the last object will win.

They wonder if they can change the game to make it more fascinating. Would not that be more interesting if make the rules stricter? For example what if each player is obliged to take objects from the last non-empty heap as his opponent took objects from. And if there is no such heap, he can choose one heap freely and take objects from it.ENimEN is their new invented game based on this rule.

If you are interested in ENimEN, write a program to determine the winner given the initial arrangement assuming both players, play optimal. We believe it has also some benefits for you!

Input 

The first line contains T ( T$ \le$100), the number of test cases. Each test begins with an integerN ( N$ \le$20000) in the first line, the number of heaps followed by N integers ai (1$ \le$ai$ \le$109), are the number of objects in i-th heap.

Output 

If in the optimal strategy the first player is the winner print " poopi" (as he always plays first), otherwise print "piloop". (Quotes for clarity)

Sample Input 

2
2
1 1
4
1 2 1 1

Sample Output 

piloop
poopi题意：有N堆石子，第i堆有ai个，两个人轮流取，每次可以选择一堆石子，取非0个，多个规则是：如果对手没有把这堆取完的话，那么就要继续在这堆取思路：可以推理数只有当全部为1且为偶数个的话，后手才能赢，否则的话，先手都可以控制到只剩奇数个1的时候，都是先手赢
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 20005;

int main() {
	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		int flag = 0, a;
		for (int i = 0; i < n; i++) {
			scanf("%d", &a);
			if (a > 1)
				flag = 1;
		}
		if (!flag && n % 2 == 0)
			printf("piloop\n");
		else printf("poopi\n");
	}
	return 0;
}

 

UVA - 11892 ENimEN （推理）


联系
我们