JOI 2020 - Final Round

Công ty Just Odd Inventions, Ltd. nổi tiếng với những phát minh kỳ lạ. Trong bài này, ta gọi công ty là JOI, Ltd.

Công ty vừa phát minh ra sản phẩm mới là những chiếc cà vạt chỉ có ưu điểm là dài. Có \(N+1\) loại cà vạt, được đánh số từ \(1\) đến \(N+1\). Chiếc cà vạt thứ \(i\) (\(1 \le i \le N+1\)) có độ dài \(A_i\).

Công ty tổ chức một buổi thử cà vạt với \(N\) nhân viên tham gia. Ban đầu, nhân viên thứ \(j\) (\(1 \le j \le N\)) đeo một chiếc cà vạt dài \(B_j\). Buổi thử diễn ra như sau:

1. Giám đốc chọn một chiếc cà vạt không được sử dụng trong buổi thử.
2. Mỗi nhân viên chọn một trong những chiếc cà vạt còn lại để thử. Không có hai nhân viên nào chọn cùng một chiếc.
3. Mỗi nhân viên tháo chiếc cà vạt đang đeo và đeo chiếc vừa chọn.

Nếu một nhân viên đang đeo cà vạt dài \(b\) thử chiếc cà vạt dài \(a\), mức độ lạ lẫm mà người đó cảm thấy là \(\max\{a-b,0\}\). Độ kỳ lạ của buổi thử được định nghĩa là mức độ lạ lẫm lớn nhất trong số các nhân viên.

Gọi \(C_k\) là độ kỳ lạ nhỏ nhất có thể của buổi thử khi giám đốc chọn loại bỏ chiếc cà vạt thứ \(k\). Hãy tính \(C_1,C_2,\ldots,C_{N+1}\) từ độ dài các cà vạt mới và các cà vạt mà nhân viên đeo ban đầu.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N
A_1 ... A_{N+1}
B_1 ... B_N

Dữ liệu ra

In ra một dòng chứa \(C_1,C_2,\ldots,C_{N+1}\) theo thứ tự, cách nhau bởi dấu cách.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với \(1 \le i \le N+1\).
• \(1 \le B_j \le 1\,000\,000\,000\) với \(1 \le j \le N\).

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(1\) điểm: \(N \le 10\)
2. \(8\) điểm: \(N \le 2000\)
3. \(91\) điểm: Không có

Ví dụ

3
4 3 7 6
2 6 4

2 2 1 1

5
4 7 9 10 11 12
3 5 7 9 11

4 4 3 2 2 2

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bitaro nhận được một xâu \(S\) dài \(N\) làm quà sinh nhật. Xâu \(S\) chỉ gồm ba loại ký tự J, O và I.

Với mỗi số nguyên dương \(K\), ta gọi xâu gồm đúng \(K\) ký tự J, tiếp theo là \(K\) ký tự O, rồi \(K\) ký tự I là xâu JOI cấp \(K\). Chẳng hạn, JJOOII là xâu JOI cấp \(2\).

Bitaro thích xâu JOI cấp \(K\), nên muốn biến \(S\) thành một xâu như vậy bằng ba thao tác sau, mỗi thao tác có thể thực hiện bao nhiêu lần tùy ý và theo thứ tự bất kỳ:

1. Xóa ký tự đầu tiên của \(S\).
2. Xóa ký tự cuối cùng của \(S\).
3. Xóa một ký tự của \(S\) không phải ký tự đầu tiên hay cuối cùng.

Vì thao tác \(3\) tốn nhiều thời gian, Bitaro muốn dùng thao tác này ít lần nhất có thể. Cho xâu \(S\) dài \(N\) và số nguyên dương \(K\), hãy tìm số lần thực hiện thao tác \(3\) ít nhất để biến \(S\) thành xâu JOI cấp \(K\). Nếu không thể, hãy in ra \(-1\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. \(N,K\) là số nguyên và \(S\) là một xâu.

N K
S

Dữ liệu ra

In ra một dòng chứa số lần thực hiện thao tác \(3\) ít nhất cần thiết để tạo xâu JOI cấp \(K\) từ \(S\), hoặc \(-1\) nếu không thể.

Ràng buộc

• \(3 \le N \le 200\,000\).
• \(1 \le K \le \frac{N}{3}\).
• \(S\) có độ dài \(N\) và chỉ gồm các ký tự J, O, I.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(1\) điểm: \(N \le 21\)
2. \(12\) điểm: \(N \le 3000\)
3. \(87\) điểm: Không có

Ví dụ

10 2
OJIJOIOIIJ

2

9 3
JJJOOOIII

0

9 1
IIIOOOJJJ

-1

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Nước Cộng hòa IOI, nơi JOI-kun sinh sống, nổi tiếng với một hồ nước lớn. Hôm nay có một sự kiện sưu tập dấu diễn ra quanh hồ.

Có \(N\) loại dấu đặt quanh hồ, đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ. Chu vi hồ là \(L\) mét. Loại dấu thứ \(i\) (\(1 \le i \le N\)) nằm cách điểm xuất phát \(X_i\) mét theo chiều kim đồng hồ.

Mỗi người tham gia bắt đầu tại điểm xuất phát. Sau khi sự kiện bắt đầu, họ có thể di chuyển quanh hồ theo cả chiều kim đồng hồ lẫn ngược chiều kim đồng hồ. Chỉ có thể thu thập loại dấu thứ \(i\) nếu đến vị trí của nó không muộn hơn \(T_i\) giây kể từ lúc bắt đầu, tức là đến đúng thời điểm \(T_i\) vẫn được.

JOI-kun tham gia sự kiện và mất \(1\) giây để đi \(1\) mét. Có thể bỏ qua thời gian dành cho mọi hoạt động khác.

Cho số loại dấu, chu vi hồ, vị trí và thời hạn thu thập của mỗi loại dấu, hãy tính số loại dấu nhiều nhất mà JOI-kun có thể thu thập.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N L
X_1 ... X_N
T_1 ... T_N

Dữ liệu ra

In ra một dòng chứa số loại dấu nhiều nhất có thể thu thập.

Ràng buộc

• \(1 \le N \le 200\).
• \(2 \le L \le 1\,000\,000\,000\).
• \(1 \le X_i < L\) với \(1 \le i \le N\).
• \(X_i < X_{i+1}\) với \(1 \le i \le N-1\).
• \(0 \le T_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(5\) điểm: \(N \le 12\), \(L \le 200\) và \(T_i \le 200\) với mọi \(1 \le i \le N\)
2. \(10\) điểm: \(N \le 15\)
3. \(10\) điểm: \(L \le 200\) và \(T_i \le 200\) với mọi \(1 \le i \le N\)
4. \(75\) điểm: Không có

Ví dụ

6 25
3 4 7 17 21 23
11 7 17 10 8 10

4

5 20
4 5 8 13 17
18 23 15 7 10

5

4 19
3 7 12 14
2 0 5 4

0

10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46

5

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Vương quốc JOI có \(N\) thành phố, đánh số từ \(1\) đến \(N\), và \(M\) tuyến xe buýt nối giữa các thành phố, đánh số từ \(1\) đến \(M\). Tuyến thứ \(i\) (\(1 \le i \le M\)) đi từ thành phố \(U_i\) đến thành phố \(V_i\), với giá vé \(C_i\) yên. Trên tuyến này, hành khách chỉ được lên xe ở \(U_i\) và chỉ được xuống xe ở \(V_i\). Có thể có nhiều tuyến đi từ cùng một thành phố đến cùng một thành phố khác.

Thế vận hội sắp được tổ chức tại vương quốc JOI. Ngài K là Bộ trưởng Giao thông của vương quốc. Ngay trước Thế vận hội, ngài K sẽ chọn nhiều nhất một tuyến xe buýt và đảo chiều tuyến đó mà không thay đổi giá vé. Cụ thể, nếu chọn tuyến thứ \(i\), trong suốt Thế vận hội tuyến đó sẽ đi từ \(V_i\) đến \(U_i\) thay vì từ \(U_i\) đến \(V_i\). Chi phí đảo chiều là \(D_i\) yên và do ngài K chi trả. Để tránh nhầm lẫn, không được đảo chiều tuyến xe trong thời gian diễn ra Thế vận hội.

Trong Thế vận hội, ngài K sẽ đi xe buýt từ thành phố \(1\) đến thành phố \(N\) rồi quay về thành phố \(1\). Bằng cách chọn một tuyến để đảo chiều, hoặc không đảo chiều tuyến nào, ngài muốn tối thiểu hóa tổng tiền vé của chuyến đi khứ hồi và chi phí đảo chiều.

Cho số thành phố và thông tin các tuyến xe buýt, hãy tính tổng chi phí nhỏ nhất này. Nếu không có lựa chọn hợp lệ nào cho phép thực hiện chuyến đi khứ hồi giữa thành phố \(1\) và thành phố \(N\), hãy in ra \(-1\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N M
U_1 V_1 C_1 D_1
...
U_M V_M C_M D_M

Dữ liệu ra

In ra tổng nhỏ nhất của tiền vé đi khứ hồi và chi phí đảo chiều tuyến đã chọn. Nếu không thể thực hiện chuyến đi khứ hồi giữa thành phố \(1\) và thành phố \(N\), in ra \(-1\).

Ràng buộc

• \(2 \le N \le 200\).
• \(1 \le M \le 50\,000\).
• \(1 \le U_i \le N\) với \(1 \le i \le M\).
• \(1 \le V_i \le N\) với \(1 \le i \le M\).
• \(U_i \ne V_i\) với \(1 \le i \le M\).
• \(0 \le C_i \le 1\,000\,000\) với \(1 \le i \le M\).
• \(0 \le D_i \le 1\,000\,000\,000\) với \(1 \le i \le M\).

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(5\) điểm: \(M \le 1000\)
2. \(11\) điểm: \(M\) chẵn; \(U_{2i-1}=U_{2i}\), \(V_{2i-1}=V_{2i}\) và \(C_{2i-1}=C_{2i}\) với mọi \(1 \le i \le M/2\)
3. \(21\) điểm: \(C_i=0\) với mọi \(1 \le i \le M\)
4. \(63\) điểm: Không có

Ví dụ

4 5
1 2 4 4
1 3 2 1
4 3 1 2
4 1 6 1
2 4 2 5

10

4 10
1 2 4 4
1 2 4 4
1 3 2 1
1 3 2 1
4 3 1 2
4 3 1 2
4 1 6 1
4 1 6 1
2 4 2 5
2 4 2 5

10

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

2

4 5
1 2 4 4
1 3 2 4
4 3 1 5
4 1 6 1
2 4 2 5

12

4 5
2 1 4 4
1 3 2 1
4 3 1 2
4 3 6 1
2 4 2 5

-1

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Làng JOI có \(N\) khu dân cư, đánh số từ \(1\) đến \(N\) và nằm trên một đường thẳng. Hiện tại, mỗi khu đều đang có cháy. Tại thời điểm \(0\), cường độ đám cháy ở khu thứ \(i\) (\(1 \le i \le N\)) là \(S_i\), với \(S_i>0\).

Từ thời điểm \(0\), gió thổi theo hướng từ khu thứ \(1\) đến khu thứ \(N\). Xét mỗi cặp khu kề nhau: nếu tại thời điểm \(t \ge 0\), đám cháy ở khu phía đầu gió mạnh hơn đám cháy ở khu phía cuối gió, thì tại thời điểm \(t+1\), cường độ đám cháy ở khu phía cuối gió sẽ bằng cường độ ở khu phía đầu gió tại thời điểm \(t\). Ngược lại, cường độ ở khu phía cuối gió không thay đổi.

Cụ thể, gọi \(S_i(t)\) là cường độ đám cháy ở khu thứ \(i\) tại thời điểm \(t\). Với mọi \(1 \le i \le N\) và mọi thời điểm nguyên \(t \ge 1\):

Quy ước \(S_0(t)=0\) với mọi \(t \ge 0\), và \(S_i(0)=S_i\) với mọi \(1 \le i \le N\).

Bạn là một lính cứu hỏa và có \(Q\) phương án dập lửa. Bạn dự định chỉ thực hiện một trong số đó. Trong phương án thứ \(j\) (\(1 \le j \le Q\)), tại thời điểm \(T_j\), bạn dùng chất chữa cháy để dập lửa ở tất cả các khu thứ \(k\) thỏa mãn \(L_j \le k \le R_j\). Để dập đám cháy có cường độ \(s\) trong một khu, cần \(s\) lít chất chữa cháy. Vì vậy, lượng chất chữa cháy cần cho phương án thứ \(j\), tính bằng lít, là:

Để lựa chọn phương án thực hiện, bạn muốn biết lượng chất chữa cháy cần thiết cho từng phương án. Các phương án được xét độc lập, không thực hiện liên tiếp.

Cho cường độ các đám cháy tại thời điểm \(0\) và thông tin các phương án, hãy tính lượng chất chữa cháy cần thiết cho mỗi phương án.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N Q
S_1 ... S_N
T_1 L_1 R_1
...
T_Q L_Q R_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa lượng chất chữa cháy, tính bằng lít, cần cho phương án thứ \(j\).

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le Q \le 200\,000\).
• \(1 \le S_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(1 \le T_j \le N\) với \(1 \le j \le Q\).
• \(1 \le L_j \le R_j \le N\) với \(1 \le j \le Q\).

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(1\) điểm: \(N \le 200\) và \(Q \le 200\)
2. \(6\) điểm: \(T_1=T_2=\cdots=T_Q\)
3. \(7\) điểm: \(L_j=R_j\) với mọi \(1 \le j \le Q\)
4. \(6\) điểm: \(S_i \le 2\) với mọi \(1 \le i \le N\)
5. \(80\) điểm: Không có

Ví dụ

5 5
9 3 2 6 5
1 1 3
2 1 5
3 2 5
4 3 3
5 3 5

21
39
33
9
27

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

28
21
34
4
64
43
55
9
27
9

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

9
9
3
4
3
4
5
9
9
9

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

28
27
34
4
64
43
55
9
27
9

20 20
2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
1 1 14
2 3 18
4 10 15
8 2 17
9 20 20
4 8 19
7 2 20
11 1 5
13 2 8
20 1 20
2 12 15
7 1 14
12 7 18
14 2 17
9 19 20
12 12 12
6 2 15
11 2 15
19 12 17
4 1 20

25
30
12
32
2
24
38
10
14
40
8
28
24
32
4
2
28
28
12
40

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.