SPOJ.COM – Thuật toán bài STPAR - Street Parade
Đề bài:
Để đảm bảo rằng chiếc xe diễu hành sẽ hoạt động trở lại vào mùa hè, mỗi năm ban tổ chức quyết định một thứ tự xác định trước cho việc trang trí những chiếc xe. Kinh nghiệm dạy họ rằng nên giữ một cạnh trống để có thể đưa những chiếc xe vào theo đúng thứ tự.
Đường bên cạnh là rất nhỏ. Vì vậy, 2 chiếc xe không thể cùng vượt qua. Do đó, những chiếc xe nào vào sau sẽ phải ra trước. Bởi vì các xe đi rất gần nhau nên chúng không thể quay đầu hay vào trở lại. Bạn được cho thứ tự đến của những chiếc xe. Viết chương trình kiểm tra xem các chiếc xe có thể đi vào theo đúng thứ tự mà ban tổ chức quyết định hay không.
Đầu vào:
Có nhiều test case. Dòng đầu tiên của mỗi test case là một số n, số lượng của những chiếc xe. Dòng thứ 2 chứa các số từ 1 đến n, sắp xếp theo tứ tự ngẫu nhiên. Tất cả các chữ số được phân cách bởi dấu cách. Những số này biểu diễn thứ tự, mà những chiếc xe đi đến con đường. Số xe là không lớn hơn 1000. Kết thúc của đầu vào là số 0.
Đầu ra:
Với mỗi test case , in ra 1 dòng duy nhất là "yes" nếu như thoả mãn, ngược lại thì in ra là "no".
Ví dụ:
Đầu vào:
5
5 1 2 4 3
0
Đầu ra:
yes
Giải thích:
Ban đầu:
Xe có thể thay đổi như sau:
Quá trình kết thúc.
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/STPAR/
Phân tích:
- Ở đây, tôi sẽ dùng ngăn xếp stack để giải quyết bài toán. Bài toán này có thể xếp vào dạng sử dụng [thuật toán tham lam Greedy.]/category/tham-lam-greedy/)
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #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; | |
| } |
Code Python:
| 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" |
Code by Phạm Văn Lâm.