JOI 2007/2008 - Vòng chung kết

Bạn lần lượt đặt \(n\) quân cờ vây trắng hoặc đen thành một hàng, từ trái sang phải. Khi đặt quân thứ \(i\), áp dụng quy tắc sau:

• Nếu \(i\) lẻ, giữ nguyên các quân đã có và đặt quân mới vào vị trí thứ \(i\) từ trái sang.
• Nếu \(i\) chẵn và quân mới cùng màu với quân ngoài cùng bên phải, giữ nguyên các quân đã có rồi đặt quân mới.
• Nếu \(i\) chẵn và hai màu khác nhau, thay toàn bộ đoạn quân cùng màu liên tiếp ở đầu bên phải bằng các quân cùng màu với quân mới, rồi đặt quân mới vào bên phải.

Ví dụ, nếu bảy quân hiện tại là ○○●●○○○ (trắng là ○, đen là ●), đặt quân thứ tám màu trắng sẽ được ○○●●○○○○; đặt quân thứ tám màu đen sẽ được ○○●●●●●●.

Biết màu của từng quân được đặt, hãy tính số quân trắng sau khi đặt đủ \(n\) quân.

Dữ liệu vào

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

Dòng đầu chứa \(n\), với \(1 \le n \le 100000\). Dòng thứ \(i+1\) chứa \(c_i\): \(0\) nếu quân thứ \(i\) được đặt có màu trắng, \(1\) nếu có màu đen.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số quân trắng sau khi đặt đủ \(n\) quân.

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm. \(50\%\) số điểm ứng với dữ liệu có \(n \le 10000\).

Ví dụ

8
1
0
1
1
0
0
0
0

6

8
1
0
1
1
0
0
0
1

2

Cho hai xâu, hãy tìm độ dài lớn nhất của một xâu xuất hiện liên tiếp trong cả hai xâu đó.

Một xâu \(s\) được chứa trong xâu \(t\) nếu các ký tự của \(s\) xuất hiện liên tiếp trong \(t\). Xâu rỗng có độ dài \(0\) được chứa trong mọi xâu. Chẳng hạn, ABRACADABRA chứa ABRA, RAC, D, ACADABRA, ABRACADABRA và xâu rỗng, nhưng không chứa ABRC, RAA, BA hoặc K.

Dữ liệu vào

Đọc từ đầu vào chuẩn gồm hai dòng, mỗi dòng chứa một xâu. Mỗi xâu chỉ gồm chữ cái tiếng Anh in hoa và có độ dài từ \(1\) đến \(4000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa độ dài của xâu con liên tiếp chung dài nhất.

Chấm điểm

Giới hạn thời gian: \(1.5\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm. \(30\%\) số điểm ứng với dữ liệu mà độ dài của mỗi xâu không quá \(50\).

Ví dụ

ABRACADABRA
ECADADABRBCRDARA

5

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

0

Bạn chơi ném phi tiêu theo quy tắc sau. Bạn được ném tối đa bốn phi tiêu vào bảng đích; có thể ném ít hơn bốn hoặc không ném chiếc nào. Bảng có \(N\) vùng mang các điểm số \(P_1,\ldots,P_N\). Có thể ném nhiều phi tiêu vào cùng một vùng.

Gọi \(S\) là tổng điểm của những vùng bị phi tiêu cắm trúng. Nếu \(S \le M\), bạn nhận \(S\) điểm; nếu \(S > M\), bạn nhận \(0\) điểm.

Biết điểm số trên bảng và \(M\), hãy tính điểm cao nhất có thể đạt được.

Dữ liệu vào

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

Dòng đầu chứa \(N,M\), với \(1 \le N \le 1000\) và \(1 \le M \le 200000000\).

Dòng thứ \(i+1\) chứa \(P_i\), với \(1 \le P_i \le 100000000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số điểm lớn nhất có thể đạt được.

Chấm điểm

Giới hạn thời gian: \(1.5\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm. \(20\%\) số điểm ứng với \(N \le 100\); \(50\%\) số điểm ứng với \(N \le 300\). Hai bảo đảm này không được hiểu là hai nhóm rời nhau.

Ví dụ

4 50
3
14
15
9

48

3 21
16
11
2

20

Một trò chơi yêu cầu bạn nhảy qua các hòn đá để đi từ bờ này sang bờ kia của một con sông. Các hòn đá nằm trên một lưới có \(n\) hàng, đánh số từ bờ xuất phát đến bờ đối diện.

Một bước nhảy thông thường đưa bạn tới một hòn đá hoặc bờ ở hàng kế tiếp. Một bước nhảy vượt hàng đưa bạn tới một hòn đá hoặc bờ ở hàng cách hai hàng. Bạn được dùng không quá \(m\) bước nhảy vượt hàng.

Từ bờ xuất phát, hàng kế tiếp là hàng \(1\), hàng cách hai hàng là hàng \(2\). Từ hàng \(n-1\), một bước nhảy vượt hàng tới bờ đối diện; từ hàng \(n\), một bước nhảy thông thường tới bờ đối diện.

Mỗi hòn đá có một độ trơn. Độ nguy hiểm khi nhảy từ đá này sang đá khác, cho cả hai loại bước nhảy, bằng

Bước nhảy từ bờ tới đá hoặc từ đá tới bờ có độ nguy hiểm bằng \(0\).

Hãy tìm tổng độ nguy hiểm nhỏ nhất để sang bờ đối diện. Dữ liệu bảo đảm có thể sang được và không có hai hòn đá trong cùng một ô.

Dữ liệu vào

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

Dòng đầu chứa \(n,m\), với \(2 \le n \le 150\), \(0 \le m \le \lfloor(n+1)/2\rfloor\).

Dòng thứ \(i+1\) mô tả hàng \(i\): bắt đầu bằng \(k_i\) (\(0 \le k_i \le 10\)), sau đó là \(k_i\) cặp \(x_{i,j},d_{i,j}\) lần lượt chỉ cột và độ trơn của từng hòn đá. Mọi số được phân cách bởi dấu cách. \(1 \le x_{i,j},d_{i,j} \le 1000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa tổng độ nguy hiểm nhỏ nhất.

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm. \(20\%\) số điểm ứng với \(n \le 6\); một phần \(20\%\) khác ứng với \(m=0\).

Ví dụ

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

17

5 0
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4

40

Để quảng bá Olympic Tin học, bạn muốn sơn một tấm ván ép hình chữ nhật làm biển hiệu. Trên những chỗ không muốn sơn đã dán các miếng băng che hình chữ nhật. Bạn sẽ dùng một màu khác nhau cho mỗi vùng được ngăn cách bởi băng che.

Biết vị trí các miếng băng che, hãy tính số màu cần dùng. Các cạnh của băng che song song với các cạnh tấm ván. Toàn bộ tấm ván không bị phủ kín bởi băng che.

Dữ liệu vào

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

Dòng đầu chứa chiều rộng \(w\) và chiều cao \(h\), với \(1 \le w,h \le 1000000\).

Dòng thứ hai chứa số miếng băng che \(n\), với \(1 \le n \le 1000\).

\(n\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1,y_1,x_2,y_2\), là tọa độ góc dưới trái và góc trên phải của một miếng băng che. Các tọa độ thỏa mãn \(0 \le x_1 < x_2 \le w\), \(0 \le y_1 < y_2 \le h\).

Góc dưới trái của tấm ván là \((0,0)\) và góc trên phải là \((w,h)\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số màu cần dùng.

Chấm điểm

Giới hạn thời gian: \(1.5\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(20\) bộ dữ liệu, mỗi bộ \(1\) điểm, tổng cộng \(20\) điểm. \(30\%\) số điểm ứng với \(w \le 100\), \(h \le 100\), \(n \le 100\).

Ví dụ

15 6
10
1 4 5 6
2 1 4 5
1 0 5 1
6 1 7 5
7 5 9 6
7 0 9 2
9 1 10 5
11 0 14 1
12 1 13 5
11 5 14 6

5