JOI 2026 - Chung kết - Cuộc thi 4

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 JOI 2026 - Baker 100 (p) 2.0s 1G
2 JOI 2026 - Festivals in JOI Kingdom 3 100 (p) 5.0s 1G
3 JOI 2026 - Voltage 2 100 (p) 2.0s 1G

1. JOI 2026 - Baker

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

Tiệm bánh JOI nổi tiếng với những chiếc bánh croissant thơm ngon. Tiệm có \(N\) thợ, đánh số từ \(1\) đến \(N\). Thợ \(i\) mất đúng \(i\) phút để làm một chiếc croissant và không thể làm đồng thời nhiều chiếc.

Có \(M\) khách hàng, đánh số từ \(1\) đến \(M\), dự định đến tiệm hôm nay; khách \(j\) đặt một chiếc tại thời điểm \(T_j\). Thời điểm \(t\) nghĩa là \(t\) phút kể từ bây giờ. Nếu không nhận được bánh trong vòng \(L\) phút kể từ khi đặt, khách sẽ bỏ cuộc và rời tiệm. Vì vậy, đơn của khách \(j\) chỉ được phục vụ nếu chiếc bánh hoàn thành không muộn hơn \(T_j+L\), kể cả đúng thời điểm \(T_j+L\).

Người quản lý K dự định cho đúng một thợ làm việc hôm nay và đang cân nhắc chọn ai, bắt đầu lúc nào. Vì thợ chỉ tập trung làm bánh sau khi bắt đầu ca, họ bỏ qua mọi đơn đến sau thời điểm bắt đầu, nhưng không bỏ qua đơn đến đúng thời điểm đó. Cụ thể, thợ bắt đầu lúc \(t\) không thể phục vụ đơn của khách \(j\) có \(T_j>t\).

Có \(Q\) phương án độc lập. Phương án \(q\) cho thợ \(A_q\) bắt đầu làm việc tại thời điểm \(B_q\). Với mỗi phương án, hãy tìm số khách tối đa có thể được phục vụ. Thợ có thể chọn thứ tự làm các đơn được xem xét; thời gian chờ để bắt đầu làm chiếc đầu tiên sau khi đến nơi và để chuyển sang chiếc tiếp theo sau khi hoàn thành một chiếc được xem là \(0\).

Dữ liệu vào

Dòng đầu gồm \(N,M,L,Q\). Dòng thứ hai gồm \(T_1,T_2,\ldots,T_M\) theo thứ tự không giảm. \(Q\) dòng tiếp theo, dòng \(q\) gồm \(A_q,B_q\).

Dữ liệu ra

In \(Q\) dòng. Dòng \(q\) là số khách tối đa có thể phục vụ trong phương án \(q\).

Ràng buộc

  • \(1\le N\le4\times10^{12}\), \(1\le M\le2\,000\,000\), \(1\le L\le2\times10^{12}\), \(1\le Q\le400\,000\).
  • \(0\le T_j\le2\times10^{12}\) và \(T_j\le T_{j+1}\).
  • \(1\le A_q\le N\), \(0\le B_q\le4\times10^{12}\).
  • Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

  1. \(8\) điểm: \(M\le10\), \(Q\le100\,000\).
  2. \(12\) điểm: \(M\le500\), \(Q\le100\,000\).
  3. \(30\) điểm: \(T_M\le B_q<T_1+L\) với mọi \(q\).
  4. \(10\) điểm: \(T_M\le B_q\) với mọi \(q\).
  5. \(22\) điểm: \(M\le500\,000\), \(Q\le100\,000\).
  6. \(18\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
4 4 6 4
0 2 3 8
2 3
1 6
3 3
4 7
Output 
3
2
2
0
Giải thích

Với phương án \(1\), thợ \(2\) bắt đầu tại thời điểm \(3\) và có thể phục vụ khách \(1,2,3\) như sau:

  • Làm bánh cho khách \(1\) từ thời điểm \(3\) đến \(5\), không muộn hơn hạn \(T_1+L=0+6=6\).
  • Làm bánh cho khách \(2\) từ thời điểm \(5\) đến \(7\), không muộn hơn hạn \(T_2+L=2+6=8\).
  • Làm bánh cho khách \(3\) từ thời điểm \(7\) đến \(9\), không muộn hơn hạn \(T_3+L=3+6=9\).

Khách \(4\) đặt sau khi thợ bắt đầu nên bị bỏ qua. Số khách tối đa là \(3\), vì vậy dòng đầu là \(3\).

Với phương án \(2\), thợ \(1\) bắt đầu tại thời điểm \(6\) và có thể phục vụ khách \(2,3\) như sau:

  • Làm bánh cho khách \(3\) từ thời điểm \(6\) đến \(7\), không muộn hơn hạn \(T_3+L=3+6=9\).
  • Làm bánh cho khách \(2\) từ thời điểm \(7\) đến \(8\), không muộn hơn hạn \(T_2+L=2+6=8\).

Khách \(4\) đặt sau khi thợ bắt đầu nên bị bỏ qua. Đơn của khách \(1\) phải hoàn thành trước hoặc đúng thời điểm \(6\), nên không thể phục vụ. Số khách tối đa là \(2\), vì vậy dòng thứ hai là \(2\).

Với phương án \(3\), thợ \(3\) bắt đầu tại thời điểm \(3\) có thể phục vụ khách \(1,3\) hoặc khách \(2,3\), nhưng không thể phục vụ cả ba khách \(1,2,3\). Khách \(4\) đặt sau khi thợ bắt đầu nên không thể được phục vụ. Số khách tối đa là \(2\), vì vậy dòng thứ ba là \(2\).

Với phương án \(4\), thợ \(4\) bắt đầu tại thời điểm \(7\) không thể phục vụ khách nào, nên dòng thứ tư là \(0\).

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

Ví dụ 2

Input 
20 5 12 4
1 2 4 8 10
1 12
3 10
3 11
15 10
Output 
5
4
3
0
Giải thích

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 3

Input 
100000 6 272273 10
5 9 209 8128 17202 50102
164 9
11 24
835 9267
2 256
2 314156
18475 142
1826 18978
44757 1
4 1646
218 44
Output 
2
2
4
3
1
2
5
0
3
2
Giải thích

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

Nguồn

JOI 2025/2026 - Chung kết, Cuộc thi 4, bài Baker.

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.

2. JOI 2026 - Festivals in JOI Kingdom 3

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

Vương quốc JOI có \(N\) thành phố đánh số từ \(1\) đến \(N\) và \(N-1\) quốc lộ đánh số từ \(1\) đến \(N-1\). Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua các quốc lộ. Thành phố \(i\) có độ nổi tiếng là một số nguyên không âm, ban đầu bằng \(C_i\); quốc lộ \(j\) nối hai thành phố \(A_j,B_j\) theo cả hai chiều và có thời gian đi lại là một số nguyên dương, ban đầu bằng \(D_j\).

Mỗi thành phố có một vạc lửa. Theo truyền thống lễ hội, việc thắp vạc là tín hiệu để các đoàn diễu hành xuất phát từ thành phố đó. Hai thành phố được gọi là kề nhau nếu có một quốc lộ nối trực tiếp chúng. Ngay khi vạc của một thành phố được thắp tại thời điểm \(t\), với mỗi thành phố kề, một đoàn diễu hành riêng xuất phát đến đó và đến nơi tại thời điểm \(t+d\), trong đó \(d\) là thời gian đi lại của quốc lộ nối hai thành phố.

Một số thành phố thắp lửa ngay khi lễ hội bắt đầu, còn các thành phố khác chờ lễ hội đủ sôi động. Gọi thời điểm bắt đầu lễ hội là \(0\). Thành phố có độ nổi tiếng \(0\) thắp lửa ở thời điểm \(0\). Nếu độ nổi tiếng là \(c\ge1\), nó thắp lửa tại thời điểm đầu tiên mà số đoàn diễu hành đã đến từ các thành phố kề đạt ít nhất \(c\); nếu điều này không xảy ra thì vạc không bao giờ được thắp.

Ông K sẽ ở lại vương quốc JOI. Trong thời gian đó có \(Q\) sự kiện, đánh số từ \(1\) đến \(Q\) theo thứ tự từ sớm đến muộn. Sự kiện thứ \(k\) thuộc một trong ba loại:

  • Loại \(1\): độ nổi tiếng của thành phố \(V_k\) đổi thành \(X_k\).
  • Loại \(2\): thời gian đi lại của quốc lộ \(E_k\) đổi thành \(X_k\).
  • Loại \(3\): ông K đến thành phố \(V_k\). Giả sử lễ hội bắt đầu ngay lúc này, hãy xác định vạc của thành phố đó có được thắp hay không và nếu có thì được thắp tại thời điểm nào.

Mỗi truy vấn loại 3 mô phỏng một lễ hội mới bắt đầu tại thời điểm \(0\) bằng các giá trị hiện hành; truy vấn không làm thay đổi độ nổi tiếng, thời gian đi lại hay trạng thái dùng cho sự kiện sau.

Dữ liệu vào

Dòng đầu là \(N\). \(N-1\) dòng tiếp theo gồm \(A_j,B_j,D_j\). \(N\) dòng sau đó là \(C_1,\ldots,C_N\). Dòng tiếp theo là \(Q\).

Tiếp theo là \(Q\) dòng, mỗi dòng mô tả một sự kiện. Số nguyên đầu tiên \(P_k\) là loại sự kiện, thuộc \(\{1,2,3\}\). Mỗi sự kiện có dạng 1 V X (đổi \(C_V\) thành \(X\)), 2 E X (đổi \(D_E\) thành \(X\)), hoặc 3 V (truy vấn thành phố \(V\)).

Dữ liệu ra

Với mỗi sự kiện loại 3, theo thứ tự thời gian của các sự kiện, in thời điểm vạc được thắp; in -1 nếu không bao giờ được thắp.

Ràng buộc

  • \(2\le N\le150\,000\).
  • \(1\le Q\le150\,000\).
  • \(0\le C_i\le N\), \(1\le A_j<B_j\le N\), \(1\le D_j\le10^6\).
  • Cây liên thông; mọi giá trị đầu vào là số nguyên.
  • Với sự kiện loại 1: \(1\le V\le N\) và \(0\le X\le N\).
  • Với sự kiện loại 2: \(1\le E<N\) và \(1\le X\le10^6\).
  • Với sự kiện loại 3: \(1\le V\le N\).

Phân nhóm

  1. \(6\) điểm: \(N,Q\le2\,000\).
  2. \(7\) điểm: \(A_j=1\), \(B_j=j+1\) với mọi \(1\le j\le N-1\); mọi truy vấn loại 3 hỏi thành phố \(1\).
  3. \(14\) điểm: \(N-1\) chia hết cho \(3\). Đặt \(m=(N-1)/3\). Với mọi \(j=1,\ldots,N-1\):
\[ A_j=((j-1)\bmod m)+1,\qquad B_j=j+1. \]
Mọi truy vấn loại `3` đều có $V_k=1$.
  1. \(25\) điểm: không có sự kiện loại 1; mọi truy vấn loại 3 hỏi thành phố \(1\).
  2. \(12\) điểm: mọi truy vấn loại 3 hỏi thành phố \(1\).
  3. \(22\) điểm: không có sự kiện loại 1.
  4. \(14\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
7
1 2 30
2 3 30
1 4 70
2 5 20
1 6 10
2 7 50
2
3
0
0
0
1
0
8
3 1
1 6 0
3 1
2 6 10
3 1
1 2 7
1 6 7
3 1
Output 
80
70
60
-1
Giải thích

Trong lễ hội xét ở sự kiện \(1\):

  • Thời điểm \(0\), các thành phố \(3,4,5,7\) thắp lửa.
  • Thời điểm \(50\), thành phố \(2\) thắp lửa; khi đó các đoàn từ thành phố \(3,5,7\) đã đến thành phố \(2\).
  • Thời điểm \(80\), thành phố \(1\) thắp lửa; khi đó các đoàn từ thành phố \(2,4\) đã đến thành phố \(1\).
  • Thời điểm \(90\), thành phố \(6\) thắp lửa; khi đó đoàn từ thành phố \(1\) đã đến thành phố \(6\).

Thành phố \(1\) thắp lửa tại thời điểm \(80\), nên in \(80\).

Trong lễ hội xét ở sự kiện \(3\):

  • Thời điểm \(0\), các thành phố \(3,4,5,6,7\) thắp lửa.
  • Thời điểm \(50\), thành phố \(2\) thắp lửa; khi đó các đoàn từ thành phố \(3,5,7\) đã đến thành phố \(2\).
  • Thời điểm \(70\), thành phố \(1\) thắp lửa; khi đó các đoàn từ thành phố \(4,6\) đã đến thành phố \(1\).

Thành phố \(1\) thắp lửa tại thời điểm \(70\), nên in \(70\).

Trong lễ hội xét ở sự kiện \(5\):

  • Thời điểm \(0\), các thành phố \(3,4,5,6,7\) thắp lửa.
  • Thời điểm \(30\), thành phố \(2\) thắp lửa; khi đó các đoàn từ thành phố \(3,5,7\) đã đến thành phố \(2\).
  • Thời điểm \(60\), thành phố \(1\) thắp lửa; khi đó các đoàn từ thành phố \(2,6\) đã đến thành phố \(1\).

Thành phố \(1\) thắp lửa tại thời điểm \(60\), nên in \(60\).

Trong lễ hội xét ở sự kiện \(8\), các thành phố \(3,4,5,7\) thắp lửa tại thời điểm \(0\). Các thành phố \(1,2,6\) không bao giờ thắp lửa. Vì thành phố \(1\) không thắp lửa, in \(-1\).

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

Ví dụ 2

Input 
6
1 2 10
1 3 30
1 4 50
1 5 30
1 6 10
2
0
0
0
0
1
10
3 1
2 3 20
3 1
1 6 0
3 1
1 1 4
3 1
1 2 6
1 3 6
3 1
Output 
30
20
10
30
-1
Giải thích

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

Nguồn

JOI 2025/2026 - Chung kết, Cuộc thi 4, bài Festivals in JOI Kingdom 3.

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.

3. JOI 2026 - Voltage 2

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

Bạn có biết công ty Just Odd Inventions không? Công ty này chỉ chuyên tạo ra những phát minh kỳ lạ; chúng ta gọi tắt là JOI.

Trong một phòng thí nghiệm của JOI có một mạch điện phức tạp gồm \(N\) nút và \(M\) điện trở mảnh. Các nút được đánh số từ \(0\) đến \(N-1\), các điện trở được đánh số từ \(0\) đến \(M-1\). Mỗi nút có thể được đặt ở một trong hai trạng thái: điện áp cao hoặc điện áp thấp. Điện trở \(i\) nối từ nút \(A_i\) đến một nút khác \(B_i\). Dòng điện chạy qua điện trở này khi và chỉ khi \(A_i\) ở điện áp cao và \(B_i\) ở điện áp thấp; dòng điện chỉ có thể chạy theo chiều đó. Giữa hai nút bất kỳ có nhiều nhất một điện trở, không phân biệt chiều nối.

Bạn là nhà nghiên cứu tại JOI và sẽ tiến hành thí nghiệm với mạch này. Các điện trở quá mảnh nên bạn không thể nhìn thấy chúng nối những cặp nút nào. Tuy nhiên, có một manh mối: khi đặt điện áp cho các nút, nhiệt độ của mạch tăng theo số điện trở có dòng điện chạy qua. Bạn quyết định chạm vào mạch để so sánh nhiệt độ. Bạn không thể đo nhiệt độ chính xác, nhưng có thể thử hai cách đặt điện áp và so sánh nhiệt độ của mạch giữa hai cách đó. Mỗi lần so sánh chỉ cho biết một trong ba kết quả:

  • Số điện trở có dòng điện chạy qua trong cách đặt thứ nhất lớn hơn.
  • Số điện trở có dòng điện chạy qua trong hai cách đặt bằng nhau.
  • Số điện trở có dòng điện chạy qua trong cách đặt thứ hai lớn hơn.

Mục tiêu là dùng các phép so sánh này để xác định toàn bộ điện trở, tức là tất cả các cặp có thứ tự \((a,b)\) sao cho có điện trở từ nút \(a\) đến nút \(b\). Bạn được biết trước \(N\) và \(M\), cũng như các điều kiện mỗi điện trở nối hai nút khác nhau và giữa mỗi cặp nút có nhiều nhất một điện trở, không phân biệt chiều. Chỉ dựa vào những điều kiện đó và thông tin từ các phép so sánh nhiệt độ, hãy xác định toàn bộ các cặp \((a,b)\).

Tùy cấu trúc mạch, có thể không xác định duy nhất các điện trở dù thực hiện bao nhiêu phép so sánh đi nữa. Khi đó, bạn phải báo rằng không thể xác định duy nhất mạch. Đây là tính không thể xác định vốn có của mạch, không phải chỉ do hết lượt truy vấn.

Để tránh làm hỏng điện trở, bạn được so sánh nhiệt độ tối đa \(30000\) lần. Nhân tiện, phát minh mà JOI đang chế tạo bằng mạch điện này là bí mật ngay cả trong công ty; chỉ chủ tịch biết nó là gì.

Cho số nút và số điện trở, hãy viết chương trình xác định các điện trở hoặc báo rằng không thể xác định duy nhất, bằng không quá \(30000\) phép so sánh nhiệt độ.

Giao diện

Đây là bài tương tác qua hàm. Nộp mã C++ có #include "voltage.h" và cài đặt hàm sau, không viết main:

C++
bool solve(int N, int M);
  • Hàm được gọi đúng một lần trong mỗi lần chạy, với \(N\) là số nút và \(M\) là số điện trở. Chương trình thí sinh chạy trong một tiến trình.
  • Trả về false nếu không thể xác định duy nhất các điện trở dù thực hiện bao nhiêu phép so sánh nhiệt độ đi nữa; ngược lại, trả về true.
  • Trả về true khi không thể xác định duy nhất bị chấm Wrong Answer [1].
  • Trả về false khi có thể xác định mạch từ các phép so sánh nhiệt độ bị chấm Wrong Answer [2].

Chương trình được gọi hai hàm sau do hệ thống cung cấp:

C++
int query(std::vector<int> x, std::vector<int> y);
void answer(int a, int b);

Hàm query thực hiện hai cách đặt điện áp và so sánh nhiệt độ:

  • x mô tả cách đặt thứ nhất, y mô tả cách đặt thứ hai. Mỗi mảng phải có độ dài \(N\) và chỉ gồm \(0\) hoặc \(1\).
  • Với \(0\le k<N\), x[k] = 1 đặt nút \(k\) ở điện áp cao trong cách thứ nhất, còn x[k] = 0 đặt nút đó ở điện áp thấp. y[k] có ý nghĩa tương tự cho cách thứ hai.
  • Giá trị trả về là -1 nếu cách thứ nhất có nhiều điện trở dẫn điện hơn, 0 nếu bằng nhau, hoặc 1 nếu cách thứ hai có nhiều điện trở dẫn điện hơn.
  • Nếu độ dài x khác \(N\): Wrong Answer [3].
  • Nếu x chứa giá trị khác \(0,1\): Wrong Answer [4].
  • Nếu độ dài y khác \(N\): Wrong Answer [5].
  • Nếu y chứa giá trị khác \(0,1\): Wrong Answer [6].
  • Không được gọi hàm quá \(30000\) lần; vi phạm bị chấm Wrong Answer [7].

Hàm answer báo một điện trở đã xác định, có chiều từ nút \(a\) đến nút \(b\):

  • Phải có \(0\le a,b<N\); nếu không, bị chấm Wrong Answer [8].
  • Không được gọi hàm nhiều lần với cùng cặp \((a,b)\); vi phạm bị chấm Wrong Answer [9].
  • Không được gọi hàm quá \(M\) lần; vi phạm bị chấm Wrong Answer [10].
  • Khi solve trả về true, phải đã gọi answer đúng \(M\) lần; nếu không, bị chấm Wrong Answer [11].
  • Khi solve trả về true, mỗi cặp \((a,b)\) đã báo phải thực sự tương ứng với một điện trở từ \(a\) đến \(b\); nếu không, bị chấm Wrong Answer [12].

Bạn có thể cài đặt các hàm phụ hoặc khai báo biến toàn cục dùng nội bộ. Chương trình nộp không được dùng đầu vào/đầu ra chuẩn hay tương tác với tệp khác. Có thể dùng luồng lỗi chuẩn để gỡ lỗi.

Hệ thống chấm không thích nghi: đáp án được cố định từ trước khi bắt đầu tương tác.

Chương trình chấm mẫu

Bộ tệp công khai gồm voltage.h, mã khung voltage.cpp, chương trình chấm mẫu grader.cpp và compile.sh. Chương trình chấm mẫu khác với hệ thống chấm chính thức. Để thử chương trình, đặt grader.cpp, voltage.cpp và voltage.h trong cùng thư mục rồi biên dịch bằng lệnh:

Bash
g++ -std=gnu++20 -O2 -o grader grader.cpp voltage.cpp

Hoặc chạy sh compile.sh. Tệp thực thi được tạo có tên grader.

Chương trình chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Đầu vào có dạng:

N M
A_0 B_0
A_1 B_1
...
A_{M-1} B_{M-1}

Nếu phát hiện một lỗi từ Wrong Answer [3] đến Wrong Answer [12], chương trình chấm mẫu in loại lỗi, chẳng hạn Wrong Answer [5], và kết thúc ngay. Nếu đồng thời vi phạm nhiều điều kiện, chỉ một lỗi được hiển thị.

Nếu không phát hiện các lỗi đó, chương trình chấm mẫu in số lần gọi query và giá trị trả về của solve, chẳng hạn Accepted: 30 true.

Chương trình chấm mẫu không kiểm tra Wrong Answer [1] và Wrong Answer [2], tức là không kiểm tra giá trị true/false mà solve trả về có đúng với khả năng xác định duy nhất mạch hay không. Vì vậy, thông báo Accepted từ chương trình chấm mẫu không đảm bảo chương trình đúng.

Dữ liệu vào

Bài nộp nhận dữ liệu qua các đối số của những hàm được mô tả ở trên, không đọc đầu vào chuẩn.

Dữ liệu ra

Bài nộp không ghi đầu ra chuẩn. Kết quả được trả qua giá trị trả về của các hàm được mô tả ở trên.

Ràng buộc

  • \(2\le N\le500\).
  • \(1\le M\le1000\).
  • \(0\le A_i,B_i\le N-1\) với mọi \(0\le i\le M-1\).
  • \(A_i\ne B_i\) với mọi \(0\le i\le M-1\).
  • Với mọi \(0\le i<j\le M-1\), \((A_i,B_i)\ne(A_j,B_j)\) và \((A_i,B_i)\ne(B_j,A_j)\).
  • \(N,M,A_i,B_i\) đều là số nguyên.

Phân nhóm

  1. \(10\) điểm: \(N\le100\), \(M=N-1\), \(B_i=A_{i+1}\) với mọi \(0\le i\le N-3\); \(N\) giá trị \(A_0,A_1,\ldots,A_{N-2},B_{N-2}\) đôi một khác nhau.
  2. \(12\) điểm: \(M=N-1\), \(B_i=A_{i+1}\) với mọi \(0\le i\le N-3\); \(N\) giá trị \(A_0,A_1,\ldots,A_{N-2},B_{N-2}\) đôi một khác nhau.
  3. \(27\) điểm: \(N\le100\) và \(A_i\ne A_j\) với mọi \(0\le i<j\le M-1\).
  4. \(18\) điểm: \(A_i\ne A_j\) với mọi \(0\le i<j\le M-1\).
  5. \(17\) điểm: \(N\le100\).
  6. \(16\) điểm: Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Dưới đây là đầu vào cho chương trình chấm mẫu và một chuỗi lời gọi hàm tương ứng.

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

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

Tương tác

Lời gọi solve Giá trị trả về Lời gọi từ chương trình Giá trị trả về
solve(5, 6)
query([0,0,1,1,1], [1,1,1,0,0]) -1
query([1,0,1,0,0], [0,1,0,1,0]) 0
query([0,1,1,1,0], [1,1,0,1,1]) 1
answer(0, 2)
answer(0, 3)
answer(2, 1)
answer(3, 4)
answer(3, 2)
answer(4, 1)
true

Giải thích

Trong lần gọi query đầu tiên:

  • Cách đặt thứ nhất: nút \(0,1\) ở điện áp thấp; nút \(2,3,4\) ở điện áp cao. Dòng điện chạy qua các điện trở \(1,5\).
  • Cách đặt thứ hai: nút \(3,4\) ở điện áp thấp; nút \(0,1,2\) ở điện áp cao. Dòng điện chạy qua điện trở \(2\).

Số điện trở dẫn điện trong cách thứ nhất lớn hơn nên hàm trả về \(-1\).

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

Trong các tệp ví dụ được đề gốc nhắc đến, sample-01-in.txt tương ứng với ví dụ trên; sample-02-in.txt thỏa mãn ràng buộc của tất cả các nhóm và sample-03-in.txt thỏa mãn các ràng buộc của nhóm \(3,4,5,6\).

Nguồn

JOI 2025/2026 - Chung kết, Cuộc thi 4, bài Voltage 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.