[UVA] 11995 - I Can Guess the Data Structure! [STL 적용]
11626 단어 struct
11995 - I Can Guess the Data Structure!
Time limit: 1.000 seconds
Problem I
I Can Guess the Data Structure!
There is a bag-like data structure, supporting two operations: 1 x
Throw an element x into the bag. 2
Take out an element from the bag.
Given a sequence of operations with return values, you're going to guess the data structure. It is a stack (Last-In, First-Out), a queue (First-In, First-Out), a priority-queue (Always take out larger elements first) or something else that you can hardly imagine!
Input
There are several test cases. Each test case begins with a line containing a single integer n (1<=n<=1000). Each of the next n lines is either a type-1 command, or an integer 2 followed by an integer x. That means after executing a type-2 command, we get an element x without error. The value of x is always a positive integer not larger than 100. The input is terminated by end-of-file (EOF). The size of input file does not exceed 1MB.
Output
For each test case, output one of the following: stack
It's definitely a stack. queue
It's definitely a queue. priority queue
It's definitely a priority queue. impossible
It can't be a stack, a queue or a priority queue. not sure
It can be more than one of the three data structures mentioned above.
Sample Input
6
1 1
1 2
1 3
2 1
2 2
2 3
6
1 1
1 2
1 3
2 3
2 2
2 1
2
1 1
2 2
4
1 2
1 1
2 1
2 2
7
1 2
1 5
1 1
1 3
2 5
1 4
2 4
Output for the Sample Input
queue
not sure
impossible
stack
priority queue
Rujia Liu's Present 3: A Data Structure Contest Celebrating the 100th Anniversary of Tsinghua UniversitySpecial Thanks: Yiming LiNote: Please make sure to test your program with the gift I/O files before submitting!
문제 풀이: STL에서queue,stack,priorityqueue의 사용.
코드:
1 #include<cstdio>
2 #include<cstring>
3 #include<stdbool.h>
4 #include<cmath>
5 #include<queue>
6 #include<stack>
7 #include<algorithm>
8
9
10 #define rep(i,a,b) for(i=(a);i<=(b);i++)
11 #define red(i,a,b) for(i=(a);i>=(b);i--)
12 #define clr(x,y) memset(x,y,sizeof(x))
13 #define sqr(x) ((x)*(x))
14
15 using namespace std;
16
17 int i,j,x,y,pri,qui,sti;
18
19 void check()
20 {
21 if(qui==1 && pri==0 && sti==0) printf("queue
");
22 else
23 if(qui==0 && pri==1 && sti==0) printf("priority queue
");
24 else
25 if(qui==0 && pri==0 && sti==1) printf("stack
");
26 else
27 if(qui==0 && pri==0 && sti==0) printf("impossible
");
28 else
29 printf("not sure
");
30 }
31
32 int main()
33 {
34 int T;
35
36
37
38 while(scanf("%d",&T)!=EOF) {
39 pri=qui=sti=1;
40
41 queue <int> Q;
42 stack <int> S;
43 priority_queue <int> prQ;
44
45 while(T--) {
46 scanf("%d%d",&x,&y);
47 if(x==1) {
48 Q.push(y);
49 S.push(y);
50 prQ.push(y);
51 }
52 else {
53
54 if(qui==1) {
55 if(Q.empty() || Q.front()!=y) qui=0;
56 if(!Q.empty()) Q.pop();
57 }
58
59 if(sti==1) {
60 if(S.empty() || S.top()!=y) sti=0;
61 if(!S.empty()) S.pop();
62 }
63
64 if(pri==1) {
65 if(prQ.empty() || prQ.top()!=y) pri=0;
66 if(!prQ.empty()) prQ.pop();
67 }
68 }
69 }
70
71 check();
72 }
73
74 return 0;
75 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스
은 접근자 메서드가 있는 속성 모음입니다.
클래스를 명시적으로 작성할 필요 없이.
Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다.
각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
I Can Guess the Data Structure!
There is a bag-like data structure, supporting two operations:
1 x
Throw an element x into the bag.
2
Take out an element from the bag.
Given a sequence of operations with return values, you're going to guess the data structure. It is a stack (Last-In, First-Out), a queue (First-In, First-Out), a priority-queue (Always take out larger elements first) or something else that you can hardly imagine!
Input
There are several test cases. Each test case begins with a line containing a single integer n (1<=n<=1000). Each of the next n lines is either a type-1 command, or an integer 2 followed by an integer x. That means after executing a type-2 command, we get an element x without error. The value of x is always a positive integer not larger than 100. The input is terminated by end-of-file (EOF). The size of input file does not exceed 1MB.
Output
For each test case, output one of the following:
stack
It's definitely a stack.
queue
It's definitely a queue.
priority queue
It's definitely a priority queue.
impossible
It can't be a stack, a queue or a priority queue.
not sure
It can be more than one of the three data structures mentioned above.
Sample Input
6
1 1
1 2
1 3
2 1
2 2
2 3
6
1 1
1 2
1 3
2 3
2 2
2 1
2
1 1
2 2
4
1 2
1 1
2 1
2 2
7
1 2
1 5
1 1
1 3
2 5
1 4
2 4
Output for the Sample Input
queue
not sure
impossible
stack
priority queue
Rujia Liu's Present 3: A Data Structure Contest Celebrating the 100th Anniversary of Tsinghua UniversitySpecial Thanks: Yiming LiNote: Please make sure to test your program with the gift I/O files before submitting!
문제 풀이: STL에서queue,stack,priorityqueue의 사용.
코드:
1 #include<cstdio>
2 #include<cstring>
3 #include<stdbool.h>
4 #include<cmath>
5 #include<queue>
6 #include<stack>
7 #include<algorithm>
8
9
10 #define rep(i,a,b) for(i=(a);i<=(b);i++)
11 #define red(i,a,b) for(i=(a);i>=(b);i--)
12 #define clr(x,y) memset(x,y,sizeof(x))
13 #define sqr(x) ((x)*(x))
14
15 using namespace std;
16
17 int i,j,x,y,pri,qui,sti;
18
19 void check()
20 {
21 if(qui==1 && pri==0 && sti==0) printf("queue
");
22 else
23 if(qui==0 && pri==1 && sti==0) printf("priority queue
");
24 else
25 if(qui==0 && pri==0 && sti==1) printf("stack
");
26 else
27 if(qui==0 && pri==0 && sti==0) printf("impossible
");
28 else
29 printf("not sure
");
30 }
31
32 int main()
33 {
34 int T;
35
36
37
38 while(scanf("%d",&T)!=EOF) {
39 pri=qui=sti=1;
40
41 queue <int> Q;
42 stack <int> S;
43 priority_queue <int> prQ;
44
45 while(T--) {
46 scanf("%d%d",&x,&y);
47 if(x==1) {
48 Q.push(y);
49 S.push(y);
50 prQ.push(y);
51 }
52 else {
53
54 if(qui==1) {
55 if(Q.empty() || Q.front()!=y) qui=0;
56 if(!Q.empty()) Q.pop();
57 }
58
59 if(sti==1) {
60 if(S.empty() || S.top()!=y) sti=0;
61 if(!S.empty()) S.pop();
62 }
63
64 if(pri==1) {
65 if(prQ.empty() || prQ.top()!=y) pri=0;
66 if(!prQ.empty()) prQ.pop();
67 }
68 }
69 }
70
71 check();
72 }
73
74 return 0;
75 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.