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

JOI-kun là một thợ làm bánh chuyên nghiệp, chuyên làm bánh dango Nhật Bản. Cửa hàng của cậu sử dụng \(N\) màu bánh, được đánh số từ \(1\) đến \(N\).

Một xiên dango đẹp là món bánh nổi tiếng của cửa hàng: xiên này gồm \(N\) chiếc bánh có màu đôi một khác nhau.

Với mỗi màu, JOI-kun có \(M\) chiếc bánh. Như vậy, cậu có tổng cộng \(N\times M\) chiếc bánh, được đánh số từ \(1\) đến \(N\times M\). Cậu muốn dùng toàn bộ số bánh này cùng \(M\) que xiên để làm \(M\) xiên dango đẹp.

Để tránh nhầm màu, JOI-kun sử dụng một máy kiểm tra dango. Khi nhận danh sách chỉ số của một số chiếc bánh, máy trả về số xiên dango đẹp lớn nhất có thể làm từ những chiếc bánh đó, giả sử có đủ que xiên.

JOI-kun muốn dùng máy kiểm tra để chia \(N\times M\) chiếc bánh thành \(M\) nhóm, mỗi nhóm gồm \(N\) chiếc bánh và chứa đúng một chiếc bánh của mỗi màu. Hãy cài đặt chiến lược thực hiện việc chia nhóm này với không quá \(50\,000\) lần sử dụng máy kiểm tra.

Chi tiết cài đặt

Nộp một tệp dango3.cpp, sử dụng chỉ thị #include "dango3.h" và cài đặt hàm:

void Solve(int N, int M);

Hàm này được gọi đúng một lần cho mỗi bộ kiểm thử. N là số màu bánh và M là số xiên dango đẹp cần làm.

Chương trình có thể gọi hai hàm sau do trình chấm cung cấp:

int Query(const std::vector<int> &x);
void Answer(const std::vector<int> &a);

Query(x) gửi danh sách chỉ số bánh x tới máy kiểm tra. Giá trị trả về là số xiên dango đẹp lớn nhất có thể làm từ những chiếc bánh trong x, khi có đủ que xiên. Mỗi phần tử của x phải nằm trong đoạn \([1,N\times M]\), các phần tử phải đôi một khác nhau, và tổng số lần gọi Query không được vượt quá \(50\,000\). Danh sách rỗng được phép; khi đó giá trị trả về bằng \(0\).

Answer(a) thông báo một nhóm bánh dùng để làm một xiên dango đẹp. Danh sách a phải có đúng \(N\) phần tử thuộc đoạn \([1,N\times M]\) và chứa đúng một chiếc bánh của mỗi màu. Mỗi chỉ số bánh chỉ được xuất hiện một lần trong toàn bộ các lời gọi Answer, kể cả trong cùng một lời gọi. Khi Solve kết thúc, Answer phải đã được gọi đúng \(M\) lần.

Các trường hợp bị chấm sai:

Lưu ý

Chương trình được định nghĩa các hàm phụ trợ và biến toàn cục. Chương trình không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. 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 hỗ trợ trong phần đính kèm chứa trình chấm mẫu grader.cpp, tệp tiêu đề dango3.h, mã nguồn mẫu dango3.cpp và các tệp đầu vào mẫu. Đặt ba tệp mã nguồn/tiêu đề trong cùng thư mục rồi chạy:

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

Khi biên dịch thành công, tệp thực thi grader được tạo ra. Trình chấm thật khác trình chấm mẫu. 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ủa trình chấm mẫu có dạng:

N M
C_1 C_2 ... C_{N*M}

Trong đó \(C_i\) là màu của chiếc bánh \(i\), thuộc đoạn \([1,N]\). Đây là thông tin riêng của trình chấm, không phải tham số truyền cho Solve.

Nếu chương trình được chấp nhận, trình chấm mẫu xuất số lần gọi Query, chẳng hạn Accepted: 2022. Nếu chương trình bị chấm sai, trình chấm mẫu xuất loại lỗi, chẳng hạn Wrong Answer [4]. Nếu đồng thời vi phạm nhiều điều kiện, trình chấm mẫu chỉ báo một loại lỗi.

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 gửi qua các hàm gọi lại được mô tả ở trên.

Ràng buộc

• \(1\le C_i\le N\) với mọi \(1\le i\le N\times M\).
• Với mỗi màu \(j\) (\(1\le j\le N\)), có đúng \(M\) chỉ số \(i\) thỏa mãn \(C_i=j\).
• \(N\), \(M\) và mọi \(C_i\) đều là số nguyên.

Phân nhóm

1. \(2\) điểm: \(N=4\), \(M=4\).
2. \(5\) điểm: \(N=100\), \(M=10\).
3. \(15\) điểm: \(N=200\), \(M=25\).
4. \(78\) điểm: \(N=400\), \(M=25\).

Ví dụ giao tiếp

Ví dụ 1

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

3 2
3 3 1 2 1 2

Lời gọi và giá trị trả về

Solve(3, 2)
Query([]) -> 0
Query([4, 2, 1, 3]) -> 1
Query([3, 4, 5]) -> 0
Query([2, 6, 5]) -> 1
Query([6, 5, 4, 3, 2, 1]) -> 2
Answer([1, 6, 5])
Answer([2, 3, 4])

Giải thích

Đầu vào này không thỏa mãn ràng buộc của bất kỳ nhóm nào. Tệp sample-02.txt trong gói hỗ trợ thỏa mãn ràng buộc của nhóm \(1\).

Nguồn

Nguồn: JOI 2021/2022, Spring Training Camp, Contest 4. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.

JOI-kun có \(N\) con cá, được đánh số từ \(1\) đến \(N\). Kích thước của con cá \(i\) là \(A_i\).

Khi nuôi cá, cần chú ý rằng hai con cá ở cạnh nhau có thể ăn nhau theo thời gian. Hai con cá được coi là ở cạnh nhau nếu không có con cá nào nằm giữa chúng. Cụ thể, nếu cá \(x\) có kích thước lớn hơn hoặc bằng cá \(y\) và hai con ở cạnh nhau, cá \(x\) có thể ăn cá \(y\). Sau đó, kích thước của cá \(x\) bằng tổng kích thước trước đó của hai con. Nếu hai con có cùng kích thước, con nào cũng có thể ăn con còn lại.

JOI-kun sẽ nuôi cá trong \(Q\) ngày. Để giết thời gian, cậu thực hiện các thí nghiệm tưởng tượng. Vào ngày thứ \(j\), cậu thực hiện một trong hai thao tác:

• Loại 1: Cho cá \(X_j\) ăn một loại thức ăn đặc biệt. Sau đó, kích thước của cá \(X_j\) trở thành \(Y_j\).
• Loại 2: Chỉ lấy những con cá có chỉ số từ \(L_j\) đến \(R_j\) và tưởng tượng đặt chúng vào bể theo thứ tự \(L_j,L_j+1,\ldots,R_j\) từ trái sang phải. Theo quy luật trên, cuối cùng chỉ còn một con sống sót. Chỉ số của con sống sót phụ thuộc vào việc chọn con nào bị ăn và thời điểm các lần ăn xảy ra. JOI-kun muốn biết có bao nhiêu chỉ số có thể là chỉ số của con sống sót. Trong thí nghiệm, thứ tự các con cá không thay đổi và không có hai con cá cùng ăn một con khác tại cùng một thời điểm.

Hãy tính số chỉ số có thể sống sót cho từng thao tác loại \(2\). Các thí nghiệm này chỉ diễn ra trong tưởng tượng: không có con cá nào thực sự bị ăn, và thí nghiệm không làm thay đổi kích thước của các con cá trong những ngày sau.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng:

N
A_1 A_2 ... A_N
Q
(Truy vấn 1)
(Truy vấn 2)
...
(Truy vấn Q)

Mỗi truy vấn nằm trên một dòng, gồm các số nguyên cách nhau bởi dấu cách. Số đầu tiên là \(T_j\):

• Nếu \(T_j=1\), dòng có dạng 1 X_j Y_j, nghĩa là đặt kích thước cá \(X_j\) thành \(Y_j\).
• Nếu \(T_j=2\), dòng có dạng 2 L_j R_j, nghĩa là thực hiện thí nghiệm tưởng tượng với đoạn cá từ \(L_j\) đến \(R_j\).

Dữ liệu ra

Với mỗi truy vấn loại \(2\), theo đúng thứ tự xuất hiện, xuất một dòng chứa số chỉ số có thể là chỉ số của con cá sống sót.

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le Q\le 100\,000\).
• \(1\le A_i\le 10^9\) với mọi \(1\le i\le N\).
• \(T_j\in\{1,2\}\).
• Với truy vấn loại \(1\): \(1\le X_j\le N\) và \(1\le Y_j\le 10^9\).
• Với truy vấn loại \(2\): \(1\le L_j\le R_j\le N\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(N\le 500\), \(Q\le 500\).
2. \(8\) điểm: \(Q=1\) và truy vấn duy nhất là loại \(2\) với \(L_1=1\), \(R_1=N\).
3. \(12\) điểm: \(Q\le 1000\).
4. \(23\) điểm: Mọi truy vấn đều là loại \(2\).
5. \(35\) điểm: Với mọi truy vấn loại \(2\), \(L_j=1\) và \(R_j=N\).
6. \(17\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

5
2
2
3
1

13
10 4 2 5 20 5 4 8 20 10 3 3 7
1
2 1 13

7

12
32 32 4 1 1 1 1 4 4 16 32 128
7
2 1 12
2 2 6
2 8 10
2 1 9
2 3 8
2 5 9
2 2 12

12
1
1
2
6
2
1

10
2 3 5 10 1 3 4 9 5 2
8
2 1 10
1 10 5
2 1 10
1 4 1000000000
2 1 10
1 8 20
1 4 8
2 1 10

4
6
1
6

Nguồn

Nguồn: JOI 2021/2022, Spring Training Camp, Contest 4. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.

Thị trấn JOI từng là một khu công nghiệp phát triển. Nhiều nhà ga và tuyến đường sắt đã được xây dựng để vận chuyển hàng hóa. Khi thị trấn suy thoái, những nhà ga và tuyến đường sắt này không còn được sử dụng, nhưng vẫn còn tồn tại.

Có \(N\) nhà ga, được đánh số từ \(1\) đến \(N\), và \(M\) tuyến đường sắt. Tuyến thứ \(i\) nối hai chiều giữa ga \(A_i\) và ga \(B_i\), có khổ đường là \(W_i\). Có thể đi từ một ga bất kỳ đến mọi ga khác bằng các tuyến đường sắt hiện có.

Là thị trưởng, bạn muốn tận dụng hệ thống này để thu hút một công ty đường sắt và hồi sinh thị trấn. Có \(Q\) công ty đăng ký tham gia dự án. Tuy nhiên, các công ty sử dụng tàu có khổ đường khác nhau, nên cần cải tạo một số tuyến đường sắt cho phù hợp.

Công ty thứ \(j\) sử dụng khổ đường \(X_j\). Để thu hút công ty này, phải bảo đảm rằng có thể đi từ bất kỳ ga nào đến bất kỳ ga nào khác chỉ bằng những tuyến đường sắt có khổ đường \(X_j\).

Bạn được thực hiện thao tác cải tạo sau tùy ý nhiều lần: chọn một tuyến đường sắt rồi tăng hoặc giảm khổ đường của tuyến đó đi \(1\), với chi phí \(1\). Nếu khổ đường hiện tại bằng \(1\) thì không được giảm thêm.

Để quyết định lựa chọn công ty nào, hãy tính chi phí nhỏ nhất cần bỏ ra cho từng công ty. Chi phí cho mỗi công ty được tính độc lập, bắt đầu từ hệ thống đường sắt ban đầu.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng:

N M
A_1 B_1 W_1
A_2 B_2 W_2
...
A_M B_M W_M
Q
X_1
X_2
...
X_Q

Mọi giá trị đầu vào đều là số nguyên.

Dữ liệu ra

Xuất \(Q\) dòng. Dòng thứ \(j\) chứa chi phí nhỏ nhất cần bỏ ra để thu hút công ty thứ \(j\).

Ràng buộc

• \(2\le N\le 500\).
• \(N-1\le M\le 100\,000\).
• \(1\le Q\le 1\,000\,000\).
• \(1\le A_i<B_i\le N\) với mọi \(1\le i\le M\).
• \(1\le W_i\le 10^9\) với mọi \(1\le i\le M\).
• \((A_i,B_i,W_i)\ne(A_j,B_j,W_j)\) với mọi \(1\le i<j\le M\). Hai ga có thể được nối bằng nhiều tuyến có khổ đường khác nhau.
• Có thể đi từ bất kỳ ga nào đến bất kỳ ga nào khác bằng các tuyến đường sắt hiện có.
• \(1\le X_j\le 10^9\) với mọi \(1\le j\le Q\).
• \(X_j<X_{j+1}\) với mọi \(1\le j<Q\).

Phân nhóm

1. \(3\) điểm: \(M\le 16\), \(Q\le 10\).
2. \(4\) điểm: \(Q\le 10\).
3. \(7\) điểm: \(B_i=A_i+1\) với mọi \(1\le i\le M\).
4. \(28\) điểm: \(M\le 1000\).
5. \(35\) điểm: \(Q\le 20\,000\).
6. \(23\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17

8
2
5
10
9
21

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

1
1
2
0

10 20
6 7 914727791
1 8 771674531
3 5 632918108
5 9 329296846
1 7 237501112
4 9 303328173
2 6 216298255
2 10 504024991
3 8 158236886
1 10 10176179
8 9 918271145
3 6 217165898
3 6 624543444
4 9 70147274
8 9 976983490
6 9 210108505
2 9 972711062
1 10 564567289
3 7 411395464
4 7 952470985
10
115721165
198969744
356664401
429802521
513343279
610443927
741016686
786597783
898772266
903568946

1121073688
761832468
1026806785
1316097872
1321500065
1445238392
1637513141
1621778548
1733953031
1738749711

Nguồn

Nguồn: JOI 2021/2022, Spring Training Camp, Contest 4. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.