JOI 2021 - Vòng chung kết quốc gia - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2021 - Growing Vegetables is Fun 4	100 (p)	2.0s	512M
2	JOI 2021 - Snowball	100 (p)	3.0s	512M
3	JOI 2021 - Group Photo	100 (p)	4.0s	512M
4	JOI 2021 - Robot	100 (p)	4.0s	512M
5	JOI 2021 - Dungeon 3	100 (p)	3.0s	512M

1. JOI 2021 - Growing Vegetables is Fun 4

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

Bitaro thích làm vườn. Hiện cậu đang trồng một loại cây gọi là cỏ Biba trong vườn nhà. Có \(N\) cây cỏ Biba được trồng thành một hàng từ tây sang đông, đánh số từ \(1\) đến \(N\) theo thứ tự đó. Hiện tại, chiều cao của cây thứ \(i\) (\(1 \le i \le N\)) là \(A_i\).

Nhờ được cải tiến giống, mỗi lần được tưới nước, một cây cỏ Biba sẽ cao thêm \(1\) đơn vị. Để khu vườn trông đẹp hơn, Bitaro muốn tưới nước một số lần sao cho điều kiện sau được thỏa mãn:

Gọi \(B_i\) là chiều cao của cây thứ \(i\) sau khi hoàn thành tất cả các lần tưới. Phải tồn tại một số nguyên \(k\) (\(1 \le k \le N\)) sao cho \(B_j < B_{j+1}\) với mọi \(1 \le j \le k-1\), và \(B_j > B_{j+1}\) với mọi \(k \le j \le N-1\).

Tuy nhiên, Bitaro vụng về nên mỗi lần chỉ có thể tưới đồng thời tất cả các cây trong một đoạn liên tiếp. Cụ thể, trong một lần tưới, cậu chọn hai số nguyên \(L,R\) (\(1 \le L \le R \le N\)) rồi tưới các cây \(L,L+1,\ldots,R\).

Cho số lượng cây cỏ Biba và chiều cao hiện tại của chúng, hãy tìm số lần tưới ít nhất để thỏa mãn điều kiện trên.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N
A_1 A_2 ... A_N

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra một dòng chứa số lần tưới ít nhất cần thực hiện.

Ràng buộc

\(2 \le N \le 200\,000\).
\(1 \le A_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

Nhóm 1 (40 điểm): \(N \le 2000\).
Nhóm 2 (60 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

5
3 2 2 3 1

Output

Giải thích

Có thể thỏa mãn điều kiện bằng ba lần tưới như sau:

Chọn \(L=2\), \(R=5\) và tưới các cây \(2,3,4,5\). Chiều cao các cây từ tây sang đông trở thành \(3,3,3,4,2\).
Chọn \(L=2\), \(R=3\) và tưới các cây \(2,3\). Chiều cao các cây trở thành \(3,4,4,4,2\).
Chọn \(L=3\), \(R=3\) và tưới cây \(3\). Chiều cao các cây trở thành \(3,4,5,4,2\).

Không thể thỏa mãn điều kiện bằng ít hơn ba lần tưới, nên đáp án là \(3\).

Ví dụ 2

Input

5
9 7 5 3 1

Output

Giải thích

Điều kiện đã được thỏa mãn ngay từ đầu, nên không cần tưới lần nào. Đáp án là \(0\).

Ví dụ 3

Input

2
2021 2021

Output

Giải thích

Có thể thỏa mãn điều kiện bằng một lần tưới: chọn \(L=1\), \(R=1\) để tưới cây \(1\), hoặc chọn \(L=2\), \(R=2\) để tưới cây \(2\).

Ví dụ 4

Input

8
12 2 34 85 4 91 29 85

Output

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.

2. JOI 2021 - Snowball

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

Đồng bằng JOI là một đồng bằng rất rộng trải dài từ tây sang đông. Có thể xem đồng bằng này là một trục số, với chiều dương hướng về phía đông. Mùa đông đã đến và trên đồng bằng có \(N\) quả cầu tuyết ở các tọa độ khác nhau. Các quả cầu được đánh số từ \(1\) đến \(N\) theo thứ tự từ tây sang đông. Ban đầu, quả cầu thứ \(i\) (\(1 \le i \le N\)) nằm tại tọa độ nguyên \(X_i\).

Vào mùa đông, gió trên đồng bằng JOI thổi rất mạnh. Bạn có dữ liệu quan sát gió trong \(Q\) ngày. Gió của ngày thứ \(j\) (\(1 \le j \le Q\)) được biểu diễn bởi số nguyên \(W_j\). Nếu \(W_j\) âm, gió thổi về phía tây; nếu \(W_j\) không âm, gió thổi về phía đông. Độ mạnh của gió là \(|W_j|\).

Khi gió thổi, mỗi quả cầu tuyết lăn cùng hướng với gió một quãng đường bằng độ mạnh của gió. Nói cách khác, nếu đầu ngày thứ \(j\) một quả cầu ở tọa độ \(x\), nó sẽ lăn từ \(x\) đến \(x+W_j\) và kết thúc ngày tại \(x+W_j\). Trong mỗi ngày, tất cả các quả cầu lăn đồng thời và cùng tốc độ.

Ban đầu, toàn bộ đồng bằng được phủ tuyết. Khi một quả cầu lăn qua một đoạn còn tuyết, tuyết bám vào quả cầu làm tăng khối lượng của nó, và tuyết trên đoạn đó biến mất. Cụ thể, với một số nguyên \(a\), nếu đoạn từ \(a\) đến \(a+1\) còn tuyết, khi một quả cầu lăn qua đoạn này, khối lượng của nó tăng \(1\) và tuyết trên đoạn đó biến mất. Nếu quả cầu lăn qua đoạn không còn tuyết, khối lượng của nó không đổi.

Ban đầu, khối lượng của mọi quả cầu đều bằng \(0\). Trong \(Q\) ngày quan sát không có tuyết mới rơi.

Cho tọa độ ban đầu của các quả cầu và dữ liệu gió trong \(Q\) ngày, hãy tính khối lượng của từng quả cầu vào cuối ngày thứ \(Q\).

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N Q
X_1 X_2 ... X_N
W_1
...
W_Q

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) chứa khối lượng của quả cầu thứ \(i\) vào cuối ngày thứ \(Q\).

Ràng buộc

\(1 \le N \le 200\,000\).
\(1 \le Q \le 200\,000\).
\(|X_i| \le 10^{12}\) với mọi \(1 \le i \le N\).
\(X_i < X_{i+1}\) với mọi \(1 \le i < N\).
\(|W_j| \le 10^{12}\) với mọi \(1 \le j \le Q\).

Phân nhóm

Nhóm 1 (33 điểm): \(N \le 2000\), \(Q \le 2000\).
Nhóm 2 (67 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Tọa độ và khối lượng của các quả cầu từ \(1\) đến \(4\) thay đổi như sau:

Ban đầu, các tọa độ là \(-2,3,5,8\) và các khối lượng là \(0,0,0,0\).
Ngày thứ nhất, gió thổi về phía đông với độ mạnh \(2\). Cuối ngày, các tọa độ là \(0,5,7,10\) và các khối lượng là \(2,2,2,2\).
Ngày thứ hai, gió thổi về phía tây với độ mạnh \(4\). Cuối ngày, các tọa độ là \(-4,1,3,6\) và các khối lượng là \(4,4,2,3\).
Ngày thứ ba, gió thổi về phía đông với độ mạnh \(7\). Cuối ngày, các tọa độ là \(3,8,10,13\) và các khối lượng là \(5,4,2,6\).

Vì vậy, lần lượt in ra \(5,4,2,6\).

Ví dụ 2

Input

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

Output

3000000000000

Ví dụ 3

Input

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6

Output

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.

3. JOI 2021 - Group Photo

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

Vào ngày cuối của một trại huấn luyện, \(N\) người tham gia sẽ chụp ảnh tập thể. Họ được đánh số từ \(1\) đến \(N\) theo thứ tự chiều cao tăng dần. Chiều cao của người thứ \(h\) là \(h\) (\(1 \le h \le N\)).

Mọi người đứng trên một cầu thang để chụp ảnh. Cầu thang có đúng \(N\) bậc, đánh số từ \(1\) đến \(N\) từ thấp lên cao. Bậc \(i+1\) cao hơn bậc \(i\) đúng \(2\) đơn vị (\(1 \le i < N\)). Cầu thang rất hẹp nên mỗi bậc chỉ có một người đứng, tạo thành một hàng dọc.

Buổi chụp ảnh sắp bắt đầu. Hiện tại, người thứ \(H_i\) đang đứng trên bậc \(i\) (\(1 \le i \le N\)).

Do chiều cao của mọi người chênh lệch nhiều, một số người có thể bị người khác che khuất trong ảnh. Bạn muốn sắp xếp lại vị trí để ít nhất phần đỉnh đầu của mọi người đều xuất hiện trong ảnh. Cụ thể, cần thỏa mãn điều kiện:

Gọi \(a_i\) là chiều cao của người đứng trên bậc \(i\). Khi đó, \(a_i < a_{i+1}+2\) với mọi \(1 \le i < N\).

Bạn chỉ được đổi chỗ hai người đứng ở hai bậc liên tiếp. Trong một thao tác, chọn một bậc \(i\) (\(1 \le i < N\)), rồi đổi chỗ người trên bậc \(i\) với người trên bậc \(i+1\).

Cho thứ tự hiện tại của mọi người, hãy tìm số thao tác ít nhất để thỏa mãn điều kiện trên.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N
H_1 H_2 ... H_N

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất cần thực hiện.

Ràng buộc

\(3 \le N \le 5000\).
\(1 \le H_i \le N\) với mọi \(1 \le i \le N\).
\(H_i \ne H_j\) với mọi \(1 \le i < j \le N\).

Phân nhóm

Nhóm 1 (5 điểm): \(N \le 9\).
Nhóm 2 (7 điểm): \(N \le 20\).
Nhóm 3 (32 điểm): \(N \le 200\).
Nhóm 4 (20 điểm): \(N \le 800\).
Nhóm 5 (36 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

5
3 5 2 4 1

Output

Giải thích

Có thể thực hiện ba thao tác như sau:

Đổi chỗ hai người trên bậc \(2\) và \(3\). Chiều cao từ bậc thấp lên bậc cao trở thành \(3,2,5,4,1\).
Đổi chỗ hai người trên bậc \(4\) và \(5\). Chiều cao trở thành \(3,2,5,1,4\).
Đổi chỗ hai người trên bậc \(3\) và \(4\). Chiều cao trở thành \(3,2,1,5,4\) và điều kiện được thỏa mãn.

Không thể thỏa mãn điều kiện bằng ít hơn ba thao tác, nên in ra \(3\).

Ví dụ 2

Input

5
3 2 1 5 4

Output

Giải thích

Điều kiện đã được thỏa mãn nên không cần thực hiện thao tác nào.

Ví dụ 3

Input

9
6 1 3 4 9 5 7 8 2

Output

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.

4. JOI 2021 - Robot

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

Thị trấn IOI có \(N\) giao lộ, đánh số từ \(1\) đến \(N\), và \(M\) con đường, đánh số từ \(1\) đến \(M\). Mỗi con đường nối hai giao lộ khác nhau và có thể đi theo cả hai chiều. Đường thứ \(i\) (\(1 \le i \le M\)) nối giao lộ \(A_i\) với giao lộ \(B_i\). Không có hai con đường khác nhau nối cùng một cặp giao lộ.

Mỗi đường được sơn một màu, biểu diễn bằng một số nguyên từ \(1\) đến \(M\). Hiện tại, màu của đường thứ \(i\) là \(C_i\). Nhiều đường có thể có cùng màu.

Công ty JOI đã phát triển một robot di chuyển giữa các giao lộ của thị trấn IOI. Khi bạn chỉ định một màu, robot đi theo đường có màu đó tới giao lộ kề bên. Tuy nhiên, nếu tại giao lộ hiện tại có từ hai đường mang màu được chỉ định trở lên, robot không thể xác định phải đi đường nào và sẽ dừng lại.

Robot hiện ở giao lộ \(1\). Bạn muốn đưa robot tới giao lộ \(N\) bằng cách chỉ định màu một số lần. Vì các màu hiện tại có thể không cho phép làm điều đó, bạn được sơn lại một số con đường trước khi robot di chuyển. Với chi phí \(P_i\) yên, có thể sơn lại đường thứ \(i\) thành một màu bất kỳ từ \(1\) đến \(M\).

Cho thông tin về các giao lộ và con đường, hãy tìm tổng chi phí nhỏ nhất. Nếu dù sơn lại các đường như thế nào cũng không thể đưa robot tới giao lộ \(N\), hãy in ra \(-1\).

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N M
A_1 B_1 C_1 P_1
...
A_M B_M C_M P_M

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra một dòng chứa tổng chi phí nhỏ nhất. Nếu không thể đưa robot tới giao lộ \(N\) dù sơn lại các đường như thế nào, in ra \(-1\).

Ràng buộc

\(2 \le N \le 100\,000\).
\(1 \le M \le 200\,000\).
\(1 \le A_i < B_i \le N\) với mọi \(1 \le i \le M\).
\((A_i,B_i) \ne (A_j,B_j)\) với mọi \(1 \le i < j \le M\).
\(1 \le C_i \le M\) với mọi \(1 \le i \le M\).
\(1 \le P_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le M\).

Phân nhóm

Nhóm 1 (34 điểm): \(N \le 1000\), \(M \le 2000\).
Nhóm 2 (24 điểm): \(P_i=1\) với mọi \(1 \le i \le M\).
Nhóm 3 (42 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Sơn lại đường \(4\) từ màu \(3\) sang màu \(4\) với chi phí \(1\) yên. Sơn lại đường \(6\) từ màu \(4\) sang màu \(2\) với chi phí \(2\) yên. Tổng chi phí là \(3\) yên.

Sau đó, chỉ định màu \(2\) để robot đi từ giao lộ \(1\) tới giao lộ \(2\). Tiếp theo, chỉ định màu \(4\) để robot đi tới giao lộ \(4\).

Không thể đưa robot tới giao lộ \(4\) với chi phí nhỏ hơn \(3\) yên, nên in ra \(3\).

Ví dụ 2

Input

5 2
1 4 1 2
3 5 1 4

Output

-1

Giải thích

Dù sơn lại các đường như thế nào cũng không thể đưa robot tới giao lộ \(5\), nên in ra \(-1\).

Ví dụ 3

Input

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của nhóm \(2\).

Ví dụ 4

Input

Output

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.

5. JOI 2021 - Dungeon 3

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

Có một hầm ngục gồm \(N+1\) tầng và \(M\) người chơi bên trong. Các tầng được đánh số từ \(1\) đến \(N+1\) theo thứ tự từ gần cửa vào nhất. Những người chơi được đánh số từ \(1\) đến \(M\).

Để đi từ tầng \(i\) sang tầng \(i+1\) (\(1 \le i \le N\)), người chơi phải tiêu hao \(A_i\) đơn vị năng lượng. Hầm ngục chỉ cho phép đi một chiều: chỉ có thể di chuyển từ tầng \(i\) sang tầng \(i+1\).

Trên mỗi tầng từ \(1\) đến \(N\) có một suối hồi phục. Tại suối ở tầng \(i\), người chơi có thể trả \(B_i\) đồng xu để hồi phục \(1\) đơn vị năng lượng. Có thể sử dụng suối nhiều lần miễn là có đủ xu. Tuy nhiên, mỗi người chơi có một giới hạn năng lượng riêng, và năng lượng không được vượt quá giới hạn đó kể cả khi sử dụng suối hồi phục.

Người chơi thứ \(j\) (\(1 \le j \le M\)) hiện ở tầng \(S_j\), có năng lượng hiện tại bằng \(0\) và giới hạn năng lượng là \(U_j\). Người này muốn tới tầng \(T_j\) mà năng lượng không bao giờ nhỏ hơn \(0\) trên đường đi.

Cho thông tin về hầm ngục và những người chơi, với mỗi người hãy xác định có thể tới tầng đích hay không. Nếu có thể, hãy tìm số đồng xu ít nhất cần dùng.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N M
A_1 A_2 ... A_N
B_1 B_2 ... B_N
S_1 T_1 U_1
...
S_M T_M U_M

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra \(M\) dòng. Dòng thứ \(j\) (\(1 \le j \le M\)) chứa số đồng xu ít nhất mà người chơi thứ \(j\) cần để tới tầng \(T_j\). Nếu người đó không thể tới tầng \(T_j\), in ra \(-1\).

Ràng buộc

\(1 \le N \le 200\,000\).
\(1 \le M \le 200\,000\).
\(1 \le A_i \le 200\,000\) với mọi \(1 \le i \le N\).
\(1 \le B_i \le 200\,000\) với mọi \(1 \le i \le N\).
\(1 \le S_j < T_j \le N+1\) với mọi \(1 \le j \le M\).
\(1 \le U_j \le 100\,000\,000\) với mọi \(1 \le j \le M\).

Phân nhóm

Nhóm 1 (11 điểm): \(N \le 3000\), \(M \le 3000\).
Nhóm 2 (14 điểm): \(U_1=U_2=\cdots=U_M\).
Nhóm 3 (31 điểm): \(T_j=N+1\) với mọi \(1 \le j \le M\).
Nhóm 4 (44 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Người chơi \(1\) có giới hạn năng lượng là \(3\), nên không thể đi từ tầng \(2\) tới tầng \(3\). Vì vậy, dòng đầu tiên là \(-1\).

Người chơi \(2\) có giới hạn năng lượng là \(4\) và có thể tới tầng \(6\) như sau:

Ở tầng \(1\), trả \(8\) xu để năng lượng đạt \(4\), rồi đi tới tầng \(2\). Năng lượng còn \(1\).
Ở tầng \(2\), trả \(15\) xu để năng lượng đạt \(4\), rồi đi tới tầng \(3\). Năng lượng còn \(0\).
Ở tầng \(3\), trả \(4\) xu để năng lượng đạt \(4\), rồi đi tới tầng \(4\). Năng lượng còn \(3\).
Ở tầng \(4\), không trả thêm xu mà đi tới tầng \(5\). Năng lượng còn \(2\).
Ở tầng \(5\), trả \(2\) xu để năng lượng đạt \(4\), rồi đi tới tầng \(6\). Năng lượng còn \(0\).

Tổng cộng cần \(29\) xu. Không thể tới tầng \(6\) với ít hơn \(29\) xu, nên dòng thứ hai là \(29\).

Ví dụ 2

Input

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

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của nhóm \(3\).

Ví dụ 3

Input

20 20
2 3 2 11 4 6 9 15 17 14 8 17 3 12 20 4 19 8 4 5
19 3 18 2 13 7 5 19 10 1 12 8 1 15 20 1 13 2 18 6
12 15 67
7 15 18
16 17 14
9 21 97
1 19 43
3 18 31
16 20 70
7 20 28
1 16 61
3 5 69
9 10 15
2 13 134
11 19 23
16 20 14
5 21 16
15 20 11
7 11 54
7 16 16
13 17 10
3 15 135

Output

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.