JOI 2026 - Bán kết

Có \(N\) nhóm khách, mỗi nhóm gồm hai người và phải ngồi ở hai ghế kề nhau, cùng hai khách VIP đi một mình. Có \(2N+2\) ghế trên một hàng, được đánh số từ \(1\) đến \(2N+2\) theo thứ tự từ trái sang phải; độ thoải mái ghế \(i\) là \(A_i\). Mỗi khách được xếp vào đúng một ghế và mỗi ghế có đúng một khách, không có hai khách ngồi chung ghế. Hãy xếp tất cả khách để tổng độ thoải mái của hai ghế dành cho VIP là lớn nhất.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(A_1,\ldots,A_{2N+2}\).

Dữ liệu ra

In tổng độ thoải mái lớn nhất của hai ghế VIP.

Ràng buộc

• \(1\le N\le200000\).
• \(1\le A_i\le10^9\).
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(10\) điểm: \(N=1\).
2. \(10\) điểm: \(N\le2\).
3. \(10\) điểm: \(N\le3\).
4. \(30\) điểm: \(N\le2000\).
5. \(40\) điểm: không có ràng buộc thêm.

Ví dụ

2
20 60 40 30 10 50

90

1
1000000000 1000000000 1 1

2000000000

4
4 10 8 6 7 6 7 8 12 3

16

Nguồn

JOI 2025/2026 Semifinal Stage, bài Seats 3. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.

JOI-kun sở hữu một cửa hàng đá quý. Có \(N\) khách muốn mua đá quý tại cửa hàng. Khách \(i\) có thể đến cửa hàng vào bất kỳ thời điểm nào từ \(L_i\) đến \(R_i\), kể cả hai đầu mút, và muốn mua \(C_i\) viên đá quý. Cửa hàng luôn có đủ hàng.

Vì bận rộn nên JOI-kun không thể mở cửa hàng liên tục. Cậu cân nhắc \(M\) phương án mở cửa. Trong phương án \(j\), cửa hàng mở liên tục từ thời điểm \(S_j-0.1\) đến \(T_j+0.1\). Khách \(i\) sẽ đến và mua \(C_i\) viên nếu tồn tại ít nhất một thời điểm thuộc cả \([L_i,R_i]\) và khoảng mở cửa; nếu không thì khách không mua. Hãy tính tổng số đá quý bán được cho từng phương án.

Dữ liệu vào

Dòng đầu chứa \(N\). \(N\) dòng tiếp theo, dòng \(i\) chứa \(L_i,R_i,C_i\). Dòng kế tiếp chứa \(M\). \(M\) dòng cuối, dòng \(j\) chứa \(S_j,T_j\).

Dữ liệu ra

In \(M\) dòng; dòng \(j\) là số đá quý bán được trong phương án \(j\).

Ràng buộc

• \(1\le N,M\le300000\).
• \(1\le L_i<R_i\le1000000\).
• \(1\le S_j\le T_j\le1000000\).
• \(1\le C_i\le10^9\).
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(12\) điểm: \(N,M\le1000\).
2. \(17\) điểm: \(S_j=T_j\) với mọi \(j\).
3. \(21\) điểm: \(S_j=1\) với mọi \(j\).
4. \(23\) điểm: \(S_j\le S_{j+1}\) và \(T_j\le T_{j+1}\) với mọi \(j<M\).
5. \(27\) điểm: không có ràng buộc thêm.

Ví dụ

3
3 4 10
5 8 20
6 10 30
3
4 6
1 2
6 8

60
0
50

4
10 90 1
40 60 2
10 20 4
80 90 8
3
1 15
1 60
1 100

5
7
15

10
55 882 861052753
104 734 331227764
492 694 240198464
481 506 377367203
131 185 327968773
124 129 970226535
92 125 133053911
356 442 758055457
21 759 730522637
259 481 948997757
9
50 287
510 735
158 431
113 768
328 894
783 881
163 692
42 862
43 752

4303050130
2163001618
3957825141
5678671254
4247422035
861052753
4575390808
5678671254
5678671254

Nguồn

JOI 2025/2026 Semifinal Stage, bài Jeweler. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.

Cửa hàng có \(100\) loại quần áo, đánh số từ \(1\) đến \(100\), với số lượng không giới hạn. Bitaro có thể mua từ \(0\) chiếc trở lên, kể cả nhiều chiếc cùng loại. Khi nhiệt độ là \(t\) và Bitaro mặc các loại \(s_1,s_2,\ldots,s_k\), nhiệt độ cảm nhận là \(t+s_1+s_2+\cdots+s_k\); cậu có thể mặc \(0\) chiếc hoặc bất kỳ tập con nào của chính các chiếc đã mua, và mỗi chiếc mua chỉ được mặc nhiều nhất một lần trong một ngày. Những chiếc quần áo đã mua có thể được dùng lại trong các ngày khác nhau.

Biết nhiệt độ của \(N\) ngày lần lượt là \(A_1<A_2<\cdots<A_N\), hãy xác định có thể mua quần áo để mỗi ngày đều chọn được cách mặc cho nhiệt độ cảm nhận đúng \(23\) hay không. Nếu có, hãy tìm số chiếc phải mua nhỏ nhất và in một phương án tối ưu.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(A_1,\ldots,A_N\).

Dữ liệu ra

Nếu không thể, in No trên một dòng. Nếu có thể, in đúng ba dòng:

1. Yes.
2. Số quần áo tối thiểu \(k\).
3. \(k\) số nguyên \(s_1,s_2,\ldots,s_k\) là loại của các chiếc quần áo được mua.

Nếu \(k=0\), dòng thứ ba là một dòng trống. Các loại có thể được in theo thứ tự bất kỳ; nếu có nhiều phương án tối ưu, in bất kỳ phương án nào.

Ràng buộc

• \(1\le N\le81\).
• \(-40\le A_i\le40\), các \(A_i\) tăng dần.
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(6\) điểm: \(N=1\).
2. \(14\) điểm: \(N\le3\).
3. \(15\) điểm: \(A_{i+1}=A_i+1\) và \(A_N=23\).
4. \(16\) điểm: mọi \(A_i\ge12\).
5. \(9\) điểm: mọi \(A_i\ge4\).
6. \(21\) điểm: mọi \(A_i\ge-8\).
7. \(19\) điểm: không có ràng buộc thêm.

Ví dụ

3
17 20 23

Yes
2
3 3

1
24

No

5
-1 3 6 10 16

Yes
3
4 7 13

3
21 22 23

Yes
2
1 1

Nguồn

JOI 2025/2026 Semifinal Stage, bài Clothes. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.

JOI có một cây gốc tại thành phố \(1\); có \(N\) thành phố và \(N-1\) con đường hai chiều. Đường thứ \(i\) nối \(P_i\) với \(i+1\) và dòng sông tương ứng chảy từ \(P_i\) đến \(i+1\). Mỗi thành phố có đúng một chiếc đèn. Ban đầu sức mạnh mọi đèn bằng \(0\) và không thành phố nào được chiếu sáng.

Có thể thực hiện từ \(0\) chuyến đi bè trở lên. Mỗi chuyến bắt đầu ở thành phố \(1\), đi theo một đường có hướng xuống cây và kết thúc tại một thành phố tùy chọn; sức mạnh đèn tại mỗi thành phố trên đường đi, kể cả hai đầu, tăng đúng \(1\). Có thể kết thúc chuyến đi ngay tại thành phố \(1\) mà không đi qua sông nào; đèn tại thành phố \(1\) vẫn tăng sức mạnh thêm \(1\). Nếu kết thúc tại thành phố \(t\), chuyến đi tốn \(C_t\).

Đèn sức mạnh \(l\) tại một thành phố chiếu sáng mọi thành phố có thể đến từ nó qua ít hơn \(l\) con đường hai chiều, không phụ thuộc chiều chảy của sông. Hãy tìm tổng chi phí nhỏ nhất để mọi thành phố được ít nhất một đèn chiếu sáng.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(P_1,\ldots,P_{N-1}\). Dòng thứ ba chứa \(C_1,\ldots,C_N\).

Dữ liệu ra

In tổng chi phí nhỏ nhất.

Ràng buộc

• \(2\le N\le700\).
• \(1\le P_i\le i\).
• \(1\le C_i\le10^9\).
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(13\) điểm: \(N\le8\).
2. \(25\) điểm: \(N\le100\).
3. \(7\) điểm: \(P_i=1\) với mọi \(i\).
4. \(11\) điểm: \(P_i=i\) với mọi \(i\).
5. \(16\) điểm: mỗi thành phố là cha của nhiều nhất hai thành phố khác.
6. \(28\) điểm: không có ràng buộc thêm.

Ví dụ

5
1 2 2 4
10 4 8 9 5

9

9
1 1 1 2 5 5 5 3
100 70 80 90 60 30 40 50 30

90

Nguồn

JOI 2025/2026 Semifinal Stage, bài River Rafting. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.

Quốc gia JOI gồm \(N\) hòn đảo, được đánh số từ \(1\) đến \(N\). Ban đầu không có cây cầu nào nối các đảo, khiến cuộc sống của người dân gặp nhiều bất tiện. Bạn là bộ trưởng của quốc gia JOI và quyết định thực hiện một dự án công để xây cầu. Có \(M\) kế hoạch xây cầu hai chiều. Kế hoạch \(j\) nối \(A_j\) với \(B_j\) với chi phí \(C_j\); mọi chi phí đôi một khác nhau, và nếu thực hiện tất cả kế hoạch thì đồ thị liên thông.

Vì ngân sách quốc gia có hạn, bạn quyết định thực hiện dự án như sau: chọn một đảo \(s\) làm thủ đô, rồi thực hiện đúng \(N-1\) lần: trong các kế hoạch chưa thực hiện có đúng một đầu cầu đã đi được từ thủ đô và đầu kia chưa đi được, chọn kế hoạch rẻ nhất và xây cầu đó. Các điều kiện trên bảo đảm mỗi bước luôn có lựa chọn duy nhất và cuối cùng mọi đảo liên thông.

Rin đang cân nhắc chuyển đến sống tại quốc gia JOI. Để lựa chọn nơi ở, cô tính độ bất tiện của mỗi hòn đảo như sau. Gọi \(D_{s,i}\) là số cầu đã xây cho đến thời điểm đảo \(i\) lần đầu đi được từ thủ đô \(s\); đặt \(D_{i,i}=0\). Độ bất tiện của đảo \(i\) là \(\sum_{s=1}^{N}D_{s,i}\). Hãy trả lời độ bất tiện của \(Q\) đảo \(X_1,\ldots,X_Q\) mà Rin đang cân nhắc chuyển đến.

Dữ liệu vào

Dòng đầu chứa \(N,M,Q\). \(M\) dòng tiếp theo, dòng \(j\) chứa \(A_j,B_j,C_j\). \(Q\) dòng cuối lần lượt chứa \(X_1,X_2,\ldots,X_Q\), mỗi giá trị trên một dòng.

Dữ liệu ra

In \(Q\) dòng; dòng \(k\) là độ bất tiện của đảo \(X_k\).

Ràng buộc

• \(2\le N\le300\,000\), \(1\le M\le600\,000\), \(1\le Q\le N\).
• \(1\le A_j<B_j\le N\) và \(1\le C_j\le10^9\).
• Đồ thị tạo bởi toàn bộ \(M\) kế hoạch liên thông; \(C_1,C_2,\ldots,C_M\) đôi một khác nhau.
• \(1\le X_k\le N\) và \(X_1,X_2,\ldots,X_Q\) đôi một khác nhau.
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(N,M\le2000\).
2. \(8\) điểm: \(N\le2000\).
3. \(9\) điểm: \(M=N-1\), \(A_j=j\), \(B_j=j+1\) với mọi \(1\le j\le M\), và \(Q=1\).
4. \(18\) điểm: \(M=N-1\), \(A_j=j\), \(B_j=j+1\) với mọi \(1\le j\le M\).
5. \(28\) điểm: \(Q=1\).
6. \(32\) điểm: không có ràng buộc thêm.

Ví dụ

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

7
3

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

12
8
7
10
13

10 20 1
1 2 808642746
1 3 990324141
1 4 69919024
1 5 794837863
3 6 84751636
1 7 491226767
3 8 314795065
1 9 347506932
1 10 709806198
2 3 103026123
9 10 270175384
4 8 133038160
4 10 592110162
2 10 708615085
6 10 262209760
5 10 75049025
7 9 367273075
6 9 264231132
3 10 909786421
2 7 135810916
10

43

Nguồn

JOI 2025/2026 Semifinal Stage, bài New Bridge. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.

Bạn có \(N\) viên gạch được đánh số từ \(1\) đến \(N\). Mặt trên và mặt dưới của mỗi viên có màu đen (B) hoặc trắng (W); ký tự thứ \(i\) của chuỗi \(S\) và \(T\) lần lượt cho biết màu mặt trên và mặt dưới ban đầu của viên \(i\).

Uzbekistan nổi tiếng với những công trình kiến trúc lịch sử được trang trí bằng gạch. Khi tham quan các thánh đường Hồi giáo và trường học Hồi giáo (madrasa) ở Uzbekistan, bạn bị cuốn hút bởi vẻ đẹp của những công trình này và mua một cỗ máy kỳ lạ liên quan đến gạch. Cỗ máy có hai khay ở bên trái và bên phải, mỗi khay đặt được một viên gạch. Khi đặt viên gạch \(a\) ở khay trái và viên gạch \(b\) ở khay phải, máy đổi hai viên này lấy một viên mới \(c\) theo các quy tắc sau:

• Mặt trên của \(c\) màu đen khi và chỉ khi màu mặt dưới của \(a\) bằng màu mặt trên của \(b\); nếu không thì màu trắng.
• Mặt dưới của \(c\) màu đen khi và chỉ khi màu mặt trên của \(a\) bằng màu mặt dưới của \(b\); nếu không thì màu trắng.

Trong \(Q\) ngày, ngày \(j\) thực hiện một trong hai hành động:

• Loại 1: đổi màu mặt trên và mặt dưới của viên \(X_j\) lần lượt thành \(Y_j\) và \(Z_j\).
• Loại 2: xếp các viên \(L_j,L_j+1,\ldots,R_j\) theo thứ tự từ trái sang phải. Có thể thực hiện từ \(0\) đến \(R_j-L_j\) lần thao tác sau: chọn hai viên kề nhau, bỏ chúng khỏi hàng, đưa viên bên trái vào khay trái và viên bên phải vào khay phải, rồi đặt viên mới do máy tạo ra vào đúng vị trí của cặp vừa bỏ. Hãy xác định có thể thực hiện các thao tác để trong hàng có đúng \(M_j\) viên có mặt trên màu trắng (các viên khác trong hàng vẫn có thể có mặt trên màu đen) hay không.

Mỗi truy vấn loại 2 chỉ là một thí nghiệm độc lập và không làm thay đổi các viên gạch; chỉ cập nhật loại 1 mới thay đổi trạng thái dùng cho các ngày sau.

Dữ liệu vào

Dữ liệu vào có dạng:

N
S
T
Q
(Query 1)
...
(Query Q)

Gọi \(P_j\) là số nguyên đầu tiên của truy vấn thứ \(j\). Mỗi truy vấn là một trong hai dạng:

• 1 X_j Y_j Z_j: cập nhật viên \(X_j\).
• 2 L_j R_j M_j: thực hiện thí nghiệm trên đoạn \([L_j,R_j]\).

Dữ liệu ra

Với mỗi truy vấn loại 2, theo thứ tự xuất hiện, in Yes nếu có thể tạo đúng số viên mặt trên trắng được yêu cầu, ngược lại in No.

Ràng buộc

• \(1\le N\le300\,000\).
• \(S,T\) là các chuỗi độ dài \(N\) chỉ gồm B và W.
• \(1\le Q\le300\,000\).
• \(P_j\in\{1,2\}\) với mọi \(1\le j\le Q\).
• Nếu \(P_j=1\): \(1\le X_j\le N\) và \(Y_j,Z_j\in\{\texttt{B},\texttt{W}\}\).
• Nếu \(P_j=2\): \(1\le L_j\le R_j\le N\) và \(0\le M_j\le R_j-L_j+1\).
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(6\) điểm: \(N\le6\).
2. \(10\) điểm: \(N\le100\) và mọi truy vấn có loại \(2\).
3. \(9\) điểm: \(N\le500\) và mọi truy vấn có loại \(2\).
4. \(8\) điểm: \(N\le1700\) và mọi truy vấn có loại \(2\).
5. \(23\) điểm: \(N,Q\le10000\).
6. \(14\) điểm: \(N,Q\le100000\).
7. \(30\) điểm: không có ràng buộc thêm.

Ví dụ

4
WBWB
BWBB
5
2 3 4 1
2 1 2 0
1 3 B B
2 3 4 2
2 2 4 1

Yes
Yes
No
Yes

6
BWBWWB
WBWBBB
8
2 1 3 2
2 2 6 0
2 1 5 3
2 3 3 0
2 3 4 1
2 5 6 2
2 2 6 4
2 1 4 2

No
Yes
Yes
Yes
Yes
No
No
Yes

Nguồn

JOI 2025/2026 Semifinal Stage, bài Strange Machine. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.