JOI 2013/2014 - Vòng chung kết

Ủy ban Olympic Tin học Nhật Bản quyết định làm một lá cờ JOI mới để cổ vũ các thí sinh tham dự kỳ thi tại Đài Loan.

Lá cờ JOI gồm các ô vuông xếp thành \(M\) hàng và \(N\) cột. Mỗi ô vuông chứa đúng một trong ba chữ cái J, O, I.

Ngoài lá cờ JOI, ủy ban còn quy định một huy hiệu JOI. Huy hiệu gồm các ô vuông xếp thành \(2\) hàng và \(2\) cột, mỗi ô chứa đúng một trong ba chữ cái J, O, I.

Số huy hiệu JOI có trong một lá cờ là số vùng gồm \(2\) hàng liên tiếp và \(2\) cột liên tiếp mà cách sắp xếp các chữ cái trùng với huy hiệu JOI, không xoay hay lật. Các vùng thỏa mãn được đếm riêng, kể cả khi chúng chồng lên nhau.

Ủy ban có một lá cờ JOI cũ và một mảnh giấy trắng có kích thước bằng một ô vuông của lá cờ. Có thể viết lên mảnh giấy một chữ cái tùy chọn trong J, O, I. Để tạo lá cờ mới, ủy ban sẽ thực hiện một trong hai cách sau:

• Giữ nguyên lá cờ cũ làm lá cờ mới, không dùng mảnh giấy.
• Viết một chữ cái lên mảnh giấy rồi dán đè lên một ô vuông bất kỳ của lá cờ cũ, thay đổi đúng một vị trí. Lá cờ sau khi thay đổi là lá cờ mới.

Ủy ban muốn số huy hiệu JOI có trong lá cờ mới lớn nhất có thể.

Yêu cầu

Cho thông tin về lá cờ JOI cũ và huy hiệu JOI, hãy tính số huy hiệu JOI lớn nhất có thể có trong lá cờ mới.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(M, N\) cách nhau bởi một dấu cách, cho biết lá cờ có \(M\) hàng và \(N\) cột.
• Mỗi dòng trong \(M\) dòng tiếp theo chứa một xâu gồm \(N\) chữ cái J, O, I. Ký tự thứ \(j\) từ trái sang của dòng thứ \(i\) trong các dòng này là chữ cái ở hàng \(i\) từ trên xuống, cột \(j\) từ trái sang của lá cờ cũ, với \(1 \le i \le M\), \(1 \le j \le N\).
• Mỗi dòng trong \(2\) dòng tiếp theo chứa một xâu gồm \(2\) chữ cái J, O, I. Ký tự thứ \(j\) từ trái sang của dòng thứ \(i\) trong hai dòng này là chữ cái ở hàng \(i\) từ trên xuống, cột \(j\) từ trái sang của huy hiệu JOI, với \(1 \le i,j \le 2\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: số huy hiệu JOI lớn nhất có thể có trong lá cờ mới.

Ràng buộc

• \(2 \le M \le 1\,000\).
• \(2 \le N \le 1\,000\).

Phân nhóm

• Nhóm 1 (30 điểm): \(M \le 50\), \(N \le 50\).
• Nhóm 2 (70 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 5
JOIJO
IJOOO
IIJIJ
JO
IJ

3

2 6
JOJOJO
OJOJOJ
OJ
JO

2

2 2
JI
IJ
JJ
JJ

0

Incredible Okashi Inc. là công ty sản xuất những món bánh kẹo ngon đến khó tin, gọi tắt là công ty IOI. Công ty vừa làm ra những chiếc bánh manju IOI đặc biệt và quyết định đem bán. Có \(M\) loại bánh, mỗi loại được làm đúng một chiếc. Tất cả \(M\) chiếc bánh đều có cùng kích thước, nhưng mỗi chiếc có một hương vị khác nhau nên giá bán cũng khác nhau. Chiếc bánh thứ \(i\) (\(1 \le i \le M\)) có giá \(P_i\) yên.

Bạn có biết công ty Just Odd Inventions không? Công việc của công ty này là tạo ra những phát minh kỳ lạ; ta gọi tắt là công ty JOI. Công ty IOI quyết định đặt mua những chiếc hộp cao cấp của JOI để đựng bánh. JOI sản xuất \(N\) loại hộp đựng bánh manju. Hộp thứ \(j\) (\(1 \le j \le N\)) đựng được tối đa \(C_j\) chiếc bánh và có giá \(E_j\) yên.

IOI sẽ chọn một số loại hộp trong \(N\) loại, có thể chọn từ \(0\) đến \(N\) loại, và đặt mua đúng một hộp thuộc mỗi loại đã chọn. Sau đó, công ty chia bánh vào các hộp để bán thành từng bộ. Giá bán của một bộ bằng tổng giá của những chiếc bánh có trong bộ đó.

Giả sử tất cả các bộ bánh đều bán được, lợi nhuận lớn nhất mà IOI có thể thu được là bao nhiêu? Lợi nhuận bằng tổng giá bán các bộ bánh trừ đi tổng giá mua các hộp đã đặt. Những chiếc bánh không được đóng hộp sẽ được nhân viên IOI thưởng thức và không ảnh hưởng đến lợi nhuận.

Yêu cầu

Cho giá của từng chiếc bánh, sức chứa và giá của từng loại hộp, hãy tính lợi nhuận lớn nhất mà công ty IOI có thể thu được.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(M, N\) cách nhau bởi một dấu cách, cho biết có \(M\) chiếc bánh và \(N\) loại hộp.
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa số nguyên \(P_i\), là giá tính bằng yên của chiếc bánh thứ \(i\), với \(1 \le i \le M\).
• Dòng thứ \(j\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(C_j, E_j\) cách nhau bởi một dấu cách. Hộp thứ \(j\) đựng được tối đa \(C_j\) chiếc bánh và có giá \(E_j\) yên, với \(1 \le j \le N\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: lợi nhuận lớn nhất công ty IOI có thể thu được, tính bằng yên.

Ràng buộc

• \(1 \le M \le 10\,000\).
• \(1 \le N \le 500\).
• \(1 \le P_i \le 10\,000\) với \(1 \le i \le M\).
• \(1 \le C_j \le 10\,000\) với \(1 \le j \le N\).
• \(1 \le E_j \le 10\,000\) với \(1 \le j \le N\).

Phân nhóm

• Nhóm 1 (25 điểm): \(N \le 10\).
• Nhóm 2 (35 điểm): \(C_j \le 10\) với mọi \(1 \le j \le N\).
• Nhóm 3 (40 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 3
180
160
170
190
2 100
3 120
4 250

480

2 2
1000
2000
1 6666
1 7777

0

10 4
200
250
300
300
350
400
500
300
250
200
3 1400
2 500
2 600
1 900

450

JOI đang chuẩn bị ăn quà chiều cùng hai em gái JOI-ko và JOI-mi. Món ăn hôm nay là bánh Baumkuchen, món khoái khẩu của cả ba anh em.

Bánh Baumkuchen có dạng hình trụ như Hình 1. Để chia cho ba người, JOI phải cắt bánh thành ba miếng bằng ba nhát cắt theo hướng bán kính. Tuy nhiên, chiếc bánh này cứng như gỗ thật nên không dễ cắt. Vì vậy, trên bánh đã có sẵn \(N\) rãnh cắt và JOI chỉ có thể cắt tại những vị trí này.

Đánh số các rãnh từ \(1\) đến \(N\) theo chiều kim đồng hồ. Với \(1 \le i \le N-1\), phần bánh nằm giữa rãnh thứ \(i\) và rãnh thứ \(i+1\) có độ lớn \(A_i\). Phần bánh nằm giữa rãnh thứ \(N\) và rãnh thứ \(1\) có độ lớn \(A_N\).

Hình 1: Ví dụ về bánh Baumkuchen với \(N = 6\), \(A_1 = 1\), \(A_2 = 5\), \(A_3 = 4\), \(A_4 = 5\), \(A_5 = 2\), \(A_6 = 4\).

Vì thương các em, sau khi cắt bánh thành ba miếng, JOI sẽ chọn miếng nhỏ nhất cho mình và nhường hai miếng còn lại cho hai em gái. Mặt khác, JOI rất thích bánh Baumkuchen nên muốn được ăn càng nhiều càng tốt. Nếu cắt sao cho miếng nhỏ nhất có độ lớn lớn nhất có thể, miếng bánh JOI ăn sẽ có độ lớn bao nhiêu?

Yêu cầu

Cho số rãnh cắt \(N\) và các số nguyên \(A_1, \ldots, A_N\) biểu diễn độ lớn của từng phần bánh. Hãy tính giá trị lớn nhất có thể của độ lớn miếng nhỏ nhất khi chia bánh thành ba miếng.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), cho biết trên bánh có \(N\) rãnh cắt.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa số nguyên \(A_i\), với \(1 \le i \le N\). Đây là độ lớn phần bánh giữa rãnh thứ \(i\) và rãnh thứ \(i+1\); khi \(i=N\), đó là phần giữa rãnh thứ \(N\) và rãnh thứ \(1\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: giá trị lớn nhất có thể của độ lớn miếng nhỏ nhất khi chia bánh thành ba miếng.

Ràng buộc

• \(3 \le N \le 100\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N \le 100\).
• Nhóm 2 (15 điểm): \(N \le 400\).
• Nhóm 3 (30 điểm): \(N \le 8\,000\).
• Nhóm 4 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

6
1
5
4
5
2
4

6

30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

213

Trong khu rừng nơi chú sóc bay đường JOI sinh sống có \(N\) cây bạch đàn, được đánh số từ \(1\) đến \(N\). Cây \(i\) cao \(H_i\) mét.

Có \(M\) cặp cây mà JOI có thể bay trực tiếp từ cây này sang cây kia theo cả hai chiều. Với mỗi cặp, thời gian cần để bay giữa hai cây đã được xác định. Trong lúc bay, độ cao của JOI so với mặt đất giảm \(1\) mét mỗi giây. Cụ thể, nếu độ cao hiện tại là \(h\) mét và chuyến bay mất \(t\) giây thì khi đến nơi, độ cao của JOI sẽ là \(h-t\) mét. Tuy nhiên, JOI không thể thực hiện chuyến bay nếu \(h-t < 0\) hoặc \(h-t\) lớn hơn chiều cao của cây đích.

Ngoài ra, JOI có thể di chuyển lên hoặc xuống dọc theo thân cây đang đứng, thay đổi độ cao trong khoảng từ \(0\) mét đến chiều cao của cây đó. Mỗi lần tăng hoặc giảm độ cao \(1\) mét mất \(1\) giây.

JOI muốn đi từ vị trí ở độ cao \(X\) mét trên cây \(1\) đến ngọn cây \(N\), tức vị trí ở độ cao \(H_N\) mét, và muốn biết thời gian ít nhất cần để thực hiện việc này.

Yêu cầu

Cho chiều cao của từng cây, thông tin về các cặp cây JOI có thể bay trực tiếp giữa chúng và độ cao ban đầu của JOI. Hãy tính thời gian ít nhất để JOI đến ngọn cây \(N\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N, M, X\) cách nhau bởi dấu cách. Có \(N\) cây, \(M\) cặp cây có thể bay trực tiếp giữa chúng, và ban đầu JOI ở độ cao \(X\) mét trên cây \(1\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa số nguyên \(H_i\), là chiều cao tính bằng mét của cây \(i\), với \(1 \le i \le N\).
• Dòng thứ \(j\) trong \(M\) dòng tiếp theo chứa ba số nguyên \(A_j, B_j, T_j\) cách nhau bởi dấu cách. JOI có thể bay trực tiếp giữa cây \(A_j\) và cây \(B_j\) theo cả hai chiều, mỗi chuyến mất \(T_j\) giây. Các chỉ số thỏa mãn \(1 \le A_j, B_j \le N\) và \(A_j \ne B_j\). Không có cặp cây nào được liệt kê hai lần: với \(1 \le j < k \le M\), ta có cả \((A_j,B_j) \ne (A_k,B_k)\) và \((A_j,B_j) \ne (B_k,A_k)\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: thời gian ít nhất, tính bằng giây, để JOI đi từ độ cao \(X\) mét trên cây \(1\) đến ngọn cây \(N\). Nếu không có cách đi như vậy, in ra \(-1\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 300\,000\).
• \(1 \le H_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(1 \le T_j \le 1\,000\,000\,000\) với \(1 \le j \le M\).
• \(0 \le X \le H_1\).

Phân nhóm

• Nhóm 1 (25 điểm): \(N \le 1\,000\), \(M \le 3\,000\), \(H_i \le 100\) với mọi \(1 \le i \le N\), và \(T_j \le 100\) với mọi \(1 \le j \le M\).
• Nhóm 2 (25 điểm): \(X = 0\).
• Nhóm 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20

110

2 1 0
1
1
1 2 100

-1

4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10

100

JOI thích làm mô hình giấy. Hôm nay, cậu lại chuẩn bị làm một tác phẩm mới.

Trước hết, theo bản thiết kế, JOI in \(N\) đường cắt lên một tờ giấy hình chữ nhật. Mỗi đường cắt là một đoạn thẳng song song với cạnh dọc hoặc cạnh ngang của tờ giấy.

Tất cả các phần giấy tạo ra sau khi cắt đều sẽ được dùng làm các bộ phận của tác phẩm. Tất nhiên, tác phẩm càng có nhiều bộ phận thì càng khó làm. JOI muốn biết tờ giấy sẽ được chia thành bao nhiêu phần sau khi cắt theo tất cả các đường cắt.

Yêu cầu

Cho kích thước tờ giấy và thông tin về \(N\) đường cắt. Hãy tính số phần mà tờ giấy được chia thành sau khi cắt theo những đường này.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(W, H, N\) cách nhau bởi dấu cách. \(W\) là độ dài cạnh ngang, \(H\) là độ dài cạnh dọc của tờ giấy và \(N\) là số đường cắt. Các góc dưới trái, dưới phải, trên trái, trên phải của tờ giấy lần lượt có tọa độ \((0,0)\), \((W,0)\), \((0,H)\), \((W,H)\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa bốn số nguyên \(A_i, B_i, C_i, D_i\) cách nhau bởi dấu cách, thỏa mãn \(0 \le A_i \le C_i \le W\) và \(0 \le B_i \le D_i \le H\). Đường cắt thứ \(i\) là đoạn thẳng nối \((A_i,B_i)\) với \((C_i,D_i)\). Đoạn thẳng này song song với một cạnh của tờ giấy, tức là đúng một trong hai đẳng thức \(A_i=C_i\) và \(B_i=D_i\) được thỏa mãn. Hai đường cắt song song bất kỳ không có điểm chung. Một đường cắt cũng không có điểm chung với bất kỳ cạnh nào của tờ giấy song song với nó.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: số phần mà tờ giấy được chia thành.

Ràng buộc

• \(1 \le W \le 1\,000\,000\,000\).
• \(1 \le H \le 1\,000\,000\,000\).
• \(1 \le N \le 100\,000\).

Phân nhóm

• Nhóm 1 (5 điểm): \(W \le 1\,000\), \(H \le 1\,000\), \(N \le 1\,000\).
• Nhóm 2 (5 điểm): \(N \le 1\,000\).
• Nhóm 3 (20 điểm): Số cặp đường cắt khác nhau có điểm chung không vượt quá \(100\,000\).
• Nhóm 4 (20 điểm): Từ bất kỳ điểm nào nằm trên một đường cắt, đều có thể đi dọc theo một số đường cắt để đến một điểm trên một cạnh của tờ giấy.
• Nhóm 5 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

10 10 5
6 0 6 7
0 6 7 6
2 3 9 3
2 3 2 10
1 9 8 9

4

13 7 28
1 1 4 1
1 1 1 3
2 2 3 2
2 2 2 3
1 3 2 3
3 2 3 6
4 1 4 6
3 6 4 6
5 1 8 1
5 1 5 6
6 2 7 2
6 2 6 5
7 2 7 5
6 5 7 5
8 1 8 6
5 6 8 6
9 1 12 1
9 1 9 2
9 2 10 2
12 1 12 2
11 2 12 2
10 2 10 5
9 5 10 5
9 5 9 6
11 2 11 5
11 5 12 5
12 5 12 6
9 6 12 6

5