Pop Sequence

27691 단어 데이터 구조
Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.
Output Specification:
For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.
Sample Input:
5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2
Sample Output:
YES NO NO YES NO
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 

typedef long long ll;
const double PI = acos(-1);
template <typename T> 
void read(T &val) { 
	T x = 0; 
	int bz = 1; 
	char c; 
	
	for (c = getchar(); (c<'0' || c>'9') && c != '-'; 
	c = getchar()); 
	
	if (c == '-') { 
		bz = -1; 
		c = getchar(); 
	}
	
	for (; c >= '0' && c <= '9'; c = getchar()) 
		x = x * 10 + c - 48; 
		
	val = x * bz; 
}

void put(int x){  
    static char	s[20];  
    int bas;  
  
    if(x < 0) {  
        putchar('-');  
        x = -x;  
    }  
    
    if(x == 0) {  
        putchar('0');  
        return;  
    }  
    
    bas = 0;  
    for(;x;x/=10) 
		s[bas++] = x%10+'0';  
		
    for(;bas--;) 
		putchar(s[bas]);  
}  

const int MAXN = 1e3 + 5;
int a[MAXN];
std::stack<int> stk;
std::stack<int> stk2;
std::queue<int> que;

int main() {
	int m;		// Stack size
	int n;		// Number length
	int k;		// Test case
	
	std::cin >> m >> n >> k;
	
	while (k--) {		
		while (!que.empty()) {
			que.pop();
		}
		
		while (!stk.empty()) {
			stk.pop();
		}
		
		while (!stk2.empty()) {
			stk2.pop();
		}
		
		for (int i=n; i>0; i--) {
			stk.push(i); 
		}
		
		for (int i=0; i<n; i++) {
			int t;
			std::cin >> t;
			que.push(t); 	
		}
		
		while (que.size()) {
			if (!stk2.empty()) {
				if (que.empty()) {
					std::cout << "YES
"
; goto A; } if (stk2.top() == que.front()) { stk2.pop(); que.pop(); } else { if (!stk.empty()) { stk2.push(stk.top()); stk.pop(); if (stk2.size() > m) { std::cout << "NO
"
; goto A; } } else { if (stk2.top() != que.front()) { std::cout << "NO
"
; goto A; } else { stk2.pop(); que.pop(); } } } } else { if (stk.empty()) { if(que.empty()) { std::cout << "YES
"
; goto A; } else { std::cout << "NO
"
; goto A; } } else { if (stk.top() != que.front()) { stk2.push(stk.top()); stk.pop(); if (stk2.size() > m) { std::cout << "NO
"
; goto A; } } else { stk.pop(); que.pop(); } } } } if (stk.empty() && stk2.empty() && que.empty()) { std::cout << "YES
"
; } else { std::cout << "NO
"
; } A: {}; } return 0; }

좋은 웹페이지 즐겨찾기