0.Hộp xếp chồng


Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Một số khái niệm trong Toán học và Khoa học Máy tính đơn giản ở một hoặc hai chiều nhưng trở thành Phức tạp hơn khi mở rộng đến các kích thước tùy ý. Xem xét giải phương trình vi phân trong một số Kích thước và phân tích topo của một hypercube n -chiều. Các cựu là nhiều hơn nữa Phức tạp hơn so với một chiều tương đối của nó trong khi sau đó có một sự giống nhau đáng chú ý của nó "Thấp hơn" anh em họ.

Xem xét một hộp " n- chiều" được đưa ra theo kích thước của nó.

Trong hai chiều, hộp (2,3) có thể Đại diện cho một hộp với chiều dài 2 đơn vị và chiều rộng 3 đơn vị.

Trong ba chiều, hộp (4,8,9) có thể đại diện Hộp 4 x 8 x 9 (chiều dài, chiều rộng và chiều cao).

Trong 6 chiều, có thể nó không rõ hộp (4,5,6,7,8,9) đại diện; Nhưng chúng ta có thể phân tích các thuộc tính của hộp như tổng các kích thước của nó.

Trong vấn đề này bạn sẽ phân tích một thuộc tính của một nhóm các hộp n- chiều.

Bạn đang xác định Chuỗi làm tổ dài nhất của hộp, đó là một dãy ô b 1 , b 2 , ..., b k sao cho mỗi hộp b i nest Trong hộp b i +1 (1 ≤ i <k ). Một hộp D = ( d1, d2, ..., dn) tổ trong một hộp E = (e1, e2, ..., en) nếu có một số sắp xếp lại D i sao cho khi sắp xếp lại mỗi chiều không nhỏ hơn kích thước tương ứng trong hộp E. Điều này Lỏng lẻo tương ứng với hộp chuyển D để xem nếu nó sẽ phù hợp trong hộp E.

Tuy nhiên, vì bất kỳ sắp xếp lại Đủ, hộp D có thể bị bóp méo, không chỉ xoay (xem ví dụ dưới đây).

Ví dụ

Hộp D = (2,6) tổ trong hộp E = (7,3) vì D có thể được sắp xếp lại như (6,2) vì vậy Mỗi kích thước nhỏ hơn kích thước tương ứng trong E.

Hộp D = (9,5,7,3) KHÔNG Làm tổ trong hộp E = (2,10,6,8) vì không sắp xếp lại kết quả D trong một hộp đáp ứng được việc làm tổ Tài sản, nhưng F = (9,5,7,1) làm tổ trong hộp E vì F có thể được sắp xếp lại như (1,9,5,7) tổ trong E.

Về mặt chính thức, chúng ta xác định tổ như sau: Hộp D = ( d 1 , d 2 , ..., d n ) tổ trong hộp E = ( e 1 , e 2 , ..., e n ) Nếu có một hoán vị π của 1 ... n sao cho ( d π (1) , d π (2) , ..., d π ( n ) ) "phù hợp" trong ( e 1 , e 2 , .. ., E n ) tức là, nếu D π ( i ) <e i cho tất cả 1 ≤ i ≤ n .

Đầu vào

Đầu vào bao gồm một loạt các hộp hộp thoại. Mỗi dãy ô bắt đầu bằng một dòng bao gồm Số hộp k trong dãy theo chiều dọc của chiều dài các hộp, n (trên cùng hàng.) Dòng này được theo sau bởi dòng k , một dòng cho mỗi hộp với n đo của mỗi hộp trên một dòng Cách nhau bởi một hoặc nhiều khoảng trống. Dòng i-th trong chuỗi (1 ≤ i ≤ k ) cho phép đo cho Hộp i-thứ . Có thể có nhiều trình tự hộp trong tệp nhập. Chương trình của bạn nên xử lý tất cả chúng và Xác định, đối với mỗi chuỗi, trong đó k hộp xác định chuỗi làm tổ dài nhất và chiều dài Của chuỗi làm tổ đó (số hộp trong chuỗi). Trong vấn đề này chiều tối đa là 10 và chiều chiều tối thiểu là 1. Số hộp tối đa trong một dãy là 30.

Đầu ra

Đối với mỗi ô trong tệp nhập, đầu ra chiều dài của chuỗi làm tổ dài nhất trên một dòng Tiếp theo vào dòng kế tiếp bởi một danh sách các hộp chứa chuỗi này theo thứ tự. Các "nhỏ nhất" hoặc Hộp bên trong nhất của chuỗi làm tổ nên được liệt kê đầu tiên, hộp tiếp theo (nếu có) phải là Liệt kê thứ hai, vv Các ô cần được đánh số theo thứ tự mà chúng xuất hiện trong tệp tin đầu vào (đầu tiên Hộp là hộp 1, v.v.).

Nếu có nhiều chuỗi làm tổ dài nhất sau đó bất kỳ một trong số chúng có thể được đầu ra.

INPUT

5 2

3 7

8 10

5 2

9 11

21 18

8 6

5 2 20 1 30 10

23 15 7 9 11 3

40 50 34 24 14 4

9 10 11 12 13 14

31 4 18 8 27 17

44 32 13 19 41 19

1 2 3 4 5 6 80 37 47 18 21 9

OUTPUT

5

3 1 2 4 5

4

7 2 5 6


Comments

There are no comments at the moment.