JOI 2025 - Tuyển chọn mùa xuân - Ngày 4

JOI-kun đang chơi với một bộ mạch điện tử gồm \(N\) linh kiện AND, \(N\) linh kiện OR và một bảng mạch. Bảng mạch có \(2N+1\) công tắc và \(N\) khe cắm linh kiện; mỗi khe có thể được sử dụng bằng cách đặt vào đó một linh kiện AND hoặc OR. Bảng mạch cho ra giá trị \(0\) hoặc \(1\), tùy theo các linh kiện được đặt và trạng thái của các công tắc.

Quy tắc của bảng mạch

• Các công tắc được đánh số từ \(0\) đến \(2N\). Mỗi công tắc ở trạng thái ON (bật) hoặc OFF (tắt) và cho ra giá trị \(0\) hoặc \(1\) theo quy tắc dưới đây.
• Các khe cắm linh kiện được đánh số từ \(0\) đến \(N-1\). Mỗi khe cũng cho ra giá trị \(0\) hoặc \(1\).
• Giá trị của các công tắc và khe cắm được xác định theo thứ tự số hiệu giảm dần. Nếu một công tắc và một khe cắm có cùng số hiệu, giá trị của khe cắm được xác định trước.
• Với \(j=2N,2N-1,\ldots,N\), công tắc \(j\) cho ra \(0\) nếu ở trạng thái OFF và \(1\) nếu ở trạng thái ON.
• Với \(j=N-1,N-2,\ldots,0\), gọi \(x\) là giá trị của khe cắm \(j\). Công tắc \(j\) cho ra \(x\) nếu ở trạng thái OFF và \(1-x\) nếu ở trạng thái ON.
• Với \(i=N-1,N-2,\ldots,0\), khe cắm \(i\) nối với hai công tắc \(U_i,V_i\), trong đó \(i<U_i<V_i\le 2N\). Gọi \(x,y\) lần lượt là giá trị của hai công tắc này. Nếu khe cắm chứa linh kiện AND, nó cho ra \(\min(x,y)\); nếu chứa linh kiện OR, nó cho ra \(\max(x,y)\).
• Với mỗi \(j=1,2,\ldots,2N\), có đúng một chỉ số \(i\) (\(0\le i\le N-1\)) thỏa mãn \(U_i=j\) hoặc \(V_i=j\).
• Giá trị của bảng mạch bằng giá trị của công tắc \(0\).

Ví dụ, khi \(N=3\), \(U_0=1\), \(V_0=2\), \(U_1=3\), \(V_1=4\), \(U_2=5\), \(V_2=6\), các khe cắm \(0,1\) chứa linh kiện AND và khe cắm \(2\) chứa linh kiện OR, bảng mạch được biểu diễn như hình sau.

JOI-kun định đặt linh kiện AND vào tất cả các khe cắm, nhưng phát hiện có nhiều nhất \(R\) linh kiện OR bị đặt lẫn vào. Vì linh kiện AND và OR có hình dạng giống nhau, cần dùng bảng mạch để phân biệt chúng. Bạn được hỏi JOI-kun nhiều nhất \(1000\) truy vấn theo dạng sau:

• Chỉ định trạng thái của cả \(2N+1\) công tắc. JOI-kun sẽ đặt các công tắc theo yêu cầu và cho bạn biết giá trị của bảng mạch.

Cho cấu trúc kết nối và cận trên của số linh kiện OR, hãy xác định tất cả các khe cắm chứa linh kiện OR bằng nhiều nhất \(1000\) truy vấn.

Chi tiết cài đặt

Bạn cần nộp một tệp có tên circuit.cpp. Tệp này phải dùng chỉ thị #include để nạp circuit.h và cài đặt hàm sau:

std::string solve(int N, int R, std::vector<int> U, std::vector<int> V)

• Hàm được gọi đúng một lần trong mỗi bộ dữ liệu.
• N là số khe cắm linh kiện; R là cận trên của số linh kiện OR.
• U và V là hai mảng độ dài \(N\). Với \(0\le i\le N-1\), U[i] và V[i] là số hiệu \(U_i,V_i\) của hai công tắc nối với khe cắm \(i\).
• Hàm phải trả về xâu \(t\) độ dài \(N\) chỉ gồm & và |. Với mỗi \(i=0,1,\ldots,N-1\), t[i] phải là & nếu khe cắm \(i\) chứa linh kiện AND và là | nếu chứa linh kiện OR.
• Nếu độ dài xâu trả về khác \(N\), chương trình bị chấm Wrong Answer [1].
• Nếu xâu trả về chứa ký tự khác & và |, chương trình bị chấm Wrong Answer [2].
• Nếu loại linh kiện thực tế tại một khe cắm khác loại được biểu diễn trong xâu trả về, chương trình bị chấm Wrong Answer [3].

Chương trình của bạn có thể gọi hàm sau:

int query(std::string s)

• Hàm này dùng để hỏi JOI-kun một truy vấn.
• s phải là xâu độ dài \(2N+1\) chỉ gồm 0 và 1. Với mỗi \(j=0,1,\ldots,2N\), s[j] bằng 0 nghĩa là đặt công tắc \(j\) ở trạng thái OFF, còn s[j] bằng 1 nghĩa là đặt ở trạng thái ON.
• Nếu độ dài của s khác \(2N+1\), chương trình bị chấm Wrong Answer [4].
• Nếu s chứa ký tự khác 0 và 1, chương trình bị chấm Wrong Answer [5].
• Không được gọi hàm quá \(1000\) lần. Nếu vượt quá giới hạn này, chương trình bị chấm Wrong Answer [6].
• Hàm trả về giá trị của bảng mạch sau khi đặt các công tắc theo s.

Lưu ý

Bạn được cài đặt thêm các hàm phụ và khai báo biến toàn cục để dùng nội bộ. Chương trình không được tương tác với đầu vào chuẩn, đầu ra chuẩn hoặc bất kỳ tệp nào khác. Tuy nhiên, có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

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

Gói tệp được cung cấp trên trang cuộc thi chứa chương trình chấm mẫu và một tệp mã nguồn mẫu cho phần cần cài đặt. Chương trình chấm mẫu là tệp grader.cpp. Để chạy thử, đặt grader.cpp, circuit.cpp và circuit.h trong cùng một thư mục rồi dùng lệnh:

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

Bạn cũng có thể chạy tệp compile.sh có trong gói:

./compile.sh

Nếu biên dịch thành công, tệp thực thi grader sẽ được tạo. Chương trình chấm thực tế khác chương trình chấm mẫu. 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.

Dữ liệu vào

Gọi \(T\) là xâu độ dài \(N\) mà hàm solve cần trả về. Chương trình chấm mẫu đọc dữ liệu theo dạng:

N R
U_0 V_0
U_1 V_1
...
U_{N-1} V_{N-1}
T

Dữ liệu ra

• Nếu chương trình trả lời đúng, chương trình chấm mẫu in số lần gọi query, chẳng hạn Accepted: 22.
• Nếu chương trình bị chấm sai, chương trình chấm mẫu in loại lỗi, chẳng hạn Wrong Answer [4].

Chương trình chấm mẫu kết thúc ngay khi gặp một điều kiện sai. Nếu có nhiều điều kiện sai, chỉ một loại lỗi được hiển thị.

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

Ràng buộc

• \(1\le N\le 8000\).
• \(1\le R\le\min(N,120)\).
• \(i<U_i<V_i\le 2N\) (\(0\le i\le N-1\)).
• Với mỗi \(j=1,2,\ldots,2N\), có đúng một chỉ số \(i\) (\(0\le i\le N-1\)) thỏa mãn \(U_i=j\) hoặc \(V_i=j\).

Chấm điểm

1. \(1\) điểm: \(N=1\).
2. \(4\) điểm: \(N\le 1000\), \(R=1\).
3. \(5\) điểm: \(N\le 1000\).
4. \(17\) điểm: \(U_i=i+1\), \(V_i=N+1+i\) với mọi \(0\le i\le N-1\); \(R\le 70\).
5. \(8\) điểm: \(U_i=i+1\), \(V_i=N+1+i\) với mọi \(0\le i\le N-1\).
6. \(23\) điểm: \(U_i=2i+1\), \(V_i=2i+2\) với mọi \(0\le i\le N-1\); \(R\le 70\).
7. \(8\) điểm: \(U_i=2i+1\), \(V_i=2i+2\) với mọi \(0\le i\le N-1\).
8. \(27\) điểm: \(R\le 70\).
9. \(7\) điểm: Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Dưới đây là dữ liệu vào của chương trình chấm mẫu và các 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:

1 1
1 2
|

Tương tác

Chương trình chấm gọi solve(1, 1, [1], [2]).

Cuối cùng, solve trả về xâu |.

Giải thích

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

• Công tắc \(1\) ở trạng thái ON và công tắc \(2\) ở trạng thái OFF, nên chúng lần lượt cho ra \(1\) và \(0\).
• Khe cắm \(0\) chứa linh kiện OR, hai công tắc nối với nó cho ra \(1\) và \(0\), nên khe cắm cho ra \(\max(1,0)=1\).
• Công tắc \(0\) ở trạng thái OFF và khe cắm \(0\) cho ra \(1\), nên công tắc \(0\) cho ra \(1\).
• Vì vậy, bảng mạch cho ra \(1\).

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

Ví dụ 2

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

3 3
1 2
3 4
5 6
&&|

Tương tác

Chương trình chấm gọi solve(3, 3, [1, 3, 5], [2, 4, 6]).

Cuối cùng, solve trả về xâu &&|.

Giải thích

Hình trong đề bài biểu diễn bảng mạch của ví dụ này.

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

Trong các tệp được cung cấp trên trang cuộc thi, sample-01-in.txt tương ứng với ví dụ \(1\), sample-02-in.txt tương ứng với ví dụ \(2\). Ngoài ra, sample-03-in.txt thỏa mãn ràng buộc của các nhóm \(3,4,5,8,9\) và sample-04-in.txt thỏa mãn ràng buộc của các nhóm \(3,6,7,8,9\).

Nguồn

Bài Circuit 2, JOI 2024/2025, kỳ thi thứ tư của vòng tuyển chọn mùa xuân, do Ủy ban Olympic Tin học Nhật Bản (Japanese Committee for the International Olympiad in Informatics, JCIOI) công bố theo giấy phép CC BY-SA 4.0. Đây là bản dịch tiếng Việt; hình minh họa được giữ lại từ đề chính thức.

Vương quốc JOI có \(N\) thành phố được đánh số từ \(1\) đến \(N\), nối với nhau bởi \(N-1\) con đường một chiều. Với mỗi \(i=2,3,\ldots,N\), có một con đường đi từ thành phố \(i\) đến thành phố \(P_i\), trong đó \(1\le P_i<i\).

Mỗi thành phố có một mức độ nguy hiểm. Thủ đô, tức thành phố \(1\), có mức độ nguy hiểm bằng \(0\). Với thành phố \(i\) (\(2\le i\le N\)), mức độ nguy hiểm là số con đường trên đường đi từ thành phố \(i\) đến thành phố \(1\). Cấu trúc của vương quốc bảo đảm rằng đường đi này là duy nhất.

Hiện có \(K_i\) con hải ly sống tại thành phố \(i\) (\(1\le i\le N\)). Tổng thống Bitaro lập một kế hoạch di cư kéo dài \(Q\) ngày. Vào ngày thứ \(j\) (\(1\le j\le Q\)), một trong ba sự kiện sau xảy ra:

• Di dời: Tất cả hải ly đang sống tại các thành phố có mức độ nguy hiểm \(X_j\) di chuyển đến thành phố có mức độ nguy hiểm \(Y_j\) mà chúng có thể đến bằng cách đi qua một hoặc nhiều con đường từ thành phố hiện tại. Bảo đảm \(0\le Y_j<X_j\). Với mỗi con hải ly, thành phố đích được xác định duy nhất.
• Nhập cư: Số hải ly ở thành phố \(A_j\) tăng thêm \(L_j\) do có hải ly từ ngoài vương quốc đến sinh sống.
• Khảo sát: Khảo sát số hải ly hiện đang sống tại thành phố \(B_j\).

Là cấp dưới của Bitaro, bạn nhận ra có thể tính kết quả của mọi lần khảo sát chỉ từ thông tin kế hoạch mà không cần đến tận nơi. Cho cấu trúc vương quốc, số hải ly ban đầu tại mỗi thành phố và các sự kiện trong kế hoạch, hãy tính kết quả của từng lần khảo sát.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N-1\) số nguyên \(P_2,P_3,\ldots,P_N\).
• Dòng thứ ba chứa \(N\) số nguyên \(K_1,K_2,\ldots,K_N\).
• Dòng thứ tư chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) mô tả sự kiện của ngày \(j\). Số nguyên đầu tiên là \(T_j\):
  • 1 X_j Y_j: xảy ra sự kiện di dời từ mức độ nguy hiểm \(X_j\) đến mức độ nguy hiểm \(Y_j\) theo mô tả trên.
  • 2 A_j L_j: xảy ra sự kiện nhập cư, số hải ly ở thành phố \(A_j\) tăng thêm \(L_j\).
  • 3 B_j: xảy ra sự kiện khảo sát tại thành phố \(B_j\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

Với mỗi ngày \(j\) có \(T_j=3\), in số hải ly ở thành phố \(B_j\) tại thời điểm đó trên một dòng, theo thứ tự các sự kiện.

Ràng buộc

• \(2\le N\le 2000000\).
• \(1\le P_i<i\) (\(2\le i\le N\)).
• \(0\le K_i\le 100\) (\(1\le i\le N\)).
• \(1\le Q\le 2000000\).
• \(T_j\in\{1,2,3\}\) (\(1\le j\le Q\)).
• Nếu \(T_j=1\), thì \(0\le Y_j<X_j\le N-1\).
• Nếu \(T_j=2\), thì \(1\le A_j\le N\) và \(1\le L_j\le 100\).
• Nếu \(T_j=3\), thì \(1\le B_j\le N\).
• Có ít nhất một ngày \(j\) thỏa mãn \(T_j=3\).
• Tất cả giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

Gọi \(D\) là mức độ nguy hiểm lớn nhất trong các thành phố.

1. \(4\) điểm: \(D=1\).
2. \(8\) điểm: \(N\le 20\).
3. \(13\) điểm: \(D\le 20\).
4. \(15\) điểm: Không có sự kiện \(T_j=2\) và có nhiều nhất \(5\) sự kiện \(T_j=3\).
5. \(15\) điểm: Có nhiều nhất \(5\) sự kiện \(T_j=3\).
6. \(27\) điểm: Không có sự kiện \(T_j=2\).
7. \(18\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

1
8
0
3

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

3
13
0
4
0
17

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

6
18
19
6
0

Nguồn

Bài Migration Plan, JOI 2024/2025, kỳ thi thứ tư của vòng tuyển chọn mùa xuân, do Ủy ban Olympic Tin học Nhật Bản (Japanese Committee for the International Olympiad in Informatics, JCIOI) công bố theo giấy phép CC BY-SA 4.0. Đây là bản dịch tiếng Việt của đề chính thức.

Aoi có \(N\) lá bài được đánh số từ \(1\) đến \(N\). Trên mỗi lá bài ghi một số nguyên dương; số trên lá bài thứ \(i\) (\(1\le i\le N\)) là \(A_i\).

Aoi sẽ chơi \(Q\) ván bằng các lá bài và một chiếc bảng. Ván thứ \(j\) (\(1\le j\le Q\)) gồm các bước sau:

1. Viết số \(0\) lên bảng.
2. Xếp các lá bài \(L_j,L_j+1,\ldots,R_j\) trên bàn từ trái sang phải theo đúng thứ tự này.
3. Thực hiện \(R_j-L_j+1\) thao tác. Ở thao tác thứ \(k\) (\(1\le k\le R_j-L_j+1\)), gọi \(x\) là số hiện trên bảng và \(y\) là số trên lá bài thứ \(k\) từ trái sang. Xóa \(x\) rồi viết một trong hai số \(x+y\) hoặc \(x-y\) lên bảng. Nếu chọn \(x-y\), Aoi được ăn một miếng uiro, một loại bánh ngọt truyền thống của Nhật Bản. Tuy nhiên, không được viết số nhỏ hơn \(0\) lên bảng.

Cho thông tin về các lá bài và các ván chơi, hãy tìm số miếng uiro nhiều nhất Aoi có thể ăn trong mỗi ván.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\).
• Dòng thứ ba chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(L_j,R_j\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) (\(1\le j\le Q\)) chứa số miếng uiro nhiều nhất Aoi có thể ăn trong ván thứ \(j\).

Ràng buộc

• \(1\le N\le 200000\).
• \(1\le A_i\le 100\) (\(1\le i\le N\)).
• \(1\le Q\le 200000\).
• \(1\le L_j\le R_j\le N\) (\(1\le j\le Q\)).
• Tất cả giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(3\) điểm: \(N\le 20\), \(Q\le 20\).
2. \(5\) điểm: \(N\le 300\), \(Q\le 20\).
3. \(7\) điểm: \(N\le 5000\), \(Q\le 20\).
4. \(15\) điểm: \(Q\le 20\).
5. \(21\) điểm: \(A_i\le 2\) với mọi \(1\le i\le N\).
6. \(29\) điểm: \(A_i\le 20\) với mọi \(1\le i\le N\).
7. \(20\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
3 4 7 2 8
2
1 3
4 4

1
0

14
1 2 2 1 2 1 1 2 1 2 2 1 1 1
5
1 2
1 14
5 11
3 12
4 7

0
8
4
6
2

8
16 23 45 76 43 97 12 43
7
1 8
3 7
2 7
4 5
5 8
2 6
3 5

3
2
2
1
2
2
1

Nguồn

Bài Uiro, JOI 2024/2025, kỳ thi thứ tư của vòng tuyển chọn mùa xuân, do Ủy ban Olympic Tin học Nhật Bản (Japanese Committee for the International Olympiad in Informatics, JCIOI) công bố theo giấy phép CC BY-SA 4.0. Đây là bản dịch tiếng Việt của đề chính thức.