SPOJ.COM - Thuật toán bài STPAR - Street Parade

#include <iostream>
using namespace std;

const int MAX = 1005;

int Order[MAX]; // Thứ tự ban đầu của những chiếc xe
int Stack[MAX]; // Biểu diễn ngăn xếp stack, tương ứng với đoạn đường bên cạnh
int St_size;    // Độ dài ngăn xếp
int Check;      // Lưu kết quả

int main()
{
	//freopen("input.txt","r",stdin);
	int N = 0;
	while(true)
	{
		// Nhập đầu vào là số lượng xe
		cin >> N;
		if(N == 0) break;

		for(int i = 0; i < N; i++)
			cin >> Order[i];
		St_size = 0;
		Check = true;

		// Chỉ số xe có thể đi, ban đầu có giá trị 1
		int start = 1;

		// Duyệt từng xe
		for(int i = 0; i < N; i++)
		{
			// Kiểm tra xem nếu đỉnh ngăn xếp có giá trị start thì cho đi
			while(St_size > 0 && Stack[St_size-1] == start)
			{
				St_size--;
				start++;
			}

			// Nếu đầu dãy là start thì cho đi, tăng start lên 1 đơn vị
			if(Order[i] == start) start++;
			else if (St_size > 0 && Stack[St_size-1] < Order[i])
			{
				// Nếu trường hợp này xảy ra thì chắc chắn sẽ không thoả mãn.
				// Vì trường hợp này ta sẽ phải cho điểm ở đầu dãy vào ngăn xếp
				// Mà sau khi cho xong thì tồn tại 1 điểm có giá trị nhỏ hơn
				// (ưu tiên cao hơn)
				// điểm ở đầu ngăn xếp, mà nó lại không thể đi ra được.
				Check = false;
				break;
			}
			else // Cho điểm đầu của dãy vào ngăn xếp.
			{
				Stack[St_size] = Order[i];
				St_size++;
			}
		}

		if(Check) cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}

MAX = 1005
stack = [0] * MAX

while(1):
    n = int(raw_input())
    if n == 0:
        break

    order = map(int, raw_input().split())

    st_size = 0
    check = 1
    start = 1

    for i in range(0, n):
        while (st_size > 0 and stack[st_size - 1] == start):
            st_size -= 1
            start += 1

        if order[i] == start :
            start += 1
        elif st_size > 0 and stack[st_size - 1] < order[i]:
            check = 0
            break
        else:
            stack[st_size] = order[i]
            st_size += 1

    if check == 1:
        print "yes\n"
    else:
        print "no\n"