Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 1835 | Accepted: 538 |
Description
Vladimir worked for years making matrioshkas, those nesting dolls that certainly represent truly Russian craft. A matrioshka is a doll that may be opened in two halves, so that one finds another doll inside. Then this doll may be opened to find another one inside it. This can be repeated several times, till a final doll – that cannot be opened – is reached.
Recently, Vladimir realized that the idea of nesting dolls might be generalized to nesting toys. Indeed, he has designed toys that contain toys but in a more general sense. One of these toys may be opened in two halves and it may have more than one toy inside it. That is the new feature that Vladimir wants to introduce in his new line of toys.
Vladimir has developed a notation to describe how nesting toys should be constructed. A toy is represented with a positive integer, according to its size. More precisely: if when opening the toy represented by m we find the toys represented by n_{1}, n_{2}, …, n_{r}, it must be true that n_{1} + n_{2} + … + n_{r} < m. And if this is the case, we say that toy m contains directly the toys n_{1}, n_{2}, …, n_{r}. It should be clear that toys that may be contained in any of the toys n_{1}, n_{2}, …, n_{r} are not considered as directly contained in the toy m.
A generalized matrioshka is denoted with a non-empty sequence of non zero integers of the form:
a_{1} | a_{2} | … | a_{N} |
such that toy k is represented in the sequence with two integers −k and k, with the negative one occurring in the sequence first that the positive one.
For example, the sequence
−9 | −7 | −2 | 2 | −3 | −2 | −1 | 1 | 2 | 3 | 7 | 9 |
represents a generalized matrioshka conformed by six toys, namely, 1, 2 (twice), 3, 7 and 9. Note that toy 7 contains directly toys 2 and 3. Note that the first copy of toy 2 occurs left from the second one and that the second copy contains directly a toy 1. It would be wrong to understand that the first −2 and the last 2 should be paired.
On the other hand, the following sequences do not describe generalized matrioshkas:
−9 | −7 | −2 | 2 | −3 | −1 | −2 | 2 | 1 | 3 | 7 | 9 |
because toy 2 is bigger than toy 1 and cannot be allocated inside it.
−9 | −7 | −2 | 2 | −3 | −2 | −1 | 1 | 2 | 3 | 7 | −2 | 2 | 9 |
because 7 and 2 may not be allocated together inside 9.
−9 | −7 | −2 | 2 | −3 | −1 | −2 | 3 | 2 | 1 | 7 | 9 |
because there is a nesting problem within toy 3.
Your problem is to write a program to help Vladimir telling good designs from bad ones.
Input
The input file contains several test cases, each one of them in a separate line. Each test case is a sequence of non zero integers, each one with an absolute value less than 10^{7}.
Output
Output texts for each input case are presented in the same order that input is read.
For each test case the answer must be a line of the form
:-) Matrioshka!
if the design describes a generalized matrioshka. In other case, the answer should be of the form
:-( Try again.
Sample Input
1 2 3 4 5 6 7 |
-9 -7 -2 2 -3 -2 -1 1 2 3 7 9 -9 -7 -2 2 -3 -1 -2 2 1 3 7 9 -9 -7 -2 2 -3 -1 -2 3 2 1 7 9 -100 -50 -6 6 50 100 -100 -50 -6 6 45 100 -10 -5 -2 2 5 -4 -3 3 4 10 -9 -5 -2 2 5 -4 -3 3 4 9 |
Sample Output
1 2 3 4 5 6 7 |
:-) Matrioshka! :-( Try again. :-( Try again. :-) Matrioshka! :-( Try again. :-) Matrioshka! :-( Try again. |
Source
真心烦这种balabala一大堆的题目…
题目的要求是这样的(用盒子来打比方说明, 一对正负数就是一个盒子)
- 一个盒子只能装比它小的盒子.
- 一个盒子里面装的盒子的大小之和不能大于或等于盒子(盒子装的盒子里面的盒子不算).
- 最大的盒子的尺寸型号只能有一个, 比如-1 1 -2 2不合法, 但是-2 2 -2 2是合法的.
一开始用了stack, 写的乱七八糟的, 怒送3WA,后来全部推了重新写了一边果断1A.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
/* * File Name: uvaoj11111.cpp * Author: razrLeLe * Mail: razrlele@outlook.com * Homepage: https://yueyu.io * Created Time: 2014年12月26日 星期五 16时14分23秒 */ #include "vector" #include "set" #include "deque" #include "queue" #include "algorithm" #include "functional" #include "iostream" #include "cstdio" #include "cmath" #include "cstdlib" #include "string" #include "cstring" #include "string.h" #include "map" #include "cctype" #include "list" using namespace std; #define INF 0x3f3f3f3f #define LOCAL const int maxn = 10010; int stack[maxn], sum[maxn], input[maxn];//sum就是栈里面的所有盒子里层的盒子大小之和. int inputnum, stacknum; bool test() { stacknum = 1; stack[0] = input[0]; memset(sum, 0, sizeof(sum)); for(int i = 1; i < inputnum; i++) { if(input[i] < 0) { if(input[i] <= stack[stacknum-1] && stacknum) { return false; } else { if(stacknum) { sum[stacknum-1] += input[i]; if(sum[stacknum-1] <= stack[stacknum-1]) return false; } stack[stacknum++] = input[i]; } } else { if(input[i]+stack[stacknum-1]) return false; else { stacknum--; sum[stacknum] = 0; } } } if(!stacknum) return true; return false; } int main() { #ifdef LOCAL freopen("/home/razrlele/build/data.txt", "r", stdin); freopen("/home/razrlele/build/out.txt", "w", stdout); #endif int in; stacknum = 0; while(~scanf("%d", &in)) { input[inputnum++] = in; if(getchar() == '\n') { if(inputnum%2 || input[0]>0)//奇数个或者首个不为负数的果断直接输出Try agagin. { printf(":-( Try again.\n"); } else if(test()) { printf(":-) Matrioshka!\n"); } else { printf(":-( Try again.\n"); } inputnum = 0; } } return 0; } |