JOI 2017/2018 - Vòng sơ khảo

JOI muốn mua \(N\) chiếc bút chì tại một cửa hàng văn phòng phẩm gần nhà. Cửa hàng bán bút chì theo hai loại bộ: bộ \(X\) gồm \(A\) chiếc với giá \(B\) yên, còn bộ \(Y\) gồm \(C\) chiếc với giá \(D\) yên.

JOI chọn một trong hai loại bộ \(X\) hoặc \(Y\), rồi mua một số bộ thuộc loại đã chọn. JOI không được mua cả hai loại bộ.

Hãy tính số tiền ít nhất cần trả để mua được ít nhất \(N\) chiếc bút chì.

Dữ liệu vào

Một dòng chứa năm số nguyên \(N, A, B, C, D\).

Dữ liệu ra

In ra số tiền ít nhất, tính bằng yên, để JOI mua được ít nhất \(N\) chiếc bút chì.

Ràng buộc

• \(1 \le N, A, B, C, D \le 1000\).

Ví dụ

10 3 100 5 180

360

6 2 200 3 300

600

Nguồn

JOI 2017/2018, vòng loại, bài 1. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản, theo giấy phép CC BY-SA 4.0.

JOI tìm thấy một bàn cờ Sugoroku ở nhà chú. Bàn cờ gồm \(N+2\) ô nằm trên một đường thẳng. Ô thứ nhất là ô xuất phát, còn ô thứ \(N+2\) là ô đích. Với mỗi \(i\) từ \(1\) đến \(N\), ô thứ \(i+1\) ghi số \(A_i\), bằng \(0\) hoặc \(1\).

Ban đầu, quân cờ được đặt ở ô xuất phát. Người chơi lặp lại việc gieo xúc xắc và tiến quân cờ một số ô bằng số chấm gieo được. Nếu quân cờ dừng ở một ô ghi số \(1\), người chơi thua ngay. Nếu quân cờ đến hoặc vượt qua ô đích mà chưa thua, người chơi thắng.

JOI đến cửa hàng đồ chơi để mua xúc xắc. Cửa hàng bán \(N+1\) loại xúc xắc: loại thứ \(j\) có \(j\) mặt, ghi lần lượt các số \(1,2,\ldots,j\), mỗi số xuất hiện trên đúng một mặt.

JOI muốn mua loại xúc xắc có ít mặt nhất sao cho tồn tại một dãy kết quả gieo giúp JOI thắng. Hãy xác định số mặt của loại xúc xắc cần mua.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

In ra số mặt ít nhất của một loại xúc xắc mà JOI có thể dùng để thắng.

Ràng buộc

• \(1 \le N \le 100\).
• \(0 \le A_i \le 1\) với mọi \(1 \le i \le N\).

Ví dụ

5
0 1 0 0 0

2

5
1 1 1 1 1

6

7
0 0 1 0 1 1 0

3

Nguồn

JOI 2017/2018, vòng loại, bài 2. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản, theo giấy phép CC BY-SA 4.0.

Thành phố JOI được chia thành dạng bàn cờ bởi \(H\) con đường thẳng theo hướng đông - tây và \(W\) con đường thẳng theo hướng bắc - nam. Khoảng cách giữa hai con đường song song liên tiếp bằng \(1\). Thành phố sẽ chọn một đường theo hướng đông - tây và một đường theo hướng bắc - nam trong số \(H+W\) con đường này làm hai tuyến đường chính.

Gọi giao điểm của con đường thứ \(i\) tính từ phía bắc và con đường thứ \(j\) tính từ phía tây là giao lộ \((i,j)\), với \(1 \le i \le H\) và \(1 \le j \le W\). Khoảng cách từ giao lộ \((i,j)\) đến con đường thứ \(m\) tính từ phía bắc là \(|i-m|\), còn khoảng cách đến con đường thứ \(n\) tính từ phía tây là \(|j-n|\). Có \(A_{i,j}\) cư dân sống gần giao lộ \((i,j)\).

Với mỗi cư dân, xét khoảng cách từ giao lộ gần nơi họ sống nhất đến tuyến đường chính gần hơn trong hai tuyến đã chọn. Hãy tìm giá trị nhỏ nhất có thể của tổng khoảng cách này trên tất cả cư dân trong thành phố.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(H,W\).
• Trong \(H\) dòng tiếp theo, dòng thứ \(i\) chứa \(W\) số nguyên \(A_{i,1},A_{i,2},\ldots,A_{i,W}\).

Dữ liệu ra

In ra tổng khoảng cách nhỏ nhất từ giao lộ gần mỗi cư dân nhất đến tuyến đường chính gần hơn trong hai tuyến đã chọn.

Ràng buộc

• \(2 \le H \le 25\).
• \(2 \le W \le 25\).
• \(0 \le A_{i,j} \le 100\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).

Phân nhóm

1. Nhóm 1 (10 điểm): \(A_{i,j}=1\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).
2. Nhóm 2 (90 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

8

5 5
1 2 3 1 5
1 22 11 44 3
1 33 41 53 2
4 92 35 23 1
4 2 6 3 5

164

Nguồn

JOI 2017/2018, vòng loại, bài 3: Trunk Road. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.

Mizuyokan là một loại bánh ngọt Nhật Bản, được làm bằng cách đổ nhân chủ yếu từ đậu đỏ vào khuôn rồi dùng thạch agar để làm đông. JOI có một chiếc bánh mizuyokan hình hộp chữ nhật dài nằm ngang và định ăn chiếc bánh này trong bữa ăn nhẹ hôm nay.

Trên bánh có \(N-1\) vết khía theo chiều dọc để cắt. Chiều dài của bánh là \(L_1+L_2+\cdots+L_N\). Vết khía thứ \(i\) nằm ở vị trí cách đầu bên trái một khoảng \(L_1+L_2+\cdots+L_i\), với \(1 \le i \le N-1\).

Chiếc bánh quá lớn để ăn nguyên cả chiếc, nên JOI sẽ chọn ít nhất một vết khía và cắt theo các vết khía đã chọn để chia bánh thành nhiều miếng. Các miếng không đều nhau sẽ không đẹp mắt, vì vậy JOI muốn hiệu giữa chiều dài miếng dài nhất và chiều dài miếng ngắn nhất là nhỏ nhất có thể.

Hãy tìm giá trị nhỏ nhất của hiệu đó.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(L_i\).

Dữ liệu ra

In ra trên một dòng hiệu nhỏ nhất có thể giữa chiều dài miếng dài nhất và chiều dài miếng ngắn nhất.

Ràng buộc

• \(2 \le N \le 50\).
• \(1 \le L_i \le 1000\) với mọi \(1 \le i \le N\).

Phân nhóm

1. Nhóm 1 (10 điểm): \(N \le 15\).
2. Nhóm 2 (27 điểm): \(L_i \le 10\) với mọi \(1 \le i \le N\).
3. Nhóm 3 (63 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

2

2
1
10

9

5
5
5
5
5
5

0

Nguồn

JOI 2017/2018, vòng loại, bài 4: Mizuyokan. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.

Vương quốc JOI có một khu rừng rộng lớn hình chữ nhật, được chia thành lưới gồm \(H\) hàng theo hướng bắc - nam và \(W\) cột theo hướng đông - tây. Ô ở hàng thứ \(i\) tính từ phía bắc, cột thứ \(j\) tính từ phía tây có \(A_{i,j}\) cây, với \(1 \le i \le H\), \(1 \le j \le W\). Riêng ô ở góc tây bắc có một nhà máy chế biến gỗ và không có cây, tức là \(A_{1,1}=0\).

Chỉ có thể đi vào những ô không có cây. Từ một ô, người ta có thể đi sang ô kề theo hướng đông, tây, nam hoặc bắc nếu ô đó không có cây. Không được đi ra ngoài khu rừng. Là một công trình công cộng của vương quốc, JOI muốn chặt cây để có thể đi lại giữa ô ở góc tây bắc và ô ở góc đông nam.

Ban đầu, JOI đứng ở ô góc tây bắc, nơi có nhà máy chế biến gỗ. JOI có thể đi sang một ô kề theo một trong bốn hướng nếu ô đó không có cây, mất \(1\) phút. JOI cũng có thể đứng tại ô hiện tại và chặt một cây trong một ô kề theo một trong bốn hướng, mất \(1\) phút.

Sau mỗi lần chặt một cây, JOI phải mang cây vừa chặt về nhà máy ở ô góc tây bắc. Tốc độ di chuyển không thay đổi khi mang cây, nhưng trong lúc mang cây, JOI không thể chặt cây khác.

Hãy tìm thời gian ít nhất để chặt cây sao cho hai ô góc tây bắc và đông nam có thể đi lại được với nhau. Thời gian được tính đến khi JOI đã mang cây cuối cùng được chặt về nhà máy.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(H,W\).
• Trong \(H\) dòng tiếp theo, dòng thứ \(i\) chứa \(W\) số nguyên \(A_{i,1},A_{i,2},\ldots,A_{i,W}\).

Dữ liệu ra

In ra trên một dòng thời gian ít nhất, tính bằng phút, để thực hiện yêu cầu.

Ràng buộc

• \(1 \le H \le 30\).
• \(1 \le W \le 30\).
• \((H,W) \ne (1,1)\).
• \(0 \le A_{i,j} \le 10000\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).
• \(A_{1,1}=0\).

Phân nhóm

1. Nhóm 1 (15 điểm): \(1 \le H \le 5\) và \(1 \le W \le 5\).
2. Nhóm 2 (28 điểm): \(A_{i,j} \le A_{i,j+1}\) với mọi \(1 \le i \le H\), \(1 \le j \le W-1\); đồng thời \(A_{i,j} \le A_{i+1,j}\) với mọi \(1 \le i \le H-1\), \(1 \le j \le W\).
3. Nhóm 3 (57 điểm): Không có ràng buộc bổ sung.

Ví dụ

2 3
0 1 2
3 4 5

32

2 5
0 5 0 0 0
0 0 0 9 1

13

2 5
0 2 0 0 0
0 0 0 9 1

11

Nguồn

JOI 2017/2018, vòng loại, bài 5: Deforestation. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.

Có \(N\) tấm thẻ được xếp thành một hàng ngang. Tấm thẻ thứ \(i\) từ trái sang phải ghi số nguyên \(a_i\), với \(1 \le i \le N\).

JOI chơi một trò chơi với những tấm thẻ này. JOI chọn một đoạn gồm ít nhất \(K\) tấm thẻ liên tiếp và thực hiện các bước sau:

1. Sắp xếp các thẻ đã chọn từ trái sang phải theo thứ tự không giảm của số ghi trên thẻ.
2. Ghi ra giấy số trên tấm thẻ thứ \(K\) tính từ bên trái trong các thẻ vừa sắp xếp.
3. Đưa tất cả các thẻ đã chọn về vị trí ban đầu.

JOI thực hiện thao tác này với mọi đoạn gồm ít nhất \(K\) thẻ liên tiếp. Nói cách khác, với mỗi cặp \((l,r)\) thỏa mãn \(1 \le l \le r \le N\) và \(K \le r-l+1\), JOI ghi ra số nhỏ thứ \(K\) trong dãy \(a_l,a_{l+1},\ldots,a_r\).

Sau đó, JOI sắp xếp tất cả các số đã ghi ra theo thứ tự không giảm. Số thứ \(L\) từ trái sang phải trong dãy này là điểm số của JOI. Hãy tìm điểm số đó. Các lần xuất hiện của cùng một giá trị vẫn được tính riêng.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(N,K,L\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\).

Dữ liệu ra

In ra trên một dòng điểm số của JOI.

Ràng buộc

• \(1 \le N \le 200000\).
• \(1 \le K \le N\).
• \(1 \le a_i \le N\) với mọi \(1 \le i \le N\).
• \(1 \le L\).
• Số lượng số nguyên mà JOI ghi ra giấy không nhỏ hơn \(L\).

Phân nhóm

1. Nhóm 1 (6 điểm): \(N \le 100\).
2. Nhóm 2 (33 điểm): \(N \le 4000\).
3. Nhóm 3 (61 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 3 2
4 3 1 2

3

5 3 3
1 5 2 2 4

4

6 2 9
1 5 3 4 2 4

4

6 2 8
1 5 3 4 2 4

3

Nguồn

JOI 2017/2018, vòng loại, bài 6: LthKthNumber. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.