Timus #1494. Monobilliards – Pancake's Personal Website

题目：有n个数按照1,2,3…n的顺序入栈，在每一步入栈的过程中（严格按照入栈顺序，即从先到后），可以按顺序出栈（严格按照出栈顺序，即从后到先），如果可以得到题目所input的顺序，则输出not a proof，否则为cheater。

例子讲解：
input:
4
1 3 2 4
output:
not a proof
题目为1,2,3,4入栈顺序
(1). 1入栈，1出栈；
(2). 2,3入栈，3,2出栈；
(3). 4入栈，4出栈
存在这种可能，输出not a proof

input:
3
3 1 2
output:
cheater
题目为1,2,3入栈顺序
(1). 1,2,3入栈，3 出栈
因为接下来出栈必须为2，所以不存在这种可能，输出cheater

解析：堆栈

Using the idea of stack. Input numbers (by order 1,2,3,…,n) to stack one by one, remove it out of the stack (by input number’s order) in each insertion. See if the stack is empty in the end.

#include<iostream>
#include<vector>
using namespace std;


int main() {
    int n, temp;
    cin >> n >> temp;
    vector<int>arr;
    for (int i = 1; i <= n; i++) {
        arr.push_back(i);
        while (!arr.empty() && arr[arr.size() - 1] == temp) {
            if (i == n && arr.size() == 1) {
                arr.pop_back();
                break;
            }
            cin >> temp;
            arr.pop_back();
        }
    }
    if (arr.empty()) cout << "Not a proof" << endl;
    else cout << "Cheater" << endl;
    return 0;
}

#include<iostream>

#include<vector>

using namespace std;

int main() {

int n, temp;

cin >> n >> temp;

vector<int>arr;

for (int i = 1; i <= n; i++) {

arr.push_back(i);

while (!arr.empty() && arr[arr.size() - 1] == temp) {

if (i == n && arr.size() == 1) {

arr.pop_back();

break;

}

cin >> temp;

arr.pop_back();

}

if (arr.empty()) cout << "Not a proof" << endl;

else cout << "Cheater" << endl;

return 0;

}

发表回复 取消回复

发表回复取消回复