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

Với số nguyên \(n\ge 1\), gọi \(P_n\) là xâu gồm \(n+1\) chữ I và \(n\) chữ O, được xếp xen kẽ và bắt đầu bằng I. Cả I và O đều là chữ cái Latin in hoa. Chẳng hạn, \(P_1=\) IOI, \(P_2=\) IOIOI, \(P_3=\) IOIOIOI.

Cho số nguyên \(n\) và xâu \(s\) chỉ gồm các chữ I, O. Một lần xuất hiện của \(P_n\) trong \(s\) là một đoạn gồm các ký tự liên tiếp của \(s\) bằng \(P_n\). Các lần xuất hiện có thể chồng lấn nhau.

Yêu cầu

Đếm số vị trí xuất hiện của \(P_n\) trong \(s\).

Dữ liệu vào

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

• Dòng thứ nhất chứa số nguyên \(n\).
• Dòng thứ hai chứa số nguyên \(m\), là độ dài của \(s\).
• Dòng thứ ba chứa xâu \(s\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: số lần xuất hiện của \(P_n\) trong \(s\). Nếu không có lần xuất hiện nào, ghi \(0\).

Ràng buộc

• \(1\le n\le 1\,000\,000\).
• \(1\le m\le 1\,000\,000\).
• \(2n+1\le m\).
• Xâu \(s\) có đúng \(m\) ký tự và chỉ gồm I, O.
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(64\) MB.

Chấm điểm

Bài có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm.

• \(50\%\) số điểm (\(10\) điểm) ứng với các bộ dữ liệu thỏa mãn \(n\le 100\) và \(m\le 10\,000\).

Ví dụ

1
13
OOIOIOIOIIOII

4

Ở đây \(P_1=\) IOI. Bốn lần xuất hiện được gạch chân trong hình dưới đây.

2
13
OOIOIOIOIIOII

2

Ở đây \(P_2=\) IOIOI. Hai lần xuất hiện được gạch chân trong hình dưới đây.

JOI Pizza giao bánh pizza dọc theo một tuyến đường vòng khép kín dài \(d\) mét đi qua khu trung tâm thành phố.

Trên tuyến đường có \(n\) cửa hàng \(S_1,S_2,\ldots,S_n\), trong đó \(S_1\) là cửa hàng chính. Lấy vị trí của \(S_1\) làm mốc \(0\). Với \(i\ge 2\), cửa hàng \(S_i\) nằm ở vị trí \(d_i\), nghĩa là đi từ \(S_1\) theo chiều kim đồng hồ một quãng \(d_i\) mét sẽ đến \(S_i\). Các vị trí \(d_2,\ldots,d_n\) đôi một khác nhau.

Vị trí của một địa điểm nhận bánh được biểu diễn bằng số nguyên \(k\) từ \(0\) đến \(d-1\): khoảng cách từ \(S_1\) đến đó khi đi theo chiều kim đồng hồ là \(k\) mét. Khi nhận một đơn hàng, JOI Pizza sẽ làm và giao bánh từ cửa hàng có quãng đường ngắn nhất đến địa điểm nhận bánh để bánh không bị nguội. Người giao bánh chỉ được đi dọc theo tuyến đường vòng, nhưng có thể đi theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Chẳng hạn, hình dưới đây minh họa ví dụ 1. Cửa hàng chính \(S_1\) ở vị trí \(0\), cửa hàng \(S_2\) ở vị trí \(3\), cửa hàng \(S_3\) ở vị trí \(1\). Địa điểm nhận bánh thứ nhất ở vị trí \(4\), địa điểm thứ hai ở vị trí \(6\).

Địa điểm thứ nhất gần cửa hàng \(S_2\) nhất, với quãng đường giao bánh dài \(1\) mét. Địa điểm thứ hai gần cửa hàng \(S_1\) nhất, với quãng đường giao bánh dài \(2\) mét.

Yêu cầu

Cho chiều dài tuyến đường \(d\), số cửa hàng \(n\), số đơn hàng \(m\), vị trí các cửa hàng \(d_2,\ldots,d_n\) và vị trí nhận bánh \(k_1,\ldots,k_m\). Tính tổng quãng đường giao bánh của tất cả các đơn hàng, trong đó mỗi đơn hàng được giao từ cửa hàng gần địa điểm nhận bánh nhất.

Dữ liệu vào

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

• Dòng thứ nhất chứa số nguyên \(d\).
• Dòng thứ hai chứa số nguyên \(n\).
• Dòng thứ ba chứa số nguyên \(m\).
• \(n-1\) dòng tiếp theo lần lượt chứa \(d_2,d_3,\ldots,d_n\), mỗi dòng một số nguyên.
• \(m\) dòng tiếp theo lần lượt chứa \(k_1,k_2,\ldots,k_m\), mỗi dòng một số nguyên.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: tổng quãng đường giao bánh nhỏ nhất của tất cả các đơn hàng, tính bằng mét.

Ràng buộc

• \(2\le d\le 10^9\).
• \(2\le n\le 100\,000\).
• \(1\le m\le 10\,000\).
• \(1\le d_i\le d-1\) với \(2\le i\le n\); các \(d_i\) đôi một khác nhau.
• \(0\le k_i\le d-1\) với \(1\le i\le m\).
• Tổng quãng đường cần tìm không vượt quá \(10^9\).
• Giới hạn thời gian: \(2\) giây.
• Giới hạn bộ nhớ: \(64\) MB.

Chấm điểm

Bài có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm.

• \(40\%\) số điểm (\(8\) điểm) ứng với các bộ dữ liệu thỏa mãn \(n\le 10\,000\).
• \(40\%\) số điểm (\(8\) điểm) ứng với các bộ dữ liệu mà cả \(d\) và tổng quãng đường cần tìm đều không vượt quá \(1\,000\,000\).

Các điều kiện trên có thể cùng đúng trên một bộ dữ liệu.

Ví dụ

8
3
2
3
1
4
6

3

20
4
4
12
8
16
7
7
11
8

3

Bạn đang chơi trò rút thăm bằng sơ đồ thang cùng bạn J. Sơ đồ gồm \(n\) thanh dọc và \(m\) thanh ngang. Các thanh dọc được đánh số từ \(1\) đến \(n\) theo thứ tự từ trái sang phải. Ở đầu dưới của thanh dọc \(i\) có ghi số nguyên dương \(s_i\).

Nếu chọn thanh dọc \(i\), bạn bắt đầu từ đầu trên của thanh đó rồi đi xuống. Mỗi khi gặp một thanh ngang, bạn đi sang thanh dọc kề bên qua thanh ngang đó rồi tiếp tục đi xuống. Số ghi ở đầu dưới mà bạn đến được là điểm nhận được khi chọn thanh dọc \(i\).

Trong sơ đồ trên, chọn thanh dọc \(1\) được \(80\) điểm, còn chọn thanh dọc \(2\) được \(100\) điểm. Hai đường đi này được tô đậm trong hình dưới đây.

J quyết định chọn \(k\) thanh dọc liên tiếp từ thanh \(1\) đến thanh \(k\). Điểm của J bằng tổng điểm nhận được từ \(k\) lựa chọn này. Bạn được phép xóa nhiều nhất một thanh ngang khỏi sơ đồ; cũng có thể không xóa thanh nào. Nếu bạn xóa một thanh ngang, điểm của J được tính trên sơ đồ sau khi xóa.

Yêu cầu

Cho sơ đồ thang và số thanh dọc \(k\) mà J chọn. Tìm điểm nhỏ nhất mà J có thể nhận được khi bạn xóa nhiều nhất một thanh ngang.

Dữ liệu vào

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

• Dòng thứ nhất chứa bốn số nguyên \(n,m,h,k\) cách nhau bởi dấu cách. Trong đó \(h\) là chiều dài mỗi thanh dọc.
• \(n\) dòng tiếp theo lần lượt chứa \(s_1,s_2,\ldots,s_n\), mỗi dòng một số nguyên.
• \(m\) dòng tiếp theo mô tả các thanh ngang, được đánh số từ \(1\) đến \(m\) theo thứ tự nhập. Dòng thứ \(i\) trong số này chứa hai số nguyên \(a_i,b_i\) cách nhau bởi dấu cách: thanh ngang \(i\) nối thanh dọc \(a_i\) với thanh dọc \(a_i+1\) tại vị trí cách đầu trên của các thanh dọc một khoảng \(b_i\).

Không có hai thanh ngang nào chung đầu mút.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: điểm nhỏ nhất mà J có thể nhận được.

Ràng buộc

• \(2\le n\le 1000\).
• \(1\le m\le 100\,000\).
• \(2\le h\le 1000\).
• \(1\le k\le n\).
• \(s_i\) là số nguyên dương và \(s_1+s_2+\cdots+s_n\le 2\times 10^9\).
• \(1\le a_i\le n-1\) và \(1\le b_i\le h-1\).
• Không có hai thanh ngang nào chung đầu mút.
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(64\) MB.

Chấm điểm

Bài có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm.

• \(20\%\) số điểm (\(4\) điểm) ứng với các bộ dữ liệu mà không xóa thanh ngang nào cũng đạt điểm nhỏ nhất cho J.
• \(30\%\) số điểm (\(6\) điểm) ứng với các bộ dữ liệu thỏa mãn \(n\le 20\), \(m\le 30\), \(h\le 10\).
• \(60\%\) số điểm (\(12\) điểm) ứng với các bộ dữ liệu thỏa mãn \(m\le 1000\).

Các điều kiện trên có thể cùng đúng trên một bộ dữ liệu.

Ví dụ

4 5 7 2
20
80
100
50
1 1
2 6
2 3
1 5
3 1

100

Ví dụ này tương ứng với sơ đồ đầu tiên. Điểm của J nhỏ nhất khi xóa thanh ngang \(4\), là thanh nối thanh dọc \(1\) và thanh dọc \(2\) tại vị trí cách đầu trên một khoảng \(5\).

2 2 5 1
10
20
1 1
1 3

10

Trong ví dụ này, không xóa thanh ngang nào sẽ cho điểm nhỏ nhất của J.

Hình bên trái dưới đây minh họa cách xóa thanh ngang trong ví dụ 1; hình bên phải minh họa ví dụ 2.

Taro sống ở thị trấn JOI. Một ngày nọ, cậu quyết định đi dạo hằng ngày để nâng cao sức khỏe.

Thị trấn có \(H+1\) con đường chạy theo hướng đông–tây và \(W+1\) con đường chạy theo hướng bắc–nam, tạo thành một lưới ô vuông. Nhà Taro nằm ở giao lộ xa nhất về phía tây bắc; mỗi lần đi dạo, cậu đều bắt đầu từ đó.

Gọi \((a,b)\) là giao lộ thứ \(a\) tính từ phía bắc và thứ \(b\) tính từ phía tây, với các chỉ số bắt đầu từ \(1\). Nhà Taro nằm ở giao lộ \((1,1)\).

Trong hình, phía trên là phía bắc và phía trái là phía tây.

Taro muốn đường đi thay đổi qua từng ngày cho thú vị, nên cậu ghi một trong hai hướng “đông” hoặc “nam” tại mỗi giao lộ \((a,b)\) với \(1\le a\le H\) và \(1\le b\le W\). Mỗi lần đi dạo diễn ra theo các quy tắc sau:

• Khi đang ở một giao lộ có ghi hướng, Taro đổi hướng được ghi tại đó từ “đông” thành “nam” hoặc từ “nam” thành “đông”. Sau đó, cậu đi đến giao lộ kế tiếp theo hướng đã được ghi trước khi đổi.
• Khi đến con đường xa nhất về phía đông hoặc con đường xa nhất về phía nam, cậu kết thúc lần đi dạo đó.

Các hướng đã thay đổi được giữ nguyên cho những lần đi dạo tiếp theo. Đi về phía đông từ \((a,b)\) sẽ đến \((a,b+1)\); đi về phía nam sẽ đến \((a+1,b)\).

Yêu cầu

Cho các hướng được ghi ban đầu. Xác định giao lộ mà Taro kết thúc lần đi dạo thứ \(N\).

Dữ liệu vào

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

• Dòng thứ nhất chứa ba số nguyên \(H,W,N\) cách nhau bởi dấu cách.
• \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) số nguyên cách nhau bởi dấu cách. Số thứ \(j\) trên dòng thứ \(i\) trong số này mô tả hướng ban đầu tại giao lộ \((i,j)\): \(0\) là hướng nam, \(1\) là hướng đông.

Dữ liệu ra

Ghi ra đầu ra chuẩn hai số nguyên \(i,j\) cách nhau bởi một dấu cách trên một dòng, trong đó \((i,j)\) là giao lộ mà Taro kết thúc lần đi dạo thứ \(N\).

Ràng buộc

• \(1\le H\le 1000\).
• \(1\le W\le 1000\).
• \(1\le N\le 10^7\).
• Mỗi giá trị mô tả hướng là \(0\) hoặc \(1\).
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(64\) MB.

Chấm điểm

Bài có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm.

• \(30\%\) số điểm (\(6\) điểm) ứng với các bộ dữ liệu thỏa mãn \(H\le 100\), \(W\le 100\), \(N\le 1000\).

Ví dụ

3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

1 5

Ba hình dưới đây lần lượt minh họa đường đi trong lần đi dạo thứ nhất, thứ hai và thứ ba. Ký tự 東 nghĩa là đông, ký tự 南 nghĩa là nam. Các hướng trong mỗi hình là các hướng trước khi bắt đầu lần đi dạo tương ứng.

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 công ty là JOI.

JOI có hai văn phòng. Mỗi văn phòng gồm các căn phòng hình vuông cùng kích thước, được xếp thành một lưới. Giữa hai phòng có chung cạnh luôn có một cánh cửa kiểm tra thẻ căn cước. Mỗi phòng được gán một mức độ bảo mật là số nguyên dương. Thẻ căn cước có một mức xác thực riêng cho từng văn phòng, là số nguyên không âm. Chỉ khi mức xác thực đối với văn phòng đó lớn hơn hoặc bằng mức độ bảo mật của một phòng thì người mang thẻ mới được vào phòng ấy.

Mỗi văn phòng chỉ có một lối ra vào, nằm tại phòng sảnh thang máy. Mức độ bảo mật của phòng này là \(1\), mức thấp nhất. Nếu mức xác thực đối với một văn phòng bằng \(0\) thì người mang thẻ không thể vào cả sảnh thang máy của văn phòng đó.

Theo một đề xuất bất ngờ của giám đốc, JOI sẽ tổ chức các chuyến tham quan công ty cho công chúng. Bạn phải quyết định hai mức xác thực trên thẻ phát cho khách. Khách sẽ mở cửa và đi vào mỗi khi gặp một cánh cửa mà họ được phép mở; một phòng có thể được ghé thăm nhiều lần. Vì vậy, bạn không muốn cấp mức xác thực cao hơn mức cần thiết. Tuy nhiên, để chuyến tham quan đủ hấp dẫn, khách phải có thể đến được tổng cộng ít nhất \(R\) phòng khác nhau trong hai văn phòng, tính cả các phòng sảnh thang máy có thể vào được.

Văn phòng thứ \(k\) (\(k=1,2\)) có \(W_k\) phòng theo hướng đông–tây và \(H_k\) phòng theo hướng bắc–nam, tổng cộng \(W_kH_k\) phòng. Ký hiệu \((i,j)_k\) là phòng thứ \(i\) tính từ phía tây và thứ \(j\) tính từ phía bắc trong văn phòng \(k\). Sảnh thang máy ở vị trí \((X_k,Y_k)_k\).

Một phòng được tính là có thể ghé thăm nếu khách có thể đi từ sảnh thang máy đến phòng đó qua các phòng được phép vào, mỗi bước đi qua cửa nối hai phòng chung cạnh. Bạn có thể cấp mức xác thực \(0\) cho một văn phòng để khách không vào văn phòng đó.

Yêu cầu

Cho kích thước hai văn phòng, vị trí các sảnh thang máy, mức độ bảo mật của từng phòng và số \(R\). Tìm tổng nhỏ nhất của hai mức xác thực sao cho khách có thể ghé thăm ít nhất \(R\) phòng khác nhau trong hai văn phòng.

Còn JOI kiếm lợi nhuận như thế nào từ “những phát minh kỳ lạ” thì ngay trong công ty cũng là bí mật tuyệt đối, chỉ giám đốc biết.

Dữ liệu vào

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

• Dòng thứ nhất chứa số nguyên \(R\).
• Tiếp theo là dữ liệu của văn phòng \(1\), rồi dữ liệu của văn phòng \(2\).
• Dữ liệu của văn phòng \(k\) bắt đầu bằng một dòng chứa bốn số nguyên \(W_k,H_k,X_k,Y_k\) cách nhau bởi dấu cách.
• Sau đó là \(H_k\) dòng, mỗi dòng chứa \(W_k\) số nguyên cách nhau bởi dấu cách. Số thứ \(i\) trên dòng thứ \(j\) trong số này là \(L_{k,i,j}\), mức độ bảo mật của phòng \((i,j)_k\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: tổng nhỏ nhất của hai mức xác thực thỏa mãn yêu cầu.

Ràng buộc

• \(1\le R\le 100\,000\).
• \(1\le X_k\le W_k\le 500\) với \(k=1,2\).
• \(1\le Y_k\le H_k\le 500\) với \(k=1,2\).
• \(1\le L_{k,i,j}<10^8\).
• Mức độ bảo mật của mỗi sảnh thang máy bằng \(1\).
• \(R\le W_1H_1+W_2H_2\).
• Hai mức xác thực cần chọn là các số nguyên không âm.
• Giới hạn thời gian: \(2\) giây.
• Giới hạn bộ nhớ: \(64\) MB.

Chấm điểm

Bài có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm.

• \(30\%\) số điểm (\(6\) điểm) ứng với các bộ dữ liệu thỏa mãn \(R\le 100\), \(W_k\le 100\) và \(H_k\le 100\) với cả \(k=1,2\).

Ví dụ

5
2 2 1 2
9 5
1 17
3 2 2 1
6 1 20
8 18 3

15

Chọn mức xác thực \(9\) cho văn phòng \(1\) và \(6\) cho văn phòng \(2\). Khách có thể ghé thăm \(5\) phòng: \((1,1)_1\), \((1,2)_1\), \((2,1)_1\) ở văn phòng \(1\) và \((1,1)_2\), \((2,1)_2\) ở văn phòng \(2\). Tổng hai mức xác thực bằng \(15\), là tổng nhỏ nhất để có thể ghé thăm ít nhất \(5\) phòng.

Trong hình dưới đây, văn phòng \(1\) ở bên trái, văn phòng \(2\) ở bên phải; các phòng khách có thể ghé thăm được tô xám.

8
5 4 1 3
5 5 4 5 5
8 2 1 9 7
1 1 3 5 1
7 2 7 1 3
6 5 6 2
2 3 5 8 2 7
1 6 9 4 5 1
2 4 5 4 2 2
5 4 2 5 3 3
7 1 5 1 5 6

4

6
3 3 2 2
2 9 2
9 1 9
2 9 2
2 2 1 1
1 3
5 7

9

Chọn mức xác thực \(9\) cho văn phòng \(1\) và \(0\) cho văn phòng \(2\). Khách có thể ghé thăm toàn bộ \(9\) phòng của văn phòng \(1\), nhưng không thể vào bất kỳ phòng nào ở văn phòng \(2\), kể cả sảnh thang máy \((1,1)_2\). Tổng hai mức xác thực bằng \(9\), là tổng nhỏ nhất để có thể ghé thăm ít nhất \(6\) phòng.