JOI 2005/2006 - Vòng chung kết

Yêu cầu

Mỗi học sinh đánh dấu những địa điểm muốn đi trong chuyến tham quan. Hãy sắp các địa điểm theo số học sinh muốn đi giảm dần; nếu bằng nhau, địa điểm có số nhỏ hơn đứng trước.

Dữ liệu vào

Dòng đầu chứa số học sinh \(n\) và số địa điểm \(m\). Mỗi dòng trong \(n\) dòng tiếp theo chứa \(m\) giá trị 0 hoặc 1; giá trị thứ \(j\) cho biết học sinh có muốn đến địa điểm \(j\) hay không.

Dữ liệu ra

In các số địa điểm theo thứ tự yêu cầu trên một dòng.

Ràng buộc

• \(1\le n\le1000\).
• \(1\le m\le100\).

Ví dụ

20 20
1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1
0 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1 1 0
1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0
0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1
1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0
0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0
0 1 1 1 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 0
0 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1
0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 1 1
1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 1 1 1 1 0
0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0
1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1
1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1
0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1
1 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1
0 1 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 0
0 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1
1 1 0 1 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0
1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1

5 15 16 19 4 8 9 13 18 20 1 3 7 12 14 2 10 6 11 17

Yêu cầu

Một thao tác đọc chuỗi chữ số từ trái sang phải. Với mỗi đoạn gồm \(r\) chữ số \(a\) liên tiếp, ghi liền biểu diễn của \(r\) rồi chữ số \(a\). Ví dụ 122244 trở thành 113224, còn mười một chữ số 4 trở thành 114. Hãy lặp thao tác \(n\) lần.

Dữ liệu vào

Dòng đầu chứa \(n\). Dòng thứ hai chứa chuỗi chữ số ban đầu dài không quá \(100\).

Dữ liệu ra

In chuỗi thu được sau đúng \(n\) thao tác.

Ràng buộc

• \(n\le20\).

Ví dụ

1
3738893538469830671731701877825276800557025400476040953219197257965542184086336386458481140639477995

131713281913151318141619181310161711171311171011182718121512171618202517101215142014171610141019151312111911191712151719162514121118141018162316131816141518141821141016131914272915

Yêu cầu

Có \(n\) hình vuông bằng nhau được xếp thành các cột có đáy thẳng hàng, sao cho chiều cao các cột không tăng từ trái sang phải. Một cách xếp được biểu diễn bởi dãy \((a_1,\ldots,a_s)\) với \(a_1\ge\cdots\ge a_s>0\) và tổng bằng \(n\).

Hãy liệt kê mọi cách xếp theo thứ tự từ điển giảm: dãy có phần tử khác nhau đầu tiên lớn hơn được in trước.

Dữ liệu vào

Một dòng chứa \(n\).

Dữ liệu ra

Mỗi dòng in một phân hoạch \(a_1,a_2,\ldots,a_s\), các số cách nhau bởi dấu cách.

Ràng buộc

• \(n\le30\).

Ví dụ

7

7
6 1
5 2
5 1 1
4 3
4 2 1
4 1 1 1
3 3 1
3 2 2
3 2 1 1
3 1 1 1 1
2 2 2 1
2 2 1 1 1
2 1 1 1 1 1
1 1 1 1 1 1 1

Yêu cầu

Mỗi sợi dây nối hai vòng mang hai số nguyên dương khác nhau \(a,b\). Các dây có vòng cùng số có thể nối tại vòng đó. Một chuỗi là một đường đi liên thông không ghé một số vòng quá một lần; độ dài là số vòng trong đường đi. Hãy tìm độ dài chuỗi lớn nhất tạo được từ các dây đã cho.

Dữ liệu vào

Dòng đầu chứa số dây \(n\). Mỗi dòng trong \(n\) dòng tiếp theo chứa \(a,b\), mô tả hai đầu một dây.

Dữ liệu ra

In số vòng lớn nhất trong một chuỗi.

Ràng buộc

• \(1\le n\le100\).
• \(1\le a<b\le100\).

Ví dụ

21
1 2
1 3
1 4
1 5
4 8
8 14
5 9
9 15
3 7
7 12
7 13
12 19
2 6
6 10
6 11
10 16
16 20
11 17
11 18
14 21
19 22

11

Yêu cầu

Cho nhiều tấm hình chữ nhật song song với các trục tọa độ. Hãy tính diện tích hợp của chúng; nếu \(r=2\), đồng thời tính chu vi biên của hợp.

Dữ liệu vào

Dòng đầu chứa số hình chữ nhật \(n\) và loại yêu cầu \(r\). Mỗi dòng tiếp theo chứa \(x_1,y_1,x_2,y_2\), là góc trái dưới và góc phải trên của một hình chữ nhật.

Dữ liệu ra

Nếu \(r=1\), in diện tích. Nếu \(r=2\), in diện tích ở dòng đầu và chu vi ở dòng thứ hai.

Ràng buộc

• \(n\le10000\).
• \(r\in\{1,2\}\).
• \(0\le x_1<x_2\le10000\) và \(0\le y_1<y_2\le10000\).

Phân nhóm

• \(40\%\) dữ liệu có mọi tọa độ không vượt quá \(100\); một nửa số điểm này chỉ yêu cầu diện tích.
• Tổng cộng \(50\%\) dữ liệu chỉ yêu cầu diện tích.

Ví dụ

30 1
13 21 14 22
4 1 7 5
3 6 10 23
14 1 26 28
5 11 29 18
2 10 3 27
3 11 16 13
7 2 11 29
13 10 24 17
19 11 27 22
1 4 6 22
11 3 19 14
10 19 23 20
14 12 17 29
15 3 22 21
9 6 20 26
8 4 16 24
23 6 26 24
17 3 26 12
2 3 23 4
21 5 28 14
10 18 27 29
6 14 8 25
7 18 12 24
9 4 11 5
3 20 18 22
15 1 18 5
19 6 25 11
2 22 21 27
6 23 24 27

709