trang chủ / đề bài / icpcwf25_a

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ị x vào đống lệch H được thực hiện theo thủ tục đệ quy sau:

  • Nếu H rỗng, biến H thành đống lệch gồm một nút duy nhất chứa x.
  • Ngược lại, gọi y là giá trị ở gốc của H.
    • Nếu y<x, đổi chỗ hai cây con của gốc, rồi chèn đệ quy x vào cây con trái mới.
    • Nếu y≥x, tạo một nút mới có giá trị x và đặt H làm cây con trái của nút này.

Ví dụ, xét đống lệch có gốc 4; con trái của 4 là 9 (với hai con 20 và 25), con phải của 4 là 5 (với con trái 6 và con phải 11, còn 11 có con trái 17). Chèn giá trị 7: tại gốc 4<7 nên đổi chỗ hai cây con của 4 (lúc này 5 thành con trái, 9 thành con phải) rồi chèn 7 vào cây con gốc 5; tại 5<7 lại đổi chỗ hai cây con của 5 (11 thành con trái, 6 thành con phải) rồi chèn 7 vào cây con gốc 11; vì 11≥7 nên tạo nút mới 7 nhận cây con gốc 11 (gồm 11 và 17) làm cây con trái. Kết quả: gốc 4 có con trái 5 và con phải 9 (với hai con 20, 25); 5 có con trái 7 và con phải 6; 7 có con trái 11; 11 có con trái 17. Các nút 4 và 5 bị đổi chỗ hai con, còn nút 11 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ừ 1 đến 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 n (1≤n≤2·105), số nút của cây. Các nút chứa các số từ 1 đến n, mỗi số đúng một lần.

Tiếp theo là n dòng, dòng thứ i chứa hai số nguyên ℓi và ri (i<ℓi≤n hoặc ℓi=0; i<ri≤n hoặc ri=0), lần lượt là giá trị của con trái và con phải của nút chứa giá trị i; giá trị 0 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

  • 1≤n≤2·105.
  • ℓi=0 hoặc i<ℓi≤n; ri=0 hoặc i<ri≤n.
  • Dữ liệu mô tả một cây nhị phân gồm đúng các nút 1,2,…,n.

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: 1 có hai con 2,3; 2 có hai con 4,5; 3 có hai con 6,7.
2
0 2
0 0
impossible Nút 1 chỉ có con phải là 2.
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 1→2→3. Chèn 2,3,1: sau 2,3 ta có 2 với con trái 3, rồi 1 nhận cả cây làm con trái. Chèn 3,2,1 cũng cho cùng cây.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0