Hàm trần nhà
Đề bài
Mô tả
Công ty Advanced Ceiling Manufacturers (ACM) đang phân tích các tính chất của dòng sản phẩm trần nhà mới mang tên Incredibly Collapse-Proof Ceilings (ICPC). Mỗi tấm trần ICPC gồm lớp vật liệu, mỗi lớp có một giá trị độ chống sập khác nhau (là một số nguyên dương). Phép phân tích mà ACM muốn thực hiện sẽ lấy các giá trị độ chống sập của các lớp, lưu chúng vào một cây nhị phân tìm kiếm, rồi kiểm tra xem hình dạng của cây này có liên quan gì tới chất lượng của cả tấm trần hay không. Vì, chà, tại sao lại không chứ?
Cụ thể, ACM lấy các giá trị độ chống sập của các lớp theo thứ tự từ lớp trên cùng xuống lớp dưới cùng, và lần lượt chèn từng giá trị vào một cây. Quy tắc chèn một giá trị như sau:
- Nếu cây rỗng, trở thành gốc của cây.
- Nếu cây khác rỗng, so sánh với gốc của cây. Nếu nhỏ hơn thì chèn vào cây con trái của gốc, ngược lại chèn vào cây con phải.
ACM có một tập các nguyên mẫu trần nhà và muốn phân tích chúng bằng cách thử làm sập chúng. Công ty muốn gom mỗi nhóm nguyên mẫu có cây cùng hình dạng lại để phân tích chung.
Ví dụ, xét năm nguyên mẫu, mỗi nguyên mẫu có ba lớp, như trong ví dụ thứ nhất và hình dưới đây. Nguyên mẫu thứ nhất có lớp trên cùng với độ chống sập , lớp giữa và lớp dưới cùng . Nguyên mẫu thứ hai có các lớp với độ chống sập , và , vậy mà hai nguyên mẫu này tạo ra cùng một hình dạng cây, nên ACM sẽ phân tích chúng chung với nhau.
dot
graph {
node [shape=circle, style=filled, fillcolor="#dde2cc"];
subgraph cluster_a {
label="(2, 7, 1) và (3, 1, 4)"; style=dashed;
a2 [label="2"]; a1 [label="1"]; a7 [label="7"];
a2 -- a1; a2 -- a7;
b3 [label="3"]; b1 [label="1"]; b4 [label="4"];
b3 -- b1; b3 -- b4;
}
subgraph cluster_c {
label="(1, 5, 9)"; style=dashed;
c1 [label="1"]; c5 [label="5"]; c9 [label="9"];
cx [style=invis]; cy [style=invis];
c1 -- cx [style=invis]; c1 -- c5;
c5 -- cy [style=invis]; c5 -- c9;
}
subgraph cluster_d {
label="(2, 6, 5)"; style=dashed;
d2 [label="2"]; d6 [label="6"]; d5 [label="5"];
dx [style=invis]; dy [style=invis];
d2 -- dx [style=invis]; d2 -- d6;
d6 -- d5; d6 -- dy [style=invis];
}
subgraph cluster_e {
label="(9, 7, 3)"; style=dashed;
e9 [label="9"]; e7 [label="7"]; e3 [label="3"];
ex [style=invis]; ey [style=invis];
e9 -- e7; e9 -- ex [style=invis];
e7 -- e3; e7 -- ey [style=invis];
}
}
Cho một tập các nguyên mẫu, nhiệm vụ của bạn là xác định chúng tạo ra bao nhiêu hình dạng cây khác nhau.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên là số nguyên mẫu trần nhà cần phân tích và là số lớp của mỗi nguyên mẫu.
Mỗi dòng trong dòng tiếp theo mô tả một nguyên mẫu, gồm số nguyên đôi một khác nhau là độ chống sập của các lớp, theo thứ tự từ trên xuống dưới.
Dữ liệu ra
In ra số hình dạng cây khác nhau.
Ràng buộc
- , .
- Mỗi độ chống sập là số nguyên từ đến ; trong một nguyên mẫu, giá trị đôi một khác nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 2 7 1 3 1 4 1 5 9 2 6 5 9 7 3 |
4 | Như hình trên: và cùng tạo cây có gốc với hai con; ba nguyên mẫu còn lại tạo ba dạng "đường" khác nhau (phải-phải, phải-trái, trái-trái). |
| 3 4 3 1 2 40000 3 4 2 1 33 42 17 23 |
2 | Nguyên mẫu thứ nhất và thứ ba cùng hình dạng: gốc có con phải là một lá, con trái có đúng một con phải. Nguyên mẫu thứ hai có con trái của gốc có một con trái. |
Bình luận