URAL 1494. Monobilliards

Author: 2015-10-23

ACM

,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1494

1494. Monobilliards

Time limit: 1.0 second
Memory limit: 64 MB
A monobilliards table set up in a gaming house of a town N turned out to be a very profitable investment, but only till the day the famous Mr. Chichikov came to the town. Chichikov was winning again and again, and the owner was counting his losses suspecting that something was wrong. But he couldn’t prove the cheating until an inspector from Petersburg arrived in the town.
The rules of monobilliards are very simple. One has to pocket successively the balls with numbers 1, 2, …, N into the only pocket (exactly in this order). While Mr. Chichikov was playing, the inspector several times came up to the table and took out from the table’s pocket the last of the pocketed balls. In the end it turned out that Chichikov had pocketed all the balls and the inspector had taken out and inspected them. The cheater claimed that he had pocketed the balls in the right order! The owner understood that this was his chance, because the inspector had to remember the order in which he had taken out the balls. But would it be so easy to prove the cheating?

Input

The first line contains the number of billiard balls N (1 ≤ N ≤ 100000). In the next N lines there are the numbers of the balls in the order in which the inspector took them out from the pocket.

Output

Output the word “Cheater” if Chichikov could not pocket all the N balls in the right order, otherwise output “Not a proof”.

Samples

input output 
2
2
1

Not a proof


3
3
1
2

Cheater

Notes

In the first sample, Chichikov could pocket the balls in the right order if the inspector took them out after Chichikov pocketed the second ball. In the second sample, Chichikov could pocket the balls in any order excepting the right one 1-2-3.
Problem Author: Alex Samsonov
Problem Source: XIII-th USU Junior Contest, October 2006

2. 思路

一种桌球游戏要求按顺序将编号为1~N的N个球击入唯一的一个袋中，在游戏进行过程中，不时地将最后一颗进球从袋中取出，根据取出球号的序列，判断玩家是否作弊（即没有按1~N的顺序击球）。

球袋看成一个栈，取出球相当于出栈，问题即为判断一个序列是否为合法出栈序列。

3. 代码

#include <cstdio>

#define MAX_LENGTH 100000

void solveUral1494_Monobilliards();

int main() {
	solveUral1494_Monobilliards();
	return 0;
}

int stack[MAX_LENGTH];
void solveUral1494_Monobilliards() {
	int n;
	scanf("%d", &n);

	int curr, top = 0, cnt = 1;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &curr);
		while (stack[top] != curr && cnt <= n) {
			stack[++top] = cnt;
			++cnt;
		}
		if (stack[top] == curr && top != 0)
			--top;
	}

	if (top != 0) {
		printf("Cheater\n");
	} else {
		printf("Not a proof\n");
	}
}