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

Bitaro mua một xiên dango dài để ăn nhẹ. Các viên dango được xếp thành một cột từ trên xuống dưới và chia thành các khối liên tiếp. Có \(N\) số nguyên dương \(A_1,A_2,\ldots,A_N\); khối \(i\) gồm \(A_i\) viên dango. Khối lẻ có vị ngọt, khối chẵn có vị cay. Đặt \(s_0=0\) và \(s_i=A_1+\cdots+A_i\), nên khối \(i\) chiếm các vị trí từ \(s_{i-1}+1\) đến \(s_i\) tính từ trên xuống.

Bitaro có \(Q\) kế hoạch. Kế hoạch \(j\) cho bởi \(L_j,R_j\), và Bitaro chỉ ăn các viên từ vị trí \(s_{L_j-1}+1\) đến \(s_{R_j}\).

Trong một kế hoạch, Bitaro ăn từ trên xuống dưới trong vùng đã chọn, mỗi viên đúng một lần, chia tùy ý thành các miếng liên tiếp không rỗng. Một miếng làm Bitaro vui nếu số viên ngọt trừ số viên cay trong miếng đó không nhỏ hơn \(K\). Với mỗi kế hoạch, hãy tìm số miếng làm Bitaro vui lớn nhất có thể.

Dữ liệu vào

Dòng đầu gồm \(N,Q,K\). Dòng thứ hai gồm \(A_1,A_2,\ldots,A_N\). \(Q\) dòng tiếp theo, dòng \(j\) gồm \(L_j,R_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng \(j\) là số lần Bitaro có thể vui nhiều nhất trong kế hoạch \(j\).

Ràng buộc

• \(1\le N,Q\le500000\).
• \(1\le K\le10^{14}\).
• \(1\le A_i\le10^9\).
• \(1\le L_j\le R_j\le N\).

Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(6\) điểm: \(Q\le10\).
2. \(5\) điểm: \(K\le2\).
3. \(18\) điểm: \(K\le10\).
4. \(27\) điểm: \(A_1+\cdots+A_N\le500000\).
5. \(17\) điểm: \(N,Q\le200000\).
6. \(27\) điểm: không có ràng buộc thêm.

Ví dụ

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

7
2

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

2
0

9 4 50
24 26 89 45 84 72 15 31 66
1 9
2 8
4 6
5 6

3
2
1
1

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 1, bài Legendary Dango Eater, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.

Vườn JOI là lưới hình chữ nhật có \(H\) hàng và \(W\) cột. Ô ở hàng thứ \(i\) tính từ trên xuống và cột thứ \(j\) tính từ trái sang phải được gọi là \((i,j)\). Ban đầu, lượng nước của mọi ô bằng \(0\) và chỉ tăng khi có mưa.

Trong \(N\) ngày liên tiếp, vào buổi tối ngày \(k-1\) (\(1 \le k \le N\)), mọi ô \((i,j)\) thỏa \(U_k\le i\le D_k\) và \(L_k\le j\le R_k\) tăng lượng nước thêm \(C_k\). Khi lượng nước của một ô đạt ít nhất \(X\), ô đó trở thành bùn lầy và gây nguy hiểm.

Vì vậy, vào mỗi buổi sáng, JOI-kun, người quản lý vườn JOI, được lập nhiều nhất một khu vực cấm hình chữ nhật bao phủ tất cả các ô nguy hiểm. Nếu không có ô nguy hiểm, JOI-kun có thể không lập khu vực cấm nào; khi đó số ô bị cấm là \(0\). Với từng \(k\), hãy tìm diện tích nhỏ nhất có thể của khu vực cấm vào buổi sáng ngày \(k\).

Cụ thể, nếu lập khu vực cấm, JOI-kun chọn bốn số nguyên \(u,d,l,r\) với \(1 \le u \le d \le H\) và \(1 \le l \le r \le W\); khu vực cấm gồm các ô \((i,j)\) thỏa \(u \le i \le d\), \(l \le j \le r\). Diện tích ở đây là số ô thuộc khu vực cấm.

Dữ liệu vào

Dòng đầu gồm \(H,W,N,X\). \(N\) dòng tiếp theo, dòng \(k\) gồm \(U_k,D_k,L_k,R_k,C_k\).

Dữ liệu ra

In \(N\) dòng. Dòng \(k\) là diện tích nhỏ nhất của khu vực cấm vào buổi sáng ngày \(k\).

Ràng buộc

• \(1\le H,W\le10^9\).
• \(1\le N\le200000\).
• \(1\le X\le2\times10^{14}\).
• \(1\le U_k\le D_k\le H\).
• \(1\le L_k\le R_k\le W\).
• \(1\le C_k\le10^9\).

Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(3\) điểm: \(X=1\).
2. \(24\) điểm: \(W=1\).
3. \(15\) điểm: \(N\le300\).
4. \(30\) điểm: \(N\le5000\).
5. \(28\) điểm: không có ràng buộc thêm.

Ví dụ

3 3 5 10
3 3 1 1 5
1 3 1 2 7
1 3 3 3 4
1 1 1 2 12
3 3 3 3 6

0
1
1
6
9

9 1 5 1
3 3 1 1 4
5 8 1 1 1
3 5 1 1 3
8 8 1 1 4
8 9 1 1 5

1
6
6
6
7

4596 9794 15 141929907
600 3070 2222 8763 472026497
47 2644 3276 6033 930213777
638 945 304 1100 992702990
370 2211 2178 2977 783902937
277 2601 1559 8989 842013671
566 3272 3124 8456 254633541
91 4241 2655 8035 303526265
1342 3662 3909 7175 685435928
1176 4012 2827 8429 614977118
255 2461 1482 5835 794902067
982 2314 941 3952 342731056
1603 2215 6730 7105 332440107
2301 4568 6898 9561 591652619
124 2097 3520 8882 168525684
1845 3599 5592 7145 555656973

16165282
19783008
25583040
25583040
26266464
28021036
36437770
36437770
36437770
36437770
36437770
36437770
41864676
41864676
41864676

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 1, bài Garden 3, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.

Chủ tịch K giữ bí mật một ma trận đối xứng \(A\) kích thước \(N\times N\), với các chỉ số từ \(0\) đến \(N-1\) và \(A_{i,i}=0\). Xem \(A_{i,j}\) là trọng số cạnh \(i,j\) của đồ thị vô hướng đầy đủ. Gọi \(X\) là tổng trọng số cây khung nhỏ nhất.

Giá trị \(X\) cũng có thể được xác định bằng quá trình sau. Ban đầu đặt \(x=0\) và tạo đồ thị \(G\) gồm \(N\) đỉnh \(0,1,\ldots,N-1\), chưa có cạnh. Lặp lại \(N-1\) lần:

1. Gọi các đỉnh đang đi đến được từ đỉnh \(0\) là đỉnh gần, các đỉnh còn lại là đỉnh xa. Chọn đỉnh gần \(i\) và đỉnh xa \(j\) sao cho \(A_{i,j}N^2+iN+j\) nhỏ nhất. Luôn có ít nhất một đỉnh mỗi loại và cặp \((i,j)\) được xác định duy nhất.
2. Thêm cạnh nối \(i,j\) vào \(G\).
3. Cộng \(A_{i,j}\) vào \(x\).

Sau \(N-1\) lần lặp, \(X\) là giá trị của \(x\).

Có \(R=\lfloor5120/N\rfloor\) vòng, mỗi vòng có \(N\) người chơi. Trong vòng \(r\), các người chơi \((r,0),(r,1),\ldots,(r,N-1)\) lần lượt tương tác theo thứ tự chỉ số tăng dần. Người chơi \((r,i)\) chỉ biết hàng \(A_i\) của ma trận và \(N\) thông điệp 64-bit nhận từ vòng trước; ở vòng \(0\), cả \(N\) thông điệp đều bằng \(0\). Người chơi hoặc trả lời \(X\) để kết thúc game ngay lập tức, hoặc gửi một thông điệp 64-bit đến từng người chơi của vòng sau. Nếu hết vòng \(R-1\) mà không ai trả lời đúng thì game thất bại. Hãy cài đặt chiến lược để game thành công trong ít vòng nhất có thể.

Đây là bài Communication. Bài nộp C++ phải #include "multi.h" và hiện thực hàm strategy, không viết main. Khi chấm trên LQDOJ, chương trình được chạy trong hai tiến trình cô lập. Hàm chiến lược chỉ được dựa vào các đối số, không được dựa vào trạng thái dùng chung giữa các tiến trình. Không được giao tiếp bằng stdin, stdout hoặc tệp khác; được ghi thông tin gỡ lỗi vào stderr.

Bạn phải hiện thực hàm sau:

std::vector<unsigned long long> strategy(
    int N, int r, int i,
    std::vector<unsigned long long> A,
    std::vector<unsigned long long> B
);

• Nếu đã xác định \(X\), trả về vector độ dài \(1\) chứa \(X\).
• Nếu chưa trả lời, trả về vector độ dài \(N\); phần tử \(j\) là thông điệp gửi đến người chơi \((r+1,j)\). Quy tắc này vẫn áp dụng ở vòng \(R-1\), dù vòng sau không có người chơi.
• Với cùng tham số, hàm phải luôn trả về cùng kết quả.

Trong lời gọi strategy, A[j] là \(A_{i,j}\) và B[j] là thông điệp từ người chơi \((r-1,j)\) gửi cho người chơi \((r,i)\). Mỗi vector có đúng \(N\) phần tử. Ở vòng \(0\), mọi phần tử của B bằng \(0\). Người chơi có thể thống nhất chiến lược trước khi trò chơi bắt đầu, nhưng không được giao tiếp ngoài các thông điệp đã mô tả. Nếu có người trả lời sai \(X\), trò chơi kết thúc thất bại ngay.

Các điều kiện bị chấm sai là:

• Wrong Answer [1]: vector trả về có độ dài khác \(1\) và \(N\).
• Wrong Answer [2]: giá trị \(X\) được trả lời không đúng.
• Wrong Answer [3]: không ai trả lời trước khi vòng \(R-1\) kết thúc.
• Wrong Answer [4]: hàm trả về các giá trị khác nhau khi được gọi với cùng bộ đối số.

Các đối số được bảo đảm có thể xuất hiện khi chơi với một ma trận \(A\) và hàm strategy đã nộp. Được phép khai báo hàm phụ và biến toàn cục, nhưng giá trị trả về không được phụ thuộc vào lần gọi trước hoặc tính ngẫu nhiên lúc chạy.

Biên dịch và chạy thử

Để chạy thử, đặt multi.cpp, multi.h và trình mẫu grader.cpp trong cùng thư mục rồi biên dịch bằng:

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

Có thể dùng sh compile.sh thay cho lệnh trên. Nếu biên dịch thành công, tệp thực thi grader được tạo ra. Trình mẫu chạy trong một tiến trình và khác trình chấm thật. Chỉ trình mẫu đọc stdin và ghi stdout; các hàm của bài nộp vẫn phải tuân thủ quy tắc không giao tiếp bằng các luồng này.

Đầu vào của trình mẫu bắt đầu bằng số ván \(T\). Với mỗi ván, nhập dữ liệu theo dạng:

N
A_0,1 A_0,2 ... A_0,N-1
A_1,2 A_1,3 ... A_1,N-1
...
A_N-2,N-1

Trình mẫu in \(T\) dòng. Nếu ván thứ \(t\) thành công, dòng thứ \(t\) có dạng Accepted: 22, trong đó số là số vòng đã dùng. Nếu vi phạm điều kiện chấm sai, dòng đó có dạng Wrong Answer [4], với mã lỗi tương ứng. Nếu nhiều điều kiện cùng bị vi phạm, chỉ một điều kiện được báo.

Dữ liệu vào

Bài nộp nhận dữ liệu qua các đối số của strategy, không đọc stdin. Định dạng dữ liệu để chạy thử với trình mẫu được mô tả ở trên.

Dữ liệu ra

Submission không có standard output. Kết quả được trả qua vector của strategy.

Ràng buộc

• \(2\le N\le256\).
• \(0\le A_{i,j}<2^{48}\).
• \(A_{i,i}=0\) và \(A_{i,j}=A_{j,i}\).
• Mỗi thông điệp là số nguyên trong \([0,2^{64})\).
• Trong một lần chạy, grader có thể chơi nhiều game và gọi strategy nhiều nhất \(10\,240\) lần.
• Các lời gọi strategy không nhất thiết xuất hiện theo thứ tự vòng tăng dần; kết quả chỉ được phụ thuộc vào đúng năm đối số của lời gọi.

Phân nhóm

Trong mỗi phân nhóm, nếu có testcase không hợp lệ, quá thời gian hoặc trả lời sai thì được \(0\) điểm. Nếu mọi testcase hợp lệ, đặt \(S\) là số vòng lớn nhất trong các game của phân nhóm. Nếu trả lời ở vòng \(r\) thì số vòng đã dùng là \(r+1\). Lỗi thực thi hoặc vượt giới hạn bộ nhớ trong bất kỳ test nào cũng làm điểm phân nhóm bằng \(0\).

Với phân nhóm 3, luôn nhận đủ điểm khi mọi game hợp lệ. Nếu \(S>6\), trang thi chính thức có thể hiển thị Output is partially correct, nhưng điều này không làm thay đổi điểm phân nhóm \(3\). Với các phân nhóm khác: \(S\le6\) nhận \(100\%\) điểm; \(7\le S\le9\) nhận \((100-20(S-6))\%\); \(10\le S\le19\) nhận \((40-S)\%\); \(S\ge20\) nhận \(20\%\).

1. \(5\) điểm: \(N\le64\), mọi \(A_{i,j}\le1\).
2. \(10\) điểm: mọi \(A_{i,j}\le1\).
3. \(15\) điểm: \(N\le64\).
4. \(40\) điểm: mọi \(A_{i,j}<2^{20}\).
5. \(15\) điểm: mọi \(A_{i,j}<2^{40}\).
6. \(15\) điểm: không có ràng buộc thêm.

Ví dụ giao tiếp

Sample grader nhận một game có \(N=3\) qua dữ liệu vào sau:

1
3
1 2
3

Sau dòng \(T=1\) và dòng \(N=3\), các dòng còn lại là tam giác trên của ma trận.

grader ghi nhận chuỗi lời gọi và giá trị trả về minh họa sau:

Trong vòng \(0\), người chơi \((0,0)\) gửi lần lượt các giá trị \(0,1,2\) đến \((1,0),(1,1),(1,2)\); người chơi \((0,1)\) gửi \(3,4,5\) đến ba người chơi đó theo cùng thứ tự; người chơi \((0,2)\) gửi \(6,7,8\) theo cùng thứ tự. Chưa ai trả lời nên trò chơi chuyển sang vòng \(1\). Người chơi \((1,0)\) nhận lần lượt \(0,3,6\) từ ba người chơi vòng trước và trả lời đúng \(X=3\). Trò chơi kết thúc thành công ngay lúc đó, sau \(2\) vòng.

Ví dụ này thỏa mãn các bài toán con \(3,4,5,6\). Khi chạy thử, sample-01-in.txt tương ứng với ví dụ này; sample-02-in.txt thỏa mọi bài toán con; sample-03-in.txt thỏa các bài toán con \(3,4,5,6\); sample-04-in.txt thỏa các bài toán con \(4,5,6\).

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 1, bài Multi Communication 2, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.