JOI 2015/2016 - Vòng sơ khảo - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2016 - Selecting Subjects	100 (p)	2.0s	256M
2	JOI 2016 - Swapping Bibs	100 (p)	2.0s	256M
3	JOI 2016 - Russian Flag	100 (p)	2.0s	256M
4	JOI 2016 - Walking in JOI Kingdom	100 (p)	2.0s	256M
5	JOI 2016 - Zombie Island	100 (p)	2.0s	256M
6	JOI 2016 - Food Stalls	100 (p)	2.0s	256M

1. JOI 2016 - Selecting Subjects

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

JOI-kun đã làm bài kiểm tra của sáu môn: Vật lý, Hóa học, Sinh học, Khoa học Trái Đất, Lịch sử và Địa lý. Mỗi bài kiểm tra được chấm trên thang điểm 100.

JOI-kun sẽ chọn ba trong bốn môn Vật lý, Hóa học, Sinh học, Khoa học Trái Đất và chọn một trong hai môn Lịch sử, Địa lý.

Hãy tính tổng điểm lớn nhất của bốn môn được chọn.

Dữ liệu vào

Dữ liệu vào gồm 6 dòng, mỗi dòng chứa một số nguyên:

Dòng 1 chứa điểm Vật lý \(A\).
Dòng 2 chứa điểm Hóa học \(B\).
Dòng 3 chứa điểm Sinh học \(C\).
Dòng 4 chứa điểm Khoa học Trái Đất \(D\).
Dòng 5 chứa điểm Lịch sử \(E\).
Dòng 6 chứa điểm Địa lý \(F\).

Các số nguyên \(A,B,C,D,E,F\) đều nằm trong đoạn từ \(0\) đến \(100\).

Dữ liệu ra

In ra trên một dòng tổng điểm của các môn JOI-kun chọn.

Chấm điểm

Có 5 bộ dữ liệu chấm, mỗi bộ trị giá 20 điểm.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

JOI-kun đạt tổng điểm lớn nhất khi chọn Vật lý, Sinh học, Khoa học Trái Đất và Lịch sử: \(100+76+42+10=228\).

Ví dụ 2

Input

Output

Giải thích

Chọn Hóa học, Sinh học, Khoa học Trái Đất và Địa lý cho tổng \(140\). Chọn Vật lý, Hóa học, Khoa học Trái Đất và Địa lý cũng cho tổng \(140\).

Nguồn

Kỳ thi sơ loại Olympic Tin học Nhật Bản 2015/2016, bài 1.

2. JOI 2016 - Swapping Bibs

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(N\) học sinh của trường JOI đứng thành một hàng từ tây sang đông. Học sinh thứ \(i\) tính từ đầu phía tây là học sinh \(i\). Mỗi học sinh đeo một số báo danh ghi một số nguyên; ban đầu số báo danh của học sinh \(i\) ghi \(A_i\).

Có \(M\) cây gậy, được đánh số từ \(1\) đến \(M\). Lần lượt với \(k=1,2,\ldots,M\), thực hiện quy trình sau; quy trình của gậy \(k\) chỉ bắt đầu sau khi quy trình của gậy \(k-1\) kết thúc.

Giáo viên đưa gậy \(k\) cho học sinh 1.
Khi học sinh \(i\) nhận gậy \(k\):
Nếu \(1\le i\le N-1\), so sánh số dư khi số trên hai số báo danh của học sinh \(i\) và \(i+1\) được chia cho \(k\). Nếu số dư của học sinh \(i\) lớn hơn, hai học sinh đổi số báo danh cho nhau. Sau đó học sinh \(i\) đưa gậy cho học sinh \(i+1\).
Nếu \(i=N\), học sinh \(N\) đưa gậy cho giáo viên.
Khi giáo viên nhận lại gậy \(k\), quy trình của gậy đó kết thúc.

Hãy xác định số trên số báo danh của từng học sinh sau khi giáo viên nhận lại gậy \(M\).

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N,M\) (\(1\le N,M\le100\)).
\(N\) dòng tiếp theo: dòng thứ \(i\) chứa \(A_i\) (\(1\le A_i\le1000\)).

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) là số trên số báo danh của học sinh \(i\) sau toàn bộ quá trình.

Chấm điểm

Có 5 bộ dữ liệu chấm, mỗi bộ trị giá 20 điểm.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Sau các gậy \(1,2,3,4\), các dãy lần lượt là 3 2 8 3 1 5, 2 8 3 3 1 5, 2 3 3 1 8 5, và 2 3 1 8 5 3.

Ví dụ 2

Input

Output

Nguồn

Kỳ thi sơ loại Olympic Tin học Nhật Bản 2015/2016, bài 2.

3. JOI 2016 - Russian Flag

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Để chào mừng IOI 2016 tổ chức tại Nga, chủ tịch K muốn làm một lá cờ. Ông lấy từ kho một lá cờ cũ gồm \(N\) hàng và \(M\) cột; mỗi ô có màu trắng, xanh lam hoặc đỏ.

Ông muốn sơn lại một số ô để tạo thành cờ Nga, được định nghĩa như sau:

Một hoặc nhiều hàng trên cùng hoàn toàn màu trắng.
Một hoặc nhiều hàng tiếp theo hoàn toàn màu xanh lam.
Một hoặc nhiều hàng còn lại hoàn toàn màu đỏ.

Hãy tìm số ô ít nhất cần sơn lại.

Dữ liệu vào

Dòng đầu chứa \(N,M\) (\(3\le N,M\le50\)).
\(N\) dòng tiếp theo, mỗi dòng là một xâu dài \(M\). Ký tự W, B, R lần lượt biểu diễn màu trắng, xanh lam, đỏ.

Dữ liệu ra

In ra số ô ít nhất cần sơn lại.

Chấm điểm

Có 5 bộ dữ liệu chấm, mỗi bộ trị giá 20 điểm.

Ví dụ

Ví dụ 1

Input

4 5
WRWRW
BWRWB
WRWRW
RWBWR

Output

Giải thích

Trong ví dụ này, có thể sơn lại 11 ô để tạo cờ Nga và không thể dùng ít ô hơn.

Ví dụ 2

Input

6 14
WWWWWWWWWWWWWW
WBBBWWRRWWBBBW
WWBWWRRRRWWBWW
BWBWWRRRRWWBWW
WBBWWWRRWWBBBW
WWWWWWWWWWWWWW

Output

Nguồn

Kỳ thi sơ loại Olympic Tin học Nhật Bản 2015/2016, bài 3.

4. JOI 2016 - Walking in JOI Kingdom

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Vương quốc JOI có một con đường thẳng rất dài chạy theo hướng đông-tây. Cung điện ở vị trí \(0\); vị trí \(A>0\) cách cung điện \(A\) mét về phía đông, còn \(A<0\) cách cung điện \(-A\) mét về phía tây.

Có \(N\) ngôi nhà, đánh số từ tây sang đông. Nhà \(i\) ở tọa độ chẵn khác \(0\) là \(A_i\), và mọi \(A_i\) đôi một khác nhau. Công dân \(i\) sống tại nhà \(i\).

Theo lệnh nhà vua, mọi công dân đồng thời bắt đầu đi về đông hoặc tây theo hướng đã định, với vận tốc 1 mét mỗi giây. Khi gặp một công dân khác, kể cả một người đã dừng, họ dừng tại đó để trò chuyện và không bao giờ đi tiếp.

Nhà vua muốn biết vị trí của \(Q\) nhân vật quan trọng sau \(T\) giây.

Dữ liệu vào

Dòng đầu chứa \(N,T,Q\), với \(1\le N\le10^5\), \(0\le T\le10^{18}\) và \(1\le Q\le\min(N,1000)\).
\(N\) dòng tiếp theo: dòng \(i\) chứa \(A_i,D_i\). Ta có \(-10^{18}\le A_i\le10^{18}\); \(A_i\) là số chẵn khác \(0\); \(A_i<A_{i+1}\); \(D_i=1\) nghĩa là đi về đông và \(D_i=2\) nghĩa là đi về tây.
\(Q\) dòng cuối: dòng \(i\) chứa \(X_i\) (\(1\le X_i\le N\)), là chỉ số nhân vật quan trọng thứ \(i\); \(X_i<X_{i+1}\).

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(i\) là vị trí của nhân vật quan trọng thứ \(i\) sau \(T\) giây. Các điều kiện của đề bảo đảm vị trí này là số nguyên.

Chấm điểm

Có 5 bộ dữ liệu, mỗi bộ trị giá 20 điểm:

Dữ liệu 1: \(N\le100\), \(T\le10000\).
Dữ liệu 2: \(N\le5000\).
Dữ liệu 3: tồn tại \(M\) (\(1\le M\le N-1\)) sao cho \(D_i=1\) với \(1\le i\le M\) và \(D_j=2\) với \(M+1\le j\le N\).
Trong dữ liệu 1, 2, 3, trị tuyệt đối của mọi số nguyên trong dữ liệu vào không vượt quá \(10^9\).
Dữ liệu 4, 5 không có ràng buộc bổ sung; các số có thể không nằm trong miền số nguyên có dấu 32 bit.

Ví dụ

Ví dụ 1

Input

Output

-6
-6
15

Ví dụ 2

Input

Output

-82
-16
-13
-13
0

Nguồn

Kỳ thi sơ loại Olympic Tin học Nhật Bản 2015/2016, bài 4.

5. JOI 2016 - Zombie Island

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hòn đảo nơi JOI-kun sống đã bị zombie xâm chiếm. Cậu muốn chạy tới nơi trú ẩn an toàn nhất trên đảo.

Đảo có \(N\) thị trấn và \(M\) con đường hai chiều, mỗi đường nối hai thị trấn khác nhau. Chỉ có thể đi giữa các thị trấn bằng đường. Một số thị trấn bị zombie chiếm và không thể đi vào. Một thị trấn được gọi là nguy hiểm nếu có thể tới đó từ một thị trấn bị zombie chiếm bằng không quá \(S\) con đường; các thị trấn khác là không nguy hiểm.

Nhà JOI-kun ở thị trấn 1, nơi trú ẩn ở thị trấn \(N\); cả hai không bị zombie chiếm. Mỗi lần chuyển sang một thị trấn, cậu phải nghỉ qua đêm tại thị trấn vừa tới, trừ thị trấn 1 và \(N\). Chi phí là \(P\) yên tại thị trấn không nguy hiểm và \(Q\) yên tại thị trấn nguy hiểm. Hãy tìm tổng chi phí nhỏ nhất để tới thị trấn \(N\).

Dữ liệu vào

Dòng 1 chứa \(N,M,K,S\): \(2\le N\le10^5\), \(1\le M\le2\cdot10^5\), \(0\le K\le N-2\), \(0\le S\le10^5\).
Dòng 2 chứa \(P,Q\), với \(1\le P<Q\le10^5\).
\(K\) dòng tiếp theo chứa các thị trấn zombie \(C_i\) (\(2\le C_i\le N-1\)), đôi một khác nhau.
\(M\) dòng tiếp theo chứa \(A_j,B_j\) (\(1\le A_j<B_j\le N\)). Không có cặp đường nào lặp lại.

Dữ liệu bảo đảm có thể đi từ 1 tới \(N\) mà không qua thị trấn bị zombie chiếm.

Dữ liệu ra

In ra tổng chi phí nghỉ trọ nhỏ nhất. Kết quả có thể vượt miền số nguyên có dấu 32 bit.

Chấm điểm

Có 5 bộ dữ liệu chấm, mỗi bộ trị giá 20 điểm.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Các thị trấn 3, 4, 6, 8, 12 là nguy hiểm. Lộ trình \(1,2,5,9,10,11,12,13\) có chi phí \(11000\).

Ví dụ 2

Input

Output

Nguồn

Kỳ thi sơ loại Olympic Tin học Nhật Bản 2015/2016, bài 5.

6. JOI 2016 - Food Stalls

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Thành phố IOI là lưới chữ nhật gồm \(H\) hàng từ bắc xuống nam và \(W\) cột từ tây sang đông. Ô ở hàng \(i\), cột \(j\) được ký hiệu \((i,j)\). Một lễ hội lớn đang diễn ra và một số ô có quầy bán các loại bánh kẹo khác nhau. Không có quầy tại \((1,1)\), \((H,W)\) hay các ô chung cạnh với hai ô đó.

JOI-kun đi từ \((1,1)\) tới \((H,W)\), chỉ đi về đông hoặc nam. Mỗi khi vào một ô, cậu lần lượt thực hiện:

Nếu ô hiện tại có quầy bán loại bánh kẹo cậu chưa mua, cậu mua tại quầy đó.
Nếu các ô chung cạnh với ô hiện tại có những quầy bán loại bánh kẹo cậu chưa mua, cậu gọi người bán từ tất cả các quầy ấy ngoại trừ đúng một quầy và mua bánh kẹo của họ.

Cậu không mua cùng một loại bánh kẹo nhiều lần. Vì mọi quầy bán loại khác nhau, hãy tìm tổng số tiền nhỏ nhất cậu phải trả trên một đường đi hợp lệ.

Dữ liệu vào

Dòng đầu chứa \(H,W\) (\(3\le H,W\le1000\)).
\(H\) dòng tiếp theo, mỗi dòng là xâu dài \(W\). Ký tự . nghĩa là không có quầy; một chữ số từ 1 đến 9 là giá bánh kẹo tại quầy đó.

Dữ liệu ra

In ra tổng tiền nhỏ nhất.

Chấm điểm

Có 5 bộ dữ liệu, mỗi bộ trị giá 20 điểm. Trong dữ liệu 1, số ô có quầy không vượt quá 20. Các dữ liệu còn lại không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

5 5
..483
.59.9
3.866
79...
4.8..

Output

Giải thích

Một đường đi tối ưu lần lượt qua \((1,1),(2,1),(3,1),(3,2),(4,2),(4,3),(4,4),(4,5),(5,5)\) và mua tại các quầy \((3,1),(3,3),(4,2)\).

Ví dụ 2

Input

Output

Nguồn

Kỳ thi sơ loại Olympic Tin học Nhật Bản 2015/2016, bài 6.