Lâu rồi không thấy gì hay trên DNH nên mình mạn phép mang 1 cái đề trên mạng về chia sẻ với mấy bạn để chơi với nhau.
Đề bài:
Cho một dãy số ngẫu nhiên (không trùng nhau, bao gồm cả số âm và số dương) trong 1 stack (stack A), hãy sắp xếp chúng với sự giúp đỡ của stack phụ(stack B, stack này khởi tạo empty) với các phép toán đc liệt kê dưới đây:
- sa : swap a - Hoán đổi hai phần tử đầu tiên ở đỉnh stack A. (Không làm gì nếu chỉ có một hoặc không có phần tử).
- sb : swap b - Hoán đổi hai phần tử đầu tiên ở đỉnh stack B. (Không làm gì nếu chỉ có một hoặc không có phần tử).
- ss : sa và sb cùng một lúc.
- pa : push a - Lấy phần tử đầu tiên ở đỉnh B và đặt nó ở đỉnh A. Không làm gì nếu B trống.
- pb : push b - Lấy phần tử đầu tiên ở đỉnh A và đặt nó ở đỉnh B. Không làm gì nếu A trống.
- ra : rotate a - Dịch lên tất cả các phần tử của stack A 1 vị trí. Phần tử đầu tiên trở thành phần tử cuối cùng.
- rb : rotate b - Dịch lên tất cả các phần tử của stack B 1 vị trí. Phần tử đầu tiên trở thành phần tử cuối cùng.
- rr : ra và rb cùng một lúc.
- rra : reverse rotate a - Dịch xuống tất cả các phần tử của stack A 1 vị trí. Phần tử cuối cùng trở thành phần tử đầu tiên.
- rrb : reverse rotate b - Dịch xuống tất cả các phần tử của stack B 1 vị trí. Phần tử cuối cùng trở thành phần tử đầu tiên.
- rrr : rra và rrb cùng một lúc.
Kết quả cuối cùng là stack B rỗng, và stack A được sắp xếp tăng dần
(1) Vì đề này phổ biến trên google nên chắc chắn là mình ko post lên hỏi bài
(2) Vì (1) nên bạn không nên google để tìm cách giải, tự động suy nghĩ cho nó vui
(3) Giới hạn:
Với 3 số, không quá 3 bước.
Với 5 số, không quá 12 bước.
Với 100 số:
- 5 điểm nếu số bước ít hơn 700.
- 4 điểm nếu số bước ít hơn 900.
- 3 điểm nếu số bước ít hơn 1100.
- 2 điểm nếu số bước ít hơn 1300.
- 1 điểm nếu số bước ít hơn 1500.
Với 500 số:
- 5 điểm nếu số bước ít hơn 5500.
- 4 điểm nếu số bước ít hơn 7000.
- 3 điểm nếu số bước ít hơn 8500.
- 2 điểm nếu số bước ít hơn 10000.
- 1 điểm nếu số bước ít hơn 11500.
(4): Nếu các bạn thấy vui thì mỗi tháng mình sẽ kiếm một cái về
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?