JOIG 2026 - Chung kết - Cuộc thi 2

Ở ngoại ô Rome có một tuyến đường sắt dài, xem như trục số. Có \(N\) ga được đánh số từ \(1\) đến \(N\) theo thứ tự tọa độ tăng dần; ga \(i\) ở tọa độ \(A_i\), và không có hai ga cùng tọa độ. Tàu chỉ chạy theo chiều tọa độ tăng và dừng ở mọi ga.

Mức giá của một chặng phụ thuộc vào khoảng cách \(d ≥ 1\). Cho dãy \(1=B_1<B_2<...<B_K\). Nếu \(j_{max}\) là chỉ số lớn nhất thỏa \(B_{j_{max}} ≤ d\), giá của chặng là \(j_{max}\). Ga lên và ga xuống của một chặng phải khác nhau.

Bitaro có \(Q\) hành trình. Ở hành trình \(q\), cậu đi từ ga \(l_q\) đến ga \(r_q\) với \(l_q<r_q\). Cậu có thể xuống ở bất kỳ ga trung gian nào, thanh toán chặng vừa đi, rồi lên lại tại chính ga đó; số lần xuống không bị giới hạn. Hãy tìm tổng giá nhỏ nhất cho từng hành trình.

Dữ liệu vào

Dòng đầu là \(N\). Dòng thứ hai là \(A_1,A_2,...,A_N\). Dòng tiếp theo là \(K\), sau đó là dãy \(B_1,B_2,...,B_K\). Dòng tiếp theo là \(Q\), rồi \(Q\) dòng chứa \(l_q,r_q\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(q\) là tổng giá nhỏ nhất để đi từ ga \(l_q\) đến ga \(r_q\).

Ràng buộc

• \(2 ≤ N ≤ 150000\).
• \(1 ≤ A_1<A_2<...<A_N ≤ 10^9\).
• \(1 ≤ K ≤ 20\).
• \(1=B_1<B_2<...<B_K ≤ 10^9\).
• \(1 ≤ Q ≤ 150000\).
• \(1 ≤ l_q<r_q ≤ N\).
• Mọi giá trị đầu vào là số nguyên.

Phân nhóm

1. \(8\) điểm: \(K ≤ 2\).
2. \(11\) điểm: \(N ≤ 500\).
3. \(29\) điểm: \(Q=1\).
4. \(20\) điểm: \(K ≤ 5\).
5. \(32\) điểm: không có ràng buộc thêm.

Ví dụ

8
1 3 4 5 8 9 12 14
8
1 2 5 6 7 9 10 11
3
1 5
3 5
1 7

4
2
6

10
3 6 16 19 32 40 41 53 59 78
2
1 15
1
3 10

2

10
11 13 39 42 53 54 66 69 77 83
15
1 5 13 31 40 41 52 57 59 66 70 79 97 103 115
5
1 6
2 9
1 8
2 7
3 9

6
7
6
6
4

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 2, bài Railway Trip 4.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

Trong vườn thú có \(N\) con hải ly, đánh số từ \(0\) đến \(N-1\). Hải ly \(i\) thích táo có khối lượng trong đoạn \([L_i,R_i]\), nhưng bạn không biết các giá trị \(L_i,R_i\).

Bạn cần chọn đúng \(K\) con để đưa vào khu trưng bày. Hai con sẽ đánh nhau nếu hai khoảng sở thích của chúng giao nhau, tức tồn tại \(x\) thỏa \(L_i ≤ x ≤ R_i\) và \(L_j ≤ x ≤ R_j\). Đề bảo đảm tồn tại một cách chọn \(K\) con không đánh nhau.

Đây là bài tương tác. Bạn có thể hỏi không quá \(1000\) lần để tìm một tập hợp hợp lệ. Bộ chấm không thích nghi: mọi câu trả lời đã được cố định từ đầu.

Dữ liệu vào

Ban đầu, chương trình nhận một dòng chứa \(N\) và \(K\). Sau đó, chương trình nhận các câu trả lời của bộ chấm theo giao thức tương tác bên dưới.

Dữ liệu ra

Chương trình gửi các truy vấn và câu trả lời cuối cùng qua standard output theo giao thức tương tác bên dưới. Phải flush sau mỗi lần xuất.

Giao thức tương tác

Ban đầu, chương trình nhận một dòng gồm $N$ và $K$.

Để hỏi về tập các chỉ số phân biệt \(t_0,t_1,...,t_{m-1}\), in và flush:

? m t0 t1 ... t(m-1)

trong đó \(0 ≤ m ≤ N\) và mọi \(t_i\) thuộc \([0,N-1]\). Sau đó đọc số nguyên \(r\): số hải ly lớn nhất có thể chọn từ tập vừa hỏi mà không đánh nhau. Giá trị \(r\) có thể lớn hơn \(K\). Nếu nhận -1, phải kết thúc ngay.

Để trả lời, in và flush đúng một lần:

! s0 s1 ... s(K-1)

Các \(s_i\) phải là \(K\) chỉ số phân biệt trong \([0,N-1]\), và các khoảng sở thích tương ứng không được giao nhau. Mọi định dạng khác đều bị từ chối.

Ràng buộc

• \(1 ≤ N ≤ 1000\).
• \(1 ≤ K ≤ min(10,N)\).
• \(1 ≤ L_i ≤ R_i ≤ 10000\).
• Có ít nhất một cách chọn \(K\) hải ly không đánh nhau.
• Không được dùng quá \(1000\) truy vấn.

Phân nhóm

1. \(6\) điểm: \(N ≤ 8\).
2. \(7\) điểm: \(N ≤ 12\).
3. \(14\) điểm: \(N ≤ 20\).
4. \(21\) điểm: \(N ≤ 50\).
5. \(16\) điểm: \(N ≤ 90\).
6. \(36\) điểm: không có ràng buộc thêm. Nếu mọi test của phân nhóm này đúng, đặt \(T\) là số truy vấn lớn nhất: nhận \(13\) điểm khi \(100<T ≤ 1000\), và \(36\) điểm khi \(T ≤ 100\).

Ví dụ

4 2
2 6
3 6
4 10
8 11

Judge: 4 2
User:  ? 2 0 2
Judge: 1
User:  ? 1 1
Judge: 1
User:  ? 3 3 2 1
Judge: 2
User:  ! 1 3

L_i,R_i trong ví dụ chỉ là input của testing tool; chương trình nộp bài chỉ nhận $N$ và $K$ từ judge.

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 2, bài Zoo.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

Cánh đồng rộng lớn của làng JOI được biểu diễn bằng mặt phẳng \(xy\) vô hạn, trong đó chiều dương của trục \(x\) là hướng Đông, chiều dương của trục \(y\) là hướng Bắc. Thị trưởng muốn đặt các con bù nhìn để bảo vệ cánh đồng khỏi kẻ địch. Mỗi bù nhìn bảo vệ một vùng tùy theo vị trí và hướng quay của nó. Có \(N\) kế hoạch đặt bù nhìn, được đánh số từ \(1\) đến \(N\). Thực hiện kế hoạch thứ \(i\) tốn chi phí \(C_i\) và đặt một bù nhìn theo ba số nguyên \(T_i, X_i, Y_i\) như sau:

• Nếu \(T_i = 1\), bù nhìn ở \((X_i, Y_i)\) quay về Tây và bảo vệ mọi điểm có \(x \le X_i\).
• Nếu \(T_i = 2\), bù nhìn ở \((X_i, Y_i)\) quay về Đông và bảo vệ mọi điểm có \(x \ge X_i\).
• Nếu \(T_i = 3\), bù nhìn ở \((X_i, Y_i)\) quay về Nam và bảo vệ mọi điểm có \(y \le Y_i\).
• Nếu \(T_i = 4\), bù nhìn ở \((X_i, Y_i)\) quay về Bắc và bảo vệ mọi điểm có \(y \ge Y_i\).

Hãy chọn một số kế hoạch sao cho mọi điểm trên mặt phẳng được bảo vệ bởi ít nhất \(K\) bù nhìn, và tổng chi phí là nhỏ nhất. Nếu không thể, in ra -1.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N\), \(K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(T_i\), \(X_i\), \(Y_i\), \(C_i\).

Dữ liệu ra

In ra chi phí nhỏ nhất cần thiết, hoặc -1 nếu không thể bảo vệ mọi điểm bởi ít nhất \(K\) bù nhìn.

Ràng buộc

• \(1 \le K \le N \le 200000\).
• \(T_i \in \{1,2,3,4\}\).
• \(0 \le X_i, Y_i \le 10^9\).
• Các cặp tọa độ \((X_i, Y_i)\) đôi một khác nhau.
• \(0 \le C_i \le 10^9\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (4 điểm): \(K = 1\).
• Nhóm 2 (6 điểm): \(K \le 2\).
• Nhóm 3 (11 điểm): \(N \le 500\), \(K \le 300\).
• Nhóm 4 (27 điểm): \(N \le 6000\).
• Nhóm 5 (19 điểm): \(N \le 75000\).
• Nhóm 6 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

7 1
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

99

7 3
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

-1

19 5
2 36 42 64
2 7 89 74
1 0 15 82
1 10 63 55
2 58 28 19
2 45 91 3
2 2 34 97
1 7 55 82
1 17 12 17
2 59 76 82
1 7 4 68
2 51 98 47
1 51 21 38
2 19 0 72
1 73 73 11
2 62 19 74
1 45 7 94
1 79 32 21
1 85 50 21

315

8 3
4 4 21 80
2 59 65 69
4 63 36 3
2 29 13 23
1 37 45 95
2 79 14 89
3 91 54 76
1 85 46 62

328

Nguồn

JOI 2025/2026 Final Stage, Competition 3, problem Scarecrows 2. Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

Đất nước IOI, nơi JOI-kun sinh sống, có \(N\) thị trấn được đánh số từ \(1\) đến \(N\), cùng \(N-1\) con đường được đánh số từ \(1\) đến \(N-1\). Đường thứ \(j\) nối hai thị trấn \(U_j\) và \(V_j\) theo cả hai chiều. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.

Một cuộc hành trình sưu tập dấu sẽ được tổ chức. Mỗi thị trấn có một trạm đóng dấu; trạm ở thị trấn \(i\) được lắp đặt tại thời điểm \(T_i\).

JOI-kun quyết định tham gia. Cậu xuất phát từ một thị trấn ở thời điểm \(0\), với thể lực ban đầu \(D\). Khi ở thị trấn \(i\) tại thời điểm \(t\), cậu thực hiện các hành động sau:

1. Nếu trạm đóng dấu ở thị trấn hiện tại đã được lắp đặt, tức là \(T_i \le t\), cậu đóng dấu.
2. Cậu chọn kết thúc hành trình hoặc di chuyển sang thị trấn khác. Chỉ được chọn di chuyển nếu còn ít nhất \(1\) thể lực và có một thị trấn kề chưa từng ghé thăm.
3. Nếu chọn di chuyển, cậu chọn một thị trấn \(j\) chưa từng ghé thăm có đường nối trực tiếp với \(i\). Thể lực giảm \(1\) và cậu đến \(j\) tại thời điểm \(t+1\).
4. Nếu chọn kết thúc, hành trình thành công khi cậu đã đóng dấu ít nhất một lần; cậu nhận một món quà tại thị trấn kết thúc. Nếu chưa đóng dấu lần nào, hành trình thất bại.

Thời gian thực hiện mọi hành động ngoài việc đi giữa hai thị trấn là không đáng kể. JOI-kun không được đứng chờ tại một thị trấn.

Bạn là người tổ chức và phải chuẩn bị quà tại những thị trấn mà JOI-kun có thể kết thúc thành công. Do số quà có hạn, bạn muốn chuẩn bị quà ở ít thị trấn nhất có thể. Tuy nhiên, bạn chưa biết JOI-kun sẽ xuất phát từ đâu. Vì vậy, với mỗi thị trấn xuất phát \(s\) (\(1\le s\le N\)), hãy đếm số thị trấn \(g\) (\(1\le g\le N\)) sao cho tồn tại một hành trình thành công bắt đầu từ \(s\) và kết thúc tại \(g\).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N\), \(D\).
• Dòng thứ hai chứa \(N\) số nguyên \(T_1, T_2, \ldots, T_N\).
• \(N-1\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(U_j\), \(V_j\) mô tả một con đường.

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(s\) chứa số thị trấn cần chuẩn bị quà nếu JOI-kun xuất phát từ thị trấn \(s\).

Ràng buộc

• \(2 \le N \le 400000\).
• \(0 \le D \le N-1\).
• \(0 \le T_i \le N\).
• \(1 \le U_j < V_j \le N\).
• Đồ thị các thị trấn là liên thông.
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (3 điểm): \(D \le 1\).
• Nhóm 2 (7 điểm): \(N \le 3000\) và \((U_j, V_j) = (j, j + 1)\) với mọi \(1 \le j \le N - 1\).
• Nhóm 3 (10 điểm): \(N \le 3000\).
• Nhóm 4 (11 điểm): \((U_j, V_j) = (j, j + 1)\) với mọi \(1 \le j \le N - 1\).
• Nhóm 5 (41 điểm): \(D = N - 1\), \(N \le 150000\).
• Nhóm 6 (28 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

2
3
4
2
2

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

2
1
2
0
1

7 6
2 3 0 4 1 3 4
1 2
2 3
2 4
1 5
1 6
6 7

2
2
7
5
1
2
5

Nguồn

JOI 2025/2026 Final Stage, Competition 3, problem Collecting Stamps 5. Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.