trang chủ / đề bài / icpcwf16_c

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 n 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ị v như sau:

  • Nếu cây rỗng, v trở thành gốc của cây.
  • Nếu cây khác rỗng, so sánh v với gốc của cây. Nếu v nhỏ hơn thì chèn v vào cây con trái của gốc, ngược lại chèn v 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 2, lớp giữa 7 và lớp dưới cùng 1. Nguyên mẫu thứ hai có các lớp với độ chống sập 3, 1 và 4, 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 n là số nguyên mẫu trần nhà cần phân tích và k là số lớp của mỗi nguyên mẫu.

Mỗi dòng trong n dòng tiếp theo mô tả một nguyên mẫu, gồm k 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

  • 1≤n≤50, 1≤k≤20.
  • Mỗi độ chống sập là số nguyên từ 1 đến 106; trong một nguyên mẫu, k 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: (2,7,1) và (3,1,4) 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

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