Suy luận lệch
Đề bài
Mô tả
Chuyện dưới đây dựa trên một câu chuyện có thật, tên các nhân vật đã được thay đổi, bởi vì... à thì, chuyện kiểu này lúc nào người ta cũng đổi tên.
Giáo sư Taylor Swift đang chấm một bài tập về đống lệch số nguyên (skew heap). Một đống lệch là một cây nhị phân, mỗi nút lưu một số nguyên, sao cho giá trị ở mỗi nút nhỏ hơn hoặc bằng giá trị ở mọi nút con của nó. Lưu ý rằng đống lệch không nhất thiết là cây nhị phân hoàn hảo: cây con trái và/hoặc cây con phải của một nút bất kỳ có thể rỗng.
Việc chèn một giá trị vào đống lệch được thực hiện theo thủ tục đệ quy sau:
- Nếu rỗng, biến thành đống lệch gồm một nút duy nhất chứa .
- Ngược lại, gọi là giá trị ở gốc của .
- Nếu , đổi chỗ hai cây con của gốc, rồi chèn đệ quy vào cây con trái mới.
- Nếu , tạo một nút mới có giá trị và đặt làm cây con trái của nút này.
Ví dụ, xét đống lệch có gốc ; con trái của là (với hai con và ), con phải của là (với con trái và con phải , còn có con trái ). Chèn giá trị : tại gốc nên đổi chỗ hai cây con của (lúc này thành con trái, thành con phải) rồi chèn vào cây con gốc ; tại lại đổi chỗ hai cây con của ( thành con trái, thành con phải) rồi chèn vào cây con gốc ; vì nên tạo nút mới nhận cây con gốc (gồm và ) làm cây con trái. Kết quả: gốc có con trái và con phải (với hai con , ); có con trái và con phải ; có con trái ; có con trái . Các nút và bị đổi chỗ hai con, còn nút trở thành con trái của nút mới chèn.
Quay lại với Giáo sư Swift. Bài tập bà giao yêu cầu sinh viên vẽ đống thu được khi chèn lần lượt một hoán vị cho trước của các số từ đến , theo đúng thứ tự đã cho, vào một đống ban đầu rỗng. Thật bất ngờ, một số sinh viên trả lời sai! Điều đó khiến Giáo sư Swift tự hỏi: với một đống cho trước, có hoán vị đầu vào nào tạo ra đúng đống này không? Nếu có, hoán vị đầu vào nhỏ nhất và lớn nhất theo thứ tự từ điển là gì?
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số nút của cây. Các nút chứa các số từ đến , mỗi số đúng một lần.
Tiếp theo là dòng, dòng thứ chứa hai số nguyên và ( hoặc ; hoặc ), lần lượt là giá trị của con trái và con phải của nút chứa giá trị ; giá trị nghĩa là con tương ứng không tồn tại. Dữ liệu đảm bảo mô tả một cây nhị phân.
Dữ liệu ra
In ra hoán vị đầu vào nhỏ nhất theo thứ tự từ điển tạo ra đúng cây đã cho theo cách chèn của đống lệch, tiếp theo là hoán vị đầu vào lớn nhất theo thứ tự từ điển như vậy, mỗi hoán vị trên một dòng, các số cách nhau bởi dấu cách. Hai hoán vị này có thể trùng nhau, khi đó bạn vẫn phải in cả hai.
Nếu không có hoán vị đầu vào nào tạo ra cây đã cho, in ra impossible.
Ràng buộc
- .
- hoặc ; hoặc .
- Dữ liệu mô tả một cây nhị phân gồm đúng các nút .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 2 3 4 5 6 7 0 0 0 0 0 0 0 0 |
1 3 2 7 5 6 4 7 1 5 3 2 6 4 |
Cây nhị phân đầy đủ ba tầng: có hai con ; có hai con ; có hai con . |
| 2 0 2 0 0 |
impossible | Nút chỉ có con phải là . |
| 3 2 0 3 0 0 0 |
2 3 1 3 2 1 |
Cây là một đường đi xuống bên trái . Chèn : sau ta có với con trái , rồi nhận cả cây làm con trái. Chèn cũng cho cùng cây. |
Bình luận