JOI 2022 - Tuyển chọn mùa xuân - Ngày 3 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2022 - Broken Device 2	100 (p)	2.0s	512M
2	JOI 2022 - Sprinkler	100 (p)	4.0s	1G
3	JOI 2022 - Ants and Sugar	100 (p)	4.0s	1G

1. JOI 2022 - Broken Device 2

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

Anna và Bruno là hai cao thủ cá cược. Họ chơi một trò chơi với D-taro, người chia bài.

Trong trò chơi này, Anna và Bruno ở hai phòng khác nhau. Họ chỉ có thể liên lạc qua một thiết bị bị hỏng. D-taro đưa cho Anna một số nguyên; mục tiêu của Anna và Bruno là dùng thiết bị để truyền số nguyên đó từ Anna sang Bruno.

Khi trò chơi bắt đầu, trước tiên Anna công bố một số nguyên \(m\) từ \(1\) đến \(2000\), kể cả hai đầu mút. Sau đó, họ chơi \(Q\) lượt. Lượt thứ \(i\) (\(1\le i\le Q\)) diễn ra như sau:

D-taro đưa cho Anna số nguyên \(A_i\).
Anna đưa hai dãy \(s_i,t_i\) vào thiết bị. Mỗi phần tử của hai dãy phải là \(0\) hoặc \(1\). Hai dãy phải có cùng độ dài, và độ dài đó phải nằm trong khoảng từ \(1\) đến \(m\), kể cả hai đầu mút.
Thiết bị tạo một dãy \(u_i\) bằng cách trộn xen kẽ hai dãy \(s_i,t_i\) như mô tả dưới đây, rồi gửi \(u_i\) cho Bruno.
Bruno gửi một số nguyên cho D-taro. Anna và Bruno thắng lượt này nếu số nguyên đó bằng \(A_i\).

Hãy viết các chương trình thực hiện chiến lược của Anna và Bruno để họ thắng cả \(Q\) lượt.

Phép trộn xen kẽ

Ta nói dãy \(Z\) được tạo bằng cách trộn xen kẽ (riffle shuffle) hai dãy \(X,Y\) nếu có thể chia các phần tử của \(Z\) thành hai nhóm sao cho:

Các phần tử thuộc nhóm thứ nhất, giữ nguyên thứ tự xuất hiện trong \(Z\), tạo thành dãy \(X\).
Các phần tử thuộc nhóm thứ hai, giữ nguyên thứ tự xuất hiện trong \(Z\), tạo thành dãy \(Y\).

Ví dụ, \(Z=[1,1,1,0,0,0]\) có thể được tạo từ \(X=[1,1,0]\) và \(Y=[1,0,0]\): các phần tử thứ \(1,2,4\) của \(Z\) tạo thành \(X\), còn các phần tử thứ \(3,5,6\) tạo thành \(Y\).

Ngược lại, với \(X=[1,1,0]\), \(Y=[1,0,0]\) và \(Z=[0,0,0,1,1,1]\), không thể tạo \(Z\) bằng cách trộn xen kẽ \(X,Y\).

Chi tiết cài đặt

Bạn cần nộp hai tệp.

Tệp thứ nhất là Anna.cpp, cài đặt chiến lược của Anna. Tệp này phải dùng chỉ thị #include để nạp Anna.h và cài đặt các hàm sau:

C++

int Declare();
std::pair<std::vector<int>, std::vector<int> > Anna(long long A);

Hàm Declare được gọi đúng một lần lúc bắt đầu. Giá trị trả về là số nguyên \(m\) do Anna công bố. Nếu \(m\) không nằm trong đoạn \([1,2000]\), chương trình bị chấm Wrong Answer [1].

Sau lời gọi Declare, hàm Anna được gọi \(Q\) lần. Lời gọi thứ \(i\) tương ứng với bước \(1\) và bước \(2\) của lượt thứ \(i\):

Tham số A là số nguyên \(A_i\) do D-taro đưa cho Anna.
Giá trị trả về là cặp hai dãy \(s_i,t_i\) được đưa vào thiết bị.
Nếu có phần tử nào của \(s_i\) hoặc \(t_i\) khác \(0\) và \(1\), chương trình bị chấm Wrong Answer [2].
Độ dài của mỗi dãy phải nằm trong đoạn \([1,m]\). Nếu không, chương trình bị chấm Wrong Answer [3].
Hai dãy phải có cùng độ dài. Nếu không, chương trình bị chấm Wrong Answer [4].

Tệp thứ hai là Bruno.cpp, cài đặt chiến lược của Bruno. Tệp này phải dùng chỉ thị #include để nạp Bruno.h và cài đặt hàm sau:

C++

long long Bruno(std::vector<int> u);

Sau mỗi lần Anna đưa các dãy vào thiết bị, hàm Bruno được gọi một lần, tổng cộng \(Q\) lần. Lời gọi thứ \(i\) tương ứng với bước \(3\) và bước \(4\) của lượt thứ \(i\):

Tham số u là dãy \(u_i\) do thiết bị gửi cho Bruno.
Giá trị trả về là số nguyên Bruno gửi cho D-taro.
Nếu giá trị trả về khác \(A_i\), chương trình bị chấm Wrong Answer [5].

Lưu ý quan trọng

Bạn có thể cài đặt thêm hàm dùng nội bộ hoặc khai báo biến toàn cục. Hai tệp nộp sẽ được liên kết với chương trình chấm thành một tệp thực thi. Mọi biến toàn cục và hàm nội bộ cần nằm trong namespace không tên để tránh xung đột với các tệp khác. Khi chấm thực tế, chương trình chạy dưới dạng hai tiến trình riêng cho Anna và Bruno; hai tiến trình không thể dùng chung biến toàn cục.
Chương trình của bạn không được dùng đầu vào chuẩn, đầu ra chuẩn, hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Bạn được phép 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 phát kèm trên trang cuộc thi chứa chương trình chấm mẫu và các tệp chương trình mẫu. Chương trình chấm mẫu nằm trong grader.cpp. Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng một thư mục và biên dịch bằng lệnh:

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Nếu biên dịch thành công, tệp thực thi grader đượ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ỉ chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Chương trình chấm mẫu đọc dữ liệu theo định dạng:

Q
A_1
A_2
...
A_Q

Dữ liệu ra

Chương trình chấm mẫu ghi các thông tin sau ra đầu ra chuẩn:

Nếu chương trình được chấm đúng, ghi giá trị \(m\) trả về bởi Declare, chẳng hạn Accepted: 2000.
Nếu chương trình bị chấm sai, ghi loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình vi phạm nhiều loại lỗi, chương trình chấm mẫu chỉ thông báo một trong số đó.

Trong chương trình chấm mẫu, phép trộn ở mỗi lượt được chọn bằng bộ sinh số giả ngẫu nhiên. Kết quả không đổi giữa các lần chạy có cùng hạt giống. Có thể thay hạt giống bằng cách truyền một số nguyên làm đối số thứ nhất, chẳng hạn:

./grader 2022

Ràng buộc

\(1\le Q\le1000\).
\(1\le A_i\le10^{18}\) với mọi \(1\le i\le Q\).

Phân nhóm

Nhóm 1 (5 điểm): \(A_i\le2000\) với mọi \(1\le i\le Q\).
Nhóm 2 (5 điểm): \(A_i\le4000000\) với mọi \(1\le i\le Q\).
Nhóm 3 (3 điểm): \(A_i\le10^7\) với mọi \(1\le i\le Q\).
Nhóm 4 (12 điểm): \(A_i\le10^8\) với mọi \(1\le i\le Q\).
Nhóm 5 (15 điểm): \(A_i\le10^{11}\) với mọi \(1\le i\le Q\).
Nhóm 6 (60 điểm): Không có ràng buộc bổ sung. Điểm của nhóm được tính theo bảng dưới đây.

Gọi \(m^*\) là giá trị lớn nhất trong các số nguyên \(m\) mà Anna công bố trên tất cả các bộ dữ liệu của nhóm 6. Lưu ý đây là giá trị công bố, không phải độ dài lớn nhất thực tế của các dãy được trả về.

Giá trị \(m^*\)	Điểm nhóm 6
\(201\le m^*\le2000\)	\(\left\lfloor40-25\log_{10}\left(\frac{m^*}{200}\right)\right\rfloor\)
\(161\le m^*\le200\)	\(40\)
\(156\le m^*\le160\)	\(44\)
\(151\le m^*\le155\)	\(48\)
\(146\le m^*\le150\)	\(52\)
\(141\le m^*\le145\)	\(56\)
\(m^*\le140\)	\(60\)

Ví dụ giao tiếp

Ví dụ 1

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

2
42
2000

Lời gọi hàm

Lời gọi	Giá trị trả về
`Declare()`	`4`
`Anna(42)`	`([0, 0, 1, 0], [1, 1, 0, 1])`
`Bruno([1, 0, 0, 1, 0, 1, 0, 1])`	`42`
`Anna(2000)`	`([0, 1], [0, 0])`
`Bruno([0, 0, 1, 0])`	`2000`

Giải thích

Ví dụ có \(Q=2\) lượt. Ở lượt 1, D-taro đưa \(A_1=42\) cho Anna; ở lượt 2, D-taro đưa \(A_2=2000\) cho Anna.

Ví dụ này thỏa mãn các nhóm \(1,2,3,4,5,6\) .

Nguồn

JOI 2021/2022, kỳ thi tuyển chọn mùa xuân, ngày thi thứ ba (22/03/2022). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.

2. JOI 2022 - Sprinkler

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

JOI-kun có nhiều năm kinh nghiệm trồng rau trong vườn nhà. Giờ đây, cậu dự định quản lý trang trại IOI.

Trang trại IOI gồm \(N\) mảnh đất, đánh số từ \(1\) đến \(N\), và \(N-1\) con đường, đánh số từ \(1\) đến \(N-1\). Con đường thứ \(i\) nối hai mảnh đất \(A_i,B_i\) theo cả hai chiều. Có thể đi từ bất kỳ mảnh đất nào đến bất kỳ mảnh đất nào khác qua các con đường. Mỗi mảnh đất có một vòi phun nước để tưới các mảnh đất xung quanh.

JOI-kun muốn trồng kê JOI trong trang trại. Đây là một loài cây kỳ lạ: chiều cao thay đổi ngay khi được tưới nước. Tuy nhiên, cây rất yếu; mỗi khi chiều cao lớn hơn hoặc bằng \(L\), phần ngọn dài \(L\) lập tức gãy ra. JOI-kun thu hoạch những phần bị gãy này.

Ban đầu, trên mảnh đất thứ \(j\) có một cây kê JOI cao \(H_j\). Trong \(Q\) ngày tiếp theo, mỗi ngày thứ \(k\) (\(1\le k\le Q\)), JOI-kun thực hiện một trong hai thao tác:

Loại 1: Dùng vòi phun tại mảnh đất \(X_k\) để tưới tất cả mảnh đất cách \(X_k\) không quá \(D_k\). Chiều cao của mỗi cây được tưới được nhân với \(W_k\). Do phần ngọn dài \(L\) liên tục gãy ra ngay khi chiều cao đạt hoặc vượt \(L\), một cây ban đầu cao \(h\) cuối cùng có chiều cao bằng phần dư của \(hW_k\) khi chia cho \(L\).
Loại 2: Đo chiều cao của cây kê trên mảnh đất \(X_k\).

Khoảng cách giữa hai mảnh đất là số con đường ít nhất cần đi qua để di chuyển từ mảnh đất này đến mảnh đất kia.

Để kiểm tra cây có phát triển đúng kế hoạch không, JOI-kun muốn tính trước chiều cao đo được trong từng thao tác loại 2. Hãy viết chương trình tính những chiều cao đó từ thông tin trang trại và kế hoạch chăm sóc.

Dữ liệu vào

Dữ liệu được cho theo định dạng sau. Mọi giá trị đều là số nguyên.

N L
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}
H_1
H_2
...
H_N
Q
(Truy vấn 1)
(Truy vấn 2)
...
(Truy vấn Q)

Truy vấn thứ \(k\) bắt đầu bằng số nguyên \(T_k\) và có một trong hai dạng:

1 X_k D_k W_k: tưới tất cả mảnh đất cách \(X_k\) không quá \(D_k\), nhân chiều cao mỗi cây được tưới với \(W_k\), rồi áp dụng quy tắc gãy ngọn nêu trên.
2 X_k: đo chiều cao cây trên mảnh đất \(X_k\).

Dữ liệu ra

Với mỗi truy vấn loại 2, theo thứ tự xuất hiện, in chiều cao cây trên mảnh đất được hỏi. Mỗi kết quả nằm trên một dòng.

Ràng buộc

\(2\le N\le200000\).
\(2\le L\le10^9\).
\(1\le A_i<B_i\le N\) với mọi \(1\le i\le N-1\).
Có thể đi từ bất kỳ mảnh đất nào đến bất kỳ mảnh đất nào khác qua các con đường.
\(0\le H_j\le L-1\) với mọi \(1\le j\le N\).
\(1\le Q\le400000\).
\(T_k\in\{1,2\}\) với mọi \(1\le k\le Q\).
Nếu \(T_k=1\): \(1\le X_k\le N\), \(0\le D_k\le40\), \(0\le W_k\le L-1\).
Nếu \(T_k=2\): \(1\le X_k\le N\).

Phân nhóm

Nhóm 1 (3 điểm): \(N\le1000\) và \(Q\le1000\).
Nhóm 2 (9 điểm): \(D_k\le1\) với mọi truy vấn có \(T_k=1\).
Nhóm 3 (29 điểm): \(D_k\le2\) với mọi truy vấn có \(T_k=1\).
Nhóm 4 (12 điểm): \(W_k=0\) với mọi truy vấn có \(T_k=1\).
Nhóm 5 (30 điểm): \(W_k=2\) với mọi truy vấn có \(T_k=1\).
Nhóm 6 (17 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Ban đầu, cả bốn cây đều cao \(1\).

Ngày 1, tưới từ mảnh đất \(2\) trong bán kính \(1\) làm chiều cao ở các mảnh đất \(1,2,3\) được nhân với \(2\). Chiều cao ở các mảnh đất \(1,2,3,4\) trở thành \(2,2,2,1\).

Ngày 2, tưới từ mảnh đất \(1\) trong bán kính \(0\) chỉ làm chiều cao ở mảnh đất \(1\) được nhân với \(2\). Các chiều cao trở thành \(4,2,2,1\).

Ngày 7, tưới từ mảnh đất \(4\) trong bán kính \(10\) làm cả bốn chiều cao được nhân với \(2\), thành \(8,4,4,2\). Cây ở mảnh đất \(1\) có chiều cao vượt \(L=7\) nên phần ngọn dài \(7\) gãy ra. Cuối cùng các chiều cao là \(1,4,4,2\).

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

Ví dụ 2

Input

Output

Giải thích

Ngày 1, tưới từ mảnh đất \(5\) trong bán kính \(1\) làm chiều cao ở các mảnh đất \(5,6\) được nhân với \(7\), thành \(63,7\). Ở mảnh đất \(5\), phần ngọn dài \(L=10\) liên tục gãy ra cho đến khi chiều cao nhỏ hơn \(10\). Cuối cùng chiều cao ở hai mảnh đất này lần lượt là \(3,7\).

Ví dụ này thỏa mãn các nhóm \(1,2,3,6\) .

Ví dụ 3

Input

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,3,4,6\) .

Nguồn

3. JOI 2022 - Ants and Sugar

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

JOI-kun là một nhà sinh học. Cậu dự định thực hiện một thí nghiệm với kiến và các viên đường.

Thí nghiệm diễn ra trên một thanh thẳng dài \(10^9\), đặt theo chiều từ trái sang phải. Điểm cách đầu trái của thanh một khoảng \(x\) được gọi là điểm có tọa độ \(x\).

Ban đầu, trên thanh không có gì. JOI-kun thực hiện \(Q\) thao tác. Thao tác thứ \(i\) (\(1\le i\le Q\)) được mô tả bởi ba số nguyên \(T_i,X_i,A_i\):

Nếu \(T_i=1\), đặt thêm \(A_i\) con kiến tại điểm có tọa độ \(X_i\).
Nếu \(T_i=2\), đặt thêm \(A_i\) viên đường tại điểm có tọa độ \(X_i\).

Kiến và đường rất nhỏ nên có thể có nhiều con kiến hoặc nhiều viên đường tại cùng một điểm. Nhiều thao tác cũng có thể được thực hiện tại cùng một tọa độ.

Những con kiến trong thí nghiệm có một đặc tính kỳ lạ. Nếu JOI-kun vỗ tay, mỗi con kiến thực hiện hành động sau đúng một lần: nếu có viên đường nào cách nó không quá \(L\), nó tùy ý chọn một viên như vậy và ăn viên đó. Có thể nhiều con kiến cùng ăn một viên đường vào cùng một thời điểm.

Với mỗi \(k\) từ \(1\) đến \(Q\), hãy trả lời câu hỏi: giả sử JOI-kun vỗ tay sau thao tác thứ \(k\), số viên đường lớn nhất có thể được ít nhất một con kiến ăn là bao nhiêu?

Hãy viết chương trình trả lời tất cả các câu hỏi từ dãy thao tác và giá trị \(L\).

Lưu ý JOI-kun không thực sự vỗ tay trong quá trình thực hiện các thao tác. Vì vậy, vị trí của kiến không thay đổi và các viên đường không bị ăn mất; mỗi câu hỏi là một giả định riêng trên toàn bộ những gì đã được đặt lên thanh.

Dữ liệu vào

Dữ liệu được cho theo định dạng sau. Mọi giá trị đều là số nguyên.

Q L
T_1 X_1 A_1
T_2 X_2 A_2
...
T_Q X_Q A_Q

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(k\) ghi số viên đường lớn nhất có thể được ít nhất một con kiến ăn nếu JOI-kun vỗ tay sau thao tác thứ \(k\).

Ràng buộc

\(1\le Q\le500000\).
\(1\le L\le10^9\).
\(T_i\in\{1,2\}\) với mọi \(1\le i\le Q\).
\(0\le X_i\le10^9\) với mọi \(1\le i\le Q\).
\(1\le A_i\le10^9\) với mọi \(1\le i\le Q\).

Phân nhóm

Nhóm 1 (6 điểm): \(Q\le3000\).
Nhóm 2 (16 điểm): \(L=1\); với mọi \(1\le i\le Q\), ta có \(X_i\le Q-1\) và \(X_i+T_i\) là số chẵn.
Nhóm 3 (26 điểm): \(Q\) là số chẵn; \(T_i=1\) với mọi \(1\le i\le Q/2\), và \(T_i=2\) với mọi \(Q/2+1\le i\le Q\).
Nhóm 4 (52 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Đặt một con kiến tại tọa độ \(1\). Nếu vỗ tay lúc này thì chưa có đường, nên đáp án là \(0\).
Đặt một viên đường tại tọa độ \(2\). Con kiến ở tọa độ \(1\) có thể ăn viên đường đó, nên đáp án là \(1\).
Đặt một con kiến tại tọa độ \(3\). Nếu vỗ tay, cả hai con kiến ở tọa độ \(1,3\) đều ăn viên đường ở tọa độ \(2\). Chỉ một viên đường được ăn, nên đáp án vẫn là \(1\).
Đặt một viên đường tại tọa độ \(0\). Số viên đường được ăn là lớn nhất khi con kiến ở tọa độ \(1\) ăn viên tại \(0\), còn con kiến ở tọa độ \(3\) ăn viên tại \(2\). Đáp án là \(2\).

Ví dụ này thỏa mãn các nhóm \(1,2,4\) .

Ví dụ 2

Input

20 1
2 16 778913911
1 7 558407445
1 1 589762439
1 17 74646747
1 1 149104909
1 15 956697952
2 6 389372991
2 4 867453845
1 15 157353445
1 9 846177695
1 7 747107163
2 10 525670462
2 16 478912944
2 6 301733761
2 12 132966485
1 1 748012313
2 10 830922632
1 19 969484637
1 13 370330582
1 1 464798040

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,2,4\) .

Ví dụ 3

Input

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,4\) .

Ví dụ 4

Input

20 268886972
1 984472666 733463744
1 478477245 94817772
1 242536956 330762563
1 65794782 319137646
1 320548477 937296140
1 815011370 938193848
1 565184190 917533785
1 245417414 534089975
1 529908772 977043962
1 603891865 700935654
2 167042244 479827216
2 173921297 798343455
2 916159596 810126726
2 999299355 465535307
2 965968070 501768990
2 936073643 174976034
2 832859952 778072072
2 955489596 704853861
2 246733786 382428992
2 227669861 390905006

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,3,4\) .