IOI 2004 - Ngày 2

Pythagoras cho rằng toán học là nền tảng của thế giới. Ngày nay, các nhà sinh học cũng nghiên cứu những tính chất toán học của các dãy sinh học.

Trong bài này, một dãy sinh học gồm \(M\) số nguyên và thỏa mãn các điều kiện sau:

• Chứa mỗi số trong các số \(0,1,\ldots,M-1\) đúng một lần.
• Bắt đầu bằng \(0\) và kết thúc bằng \(M-1\).
• Không có hai phần tử liên tiếp mang giá trị \(E,E+1\) theo đúng thứ tự đó.

Một đoạn gồm các phần tử ở những vị trí liên tiếp của dãy. Một đoạn được gọi là đoạn có khung nếu phần tử đầu là phần tử nhỏ nhất, phần tử cuối là phần tử lớn nhất và khác phần tử đầu, đồng thời đoạn chứa tất cả các số nguyên từ giá trị phần tử đầu đến giá trị phần tử cuối.

Một đoạn có khung được gọi là một empodio nếu bên trong nó không có đoạn có khung nào ngắn hơn. Từ empodia là dạng số nhiều của empodio.

Ví dụ, xét dãy \((0,3,5,4,6,2,1,7)\). Cả dãy là một đoạn có khung, nhưng không phải empodio vì nó chứa đoạn có khung \((3,5,4,6)\). Đoạn \((3,5,4,6)\) không chứa đoạn có khung nào ngắn hơn, nên đây là một empodio; nó cũng là empodio duy nhất của dãy này.

Hãy tìm tất cả các empodia của dãy sinh học được cho.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(M\), số phần tử của dãy.
• \(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên, lần lượt là các phần tử của dãy theo thứ tự.

Dữ liệu ra

• Dòng đầu chứa số nguyên \(H\), số empodia của dãy.
• \(H\) dòng tiếp theo mô tả tất cả các empodia theo thứ tự tăng dần của vị trí bắt đầu. Mỗi dòng chứa hai số nguyên \(A\) và \(B\): vị trí phần tử đầu và phần tử cuối của empodio. Các vị trí được đánh số từ \(1\).

Ràng buộc

Có một bộ kiểm thử với \(1000000\le M\le 1100000\). Trong tất cả các bộ kiểm thử còn lại, \(1\le M\le 60000\).

Phân nhóm

Có 20 bộ kiểm thử, mỗi bộ có số điểm tối đa là 5. Trong 50% số bộ kiểm thử, \(M\le 2600\).

Ví dụ

8
0
3
5
4
6
2
1
7

1
2 5

Một người nông dân có một số cánh đồng, mỗi cánh đồng được bao quanh bởi một vòng cây bách, và một số dải đất, mỗi dải có một hàng cây bách. Trên mỗi vòng hoặc hàng, giữa hai cây bách liên tiếp có đúng một cây ô liu. Mỗi cây bách của người nông dân thuộc một cánh đồng hoặc một dải đất; mọi cây ô liu đều nằm giữa hai cây bách liên tiếp như trên.

Khi lâm bệnh nặng, người nông dân nói với con trai cả rằng anh được chọn đúng \(Q\) cây bách, đồng thời được thừa hưởng mọi cây ô liu nằm giữa hai cây bách liên tiếp mà anh đã chọn. Anh có thể chọn bất kỳ tổ hợp cây bách nào trên từng cánh đồng và từng dải đất.

Người con rất thích ô liu. Hãy xác định số cây ô liu lớn nhất anh có thể thừa hưởng khi chọn đúng \(Q\) cây bách.

Hình 1. Một cách bố trí các cây bách; các cây ô liu không được vẽ. Các cánh đồng 1, 2, 3 lần lượt có 13, 4, 8 cây bách; các dải đất 1, 2, 3 lần lượt có 4, 8, 6 cây bách. Với \(Q=17\), chọn toàn bộ cây bách ở cánh đồng 1 và cánh đồng 2 cho phép thừa hưởng 17 cây ô liu, là số lượng lớn nhất.

Dữ liệu vào

• Dòng đầu chứa lần lượt ba số nguyên \(Q,M,K\): số cây bách được chọn, số cánh đồng và số dải đất.
• Dòng thứ hai chứa \(M\) số nguyên \(N_1,N_2,\ldots,N_M\), là số cây bách trên từng cánh đồng.
• Dòng thứ ba chứa \(K\) số nguyên \(R_1,R_2,\ldots,R_K\), là số cây bách trên từng dải đất.

Dữ liệu ra

In một số nguyên trên một dòng: số cây ô liu lớn nhất người con có thể thừa hưởng.

Ràng buộc

• \(0\le Q\le 150000\).
• \(0\le M,K\le 2000\).
• \(3\le N_i\le 150\) với \(1\le i\le M\).
• \(2\le R_i\le 150\) với \(1\le i\le K\).
• Tổng số cây bách trên tất cả các cánh đồng và dải đất không nhỏ hơn \(Q\).

Phân nhóm

Có 20 bộ kiểm thử, mỗi bộ có số điểm tối đa là 5. Trong 50% số bộ kiểm thử, \(Q\le 1500\).

Ví dụ

17 3 3
13 4 8
4 8 6

17

Nhà điêu khắc Hy Lạp Phidias đang chuẩn bị xây dựng một công trình mới. Ông cần những tấm đá cẩm thạch hình chữ nhật có kích thước \(W_1\times H_1,W_2\times H_2,\ldots,W_N\times H_N\).

Phidias vừa nhận được một phiến đá hình chữ nhật lớn và muốn cắt nó thành các tấm có kích thước cần dùng. Mỗi lần cắt, ông chọn một miếng đá hiện có rồi cắt thẳng theo chiều ngang hoặc chiều dọc, xuyên suốt miếng đó, để chia nó thành hai hình chữ nhật có chiều rộng và chiều cao nguyên. Đây là cách cắt duy nhất được phép; các miếng đá không thể được ghép lại.

Do hoa văn trên đá, các miếng đá không được xoay: một tấm kích thước \(A\times B\) không thể thay cho tấm \(B\times A\), trừ khi \(A=B\). Với mỗi kích thước cần dùng, Phidias có thể tạo ra không tấm nào hoặc một số lượng tùy ý các tấm.

Sau khi cắt xong, một miếng đá bị bỏ phí nếu kích thước của nó không thuộc các kích thước cần dùng. Hãy tính tổng diện tích bị bỏ phí nhỏ nhất.

Ví dụ, phiến đá ban đầu rộng 21 và cao 11; các kích thước cần dùng là \(10\times4\), \(6\times2\), \(7\times5\) và \(15\times10\). Diện tích bỏ phí nhỏ nhất là 10. Hình dưới minh họa một cách cắt đạt được giá trị đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(W,H\): chiều rộng và chiều cao của phiến đá ban đầu.
• Dòng thứ hai chứa số nguyên \(N\), số kích thước cần dùng.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(W_i,H_i\): chiều rộng và chiều cao của kích thước cần dùng thứ \(i\).

Dữ liệu ra

In một số nguyên trên một dòng: tổng diện tích nhỏ nhất của phiến đá ban đầu phải bỏ phí.

Ràng buộc

• \(1\le W,H\le600\).
• \(1\le N\le200\).
• \(1\le W_i\le W\) và \(1\le H_i\le H\) với \(1\le i\le N\).

Phân nhóm

Có 20 bộ kiểm thử, mỗi bộ có số điểm tối đa là 5. Trong 50% số bộ kiểm thử, \(W\le20\), \(H\le20\) và \(N\le5\).

Ví dụ

21 11
4
10 4
6 2
7 5
15 10

10