随笔-68  评论-10  文章-0  trackbacks-0
UVa 11111 - Generalized Matrioshkas
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2052
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <cmath>
#include <cstring>
using namespace std;

struct toy
{
    int x;
    int c;
    toy(int i = 0, int j = 0): x(i), c(j) {}
};
int n;
int a[500000];

bool isMatKa()
{
    stack<toy> st;
    for(int i = 0; i < n; ++i)
    {
        if(a[i] < 0)
            st.push(toy(a[i], a[i]));
        else
        {
            if(st.size() && st.top().x + a[i] == 0)
            {
                st.pop();
                if(st.size())
                {
                    toy t = st.top();
                    st.pop();
                    t.c += a[i];
                    if(t.c >= 0) return false;
                    st.push(t);
                }
                else if(i + 1 < n)
                    return false;
            }
            else return false;
        }
    }
    return st.empty();
}

int main()
{
    string s;
    while(getline(cin, s))
    {
        n = 0;
        stringstream str(s);
        while(str >> a[n]) ++n;
        bool isMK = true;
        isMK = isMatKa();
        if(!isMK)
            cout << ":-( Try again." << endl;
        else
            cout << ":-) Matrioshka!" << endl;
    }
    return 0;
}
posted on 2011-11-23 13:27 wuxu 阅读(528) 评论(0)  编辑 收藏 引用 所属分类: 模拟

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 wuxu