JOI 2017 Final Camp - Ngày 2

Ở Cộng hòa JOI có \(N\) nhà ga, được đánh số từ \(1\) đến \(N\) và nằm theo thứ tự chiều kim đồng hồ trên một tuyến đường sắt hình tròn.

Có \(N\) loại vé tàu, được đánh số từ \(1\) đến \(N\). Một vé loại \(i\) với \(1 \le i \le N-1\) cho phép một người đi từ ga \(i\) đến ga \(i+1\) hoặc theo chiều ngược lại. Một vé loại \(N\) cho phép một người đi giữa ga \(1\) và ga \(N\) theo một trong hai chiều. Vé chỉ được bán theo gói gồm đúng \(N\) vé, mỗi loại một vé.

Bạn làm việc tại một đại lý du lịch và hôm nay nhận được \(M\) yêu cầu. Yêu cầu thứ \(i\) cho biết có \(C_i\) người muốn đi từ ga \(A_i\) đến ga \(B_i\). Những người thuộc cùng một yêu cầu không nhất thiết phải đi cùng tuyến đường.

Yêu cầu

Tính số gói vé ít nhất cần mua để đáp ứng tất cả các yêu cầu.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên \(N,M\), là số nhà ga và số yêu cầu.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) gồm ba số nguyên \(A_i,B_i,C_i\), cho biết có \(C_i\) người muốn đi từ ga \(A_i\) đến ga \(B_i\).

Dữ liệu ra

In ra số gói vé ít nhất cần mua.

Ràng buộc

• \(3 \le N \le 200\,000\).
• \(1 \le M \le 100\,000\).
• \(1 \le A_i,B_i \le N\) với mọi \(1 \le i \le M\).
• \(1 \le C_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le M\).
• \(A_i \ne B_i\) với mọi \(1 \le i \le M\).

Phân nhóm

1. Subtask 1 (10 điểm): \(N \le 20\), \(M \le 20\), và \(C_i=1\) với mọi \(i\).
2. Subtask 2 (35 điểm): \(N \le 300\), \(M \le 300\), và \(C_i=1\) với mọi \(i\).
3. Subtask 3 (20 điểm): \(N \le 3\,000\), \(M \le 3\,000\), và \(C_i=1\) với mọi \(i\).
4. Subtask 4 (20 điểm): \(C_i=1\) với mọi \(i\).
5. Subtask 5 (15 điểm): Không có ràng buộc bổ sung.

Giới hạn

• Thời gian: 4 giây.
• Bộ nhớ: 256 MB.

Ví dụ

3 3
1 2 1
2 3 1
3 1 1

1

3 2
1 2 4
1 2 2

3

6 3
1 4 1
2 5 1
3 6 1

2

Anna và Bruno là hai nhà khảo cổ đang khảo sát một khu di tích tại Iran. Anna đến di tích để tìm cổ vật, còn Bruno phân tích kết quả tại trại căn cứ.

Cuộc khảo sát kéo dài \(Q=1\,000\) ngày. Mỗi ngày, Anna gửi cho Bruno một kết quả được biểu diễn bởi số nguyên \(X\). Thiết bị liên lạc chỉ có thể được dùng một lần mỗi ngày và gửi một dãy nhị phân độ dài \(N=150\).

Thiết bị bị hỏng tại một số vị trí. Một vị trí hỏng luôn truyền giá trị \(0\), bất kể Anna đặt giá trị nào. Khi gửi, Anna biết số lượng và vị trí các chỗ hỏng, nhưng Bruno không biết. Tập vị trí hỏng có thể thay đổi mỗi ngày.

Yêu cầu

Viết hai chương trình cùng ngôn ngữ để thực hiện việc liên lạc:

• Chương trình của Anna nhận \(N,X,K\) và mảng vị trí hỏng \(P\), rồi thiết lập dãy \(S\) cần gửi.
• Chương trình của Bruno nhận dãy \(A\) mà thiết bị truyền đến và phải khôi phục \(X\).

Ở vị trí hoạt động bình thường, \(A\) bằng \(S\). Ở vị trí hỏng, \(A\) luôn bằng \(0\).

Chi tiết cài đặt

Bạn phải nộp hai tệp viết bằng cùng một ngôn ngữ.

Tệp thứ nhất là Anna.c hoặc Anna.cpp, phải khai báo #include "Annalib.h" và cài đặt hàm:

void Anna(int N, long long X, int K, int P[])

Trong mỗi bộ kiểm thử, hàm này được gọi \(Q=1\,000\) lần:

• \(N\) là độ dài dãy cần gửi.
• \(X\) là số nguyên cần gửi.
• \(K\) là số vị trí hỏng.
• P là mảng độ dài \(K\) chứa các vị trí hỏng.

Trong Anna, bạn phải gọi hàm sau:

void Set(int pos, int bit)

• pos là vị trí cần đặt và phải thuộc đoạn \([0,N-1]\). Gọi với vị trí ngoài đoạn này dẫn đến Wrong Answer [1]. Không được gọi hai lần với cùng một pos; vi phạm dẫn đến Wrong Answer [2].
• bit phải bằng \(0\) hoặc \(1\); giá trị khác dẫn đến Wrong Answer [3].
• Set phải được gọi đúng \(N\) lần trong mỗi lần gọi Anna. Số lần gọi khác \(N\) dẫn đến Wrong Answer [4].

Nếu một lời gọi của Anna không hợp lệ, chương trình sẽ bị dừng.

Tệp thứ hai là Bruno.c hoặc Bruno.cpp, phải khai báo #include "Brunolib.h" và cài đặt hàm:

long long Bruno(int N, int A[])

Trong mỗi bộ kiểm thử, hàm này được gọi \(Q=1\,000\) lần:

• \(N\) là độ dài dãy Bruno nhận được.
• A là mảng số nguyên độ dài \(N\) chứa dãy nhận được.
• Hàm phải khôi phục và trả về \(X\).

Quy trình chấm

Nếu chương trình bị xác định là sai, quá trình chấm dừng ngay lập tức.

1. Đặt cnt = 0.
2. Gọi Anna một lần.
3. Gọi \(S\) là dãy được Anna thiết lập. Đặt các vị trí thuộc \(P\) trong \(S\) thành \(0\) để thu được \(A\), rồi gọi Bruno với tham số \(A\).
4. Tăng cnt thêm \(1\). Nếu cnt < Q, quay lại bước 2; nếu cnt = Q, chuyển sang bước 5.
5. Tính điểm chương trình.

Thời gian và bộ nhớ được tính cho các bước 1 đến 4.

Các lời gọi Anna và Bruno không được gây lỗi thực thi. Bạn có thể cài đặt thêm hàm hoặc dùng biến toàn cục, nhưng mọi hàm và biến toàn cục nội bộ nên được khai báo static để tránh xung đột khi liên kết với bộ chấm. Khi chấm chính thức, chương trình của Anna và Bruno chạy trong hai tiến trình riêng biệt nên không thể chia sẻ biến toàn cục.

Trong mỗi tiến trình, hàm tương ứng được gọi \(Q=1\,000\) lần; các biến phải được khởi tạo phù hợp. Chương trình không được dùng đầu vào/đầu ra chuẩn hoặc giao tiếp với tệp theo bất kỳ cách nào.

Bộ chấm mẫu

Gói đính kèm của đề chứa bộ chấm mẫu và mã nguồn mẫu. Nếu hai tệp của bạn là Anna.c, Bruno.c hoặc Anna.cpp, Bruno.cpp, có thể biên dịch như sau:

gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm
g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Bộ chấm thật khác bộ chấm mẫu. Bộ 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 của bộ chấm mẫu

• Dòng đầu chứa số nguyên \(Q\).
• Sau đó là thông tin của \(Q\) truy vấn, mỗi truy vấn gồm hai dòng:
• Dòng đầu gồm \(N,X,K\).
• Dòng thứ hai gồm \(K\) số \(P_0,P_1,\ldots,P_{K-1}\).

Dữ liệu ra của bộ chấm mẫu

• Nếu chương trình vi phạm một quy tắc, bộ chấm in loại lỗi theo dạng Wrong Answer [1] rồi dừng. Nếu có nhiều lỗi, chỉ một lỗi được báo.
• Nếu mọi lời gọi Anna đều hợp lệ, bộ chấm in Accepted cùng giá trị \(L^*\) được định nghĩa trong phần chấm điểm.

Ràng buộc

• \(Q=1\,000\).
• \(N=150\).
• \(0 \le X \le 1\,000\,000\,000\,000\,000\,000\).
• \(1 \le K \le 40\).
• \(0 \le P_i \le N-1\) với mọi \(0 \le i \le K-1\).
• \(P_i<P_{i+1}\) với mọi \(0 \le i \le K-2\).

Chấm điểm

Với mỗi bộ kiểm thử, xét số nguyên lớn nhất \(L \le 40\) sao cho Bruno trả lời đúng \(X\) cho mọi truy vấn có \(K \le L\). Gọi \(L^*\) là giá trị nhỏ nhất của \(L\) trên tất cả các bộ kiểm thử của bài.

Điểm số được tính như sau:

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 256 MB.

Ví dụ giao tiếp

Ví dụ sau không thỏa mãn ràng buộc chính thức vì \(Q=2\) và \(N=3\).

2
3 14 1
2
3 9 2
0 1

Các lời gọi tương ứng:

Tài liệu gốc chỉ mô tả chuỗi lời gọi và giá trị trả về cho ví dụ giao tiếp này, không cho một dòng kết quả cụ thể của bộ chấm mẫu.

Công ty Đường sắt JOI vận hành một tuyến đường sắt thẳng gồm \(N\) ga, được đánh số từ \(1\) đến \(N\). Với mỗi \(1 \le i \le N-1\), ga \(i\) và ga \(i+1\) được nối bằng một đoạn đường ray.

Có \(K\) loại tàu chạy theo cả hai hướng, được đánh số từ \(1\) đến \(K\). Mỗi ga có một cấp độ từ \(1\) đến \(K\); ga \(i\) có cấp độ \(L_i\). Hai ga đầu mút, ga \(1\) và ga \(N\), đều có cấp độ \(K\).

Tàu loại \(j\) dừng tại mọi ga có cấp độ ít nhất \(j\) và không dừng tại các ga còn lại. Do hai ga đầu mút có cấp độ \(K\), mọi loại tàu đều dừng ở đó.

Trong hành trình, hành khách có thể đi tàu theo hướng ngược với đích, đi quá đích và đổi tàu tùy ý, nhưng cuối cùng phải dừng tại ga đích. Họ muốn tối thiểu hóa số lần dừng trung gian, không quan tâm đến số ga đi qua hay số lần đổi tàu. Nếu dừng ở một ga để đổi tàu, lần dừng đó được tính là một lần dừng trung gian. Lần dừng ban đầu tại ga xuất phát và lần dừng cuối tại ga đích không được tính.

Yêu cầu

Với mỗi truy vấn, tính số lần dừng trung gian ít nhất trên một hành trình từ ga xuất phát đến ga đích.

Dữ liệu vào

• Dòng đầu gồm ba số nguyên \(N,K,Q\): số ga, số loại tàu và số truy vấn.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(L_i\), là cấp độ của ga \(i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(k\) gồm hai số nguyên \(A_k,B_k\), là ga xuất phát và ga đích của hành khách thứ \(k\).

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) chứa số lần dừng trung gian ít nhất trên một hành trình từ ga \(A_k\) đến ga \(B_k\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le K \le N\).
• \(1 \le Q \le 100\,000\).
• \(1 \le L_i \le K\) với mọi \(1 \le i \le N\).
• \(1 \le A_k,B_k \le N\) với mọi \(1 \le k \le Q\).
• \(A_k \ne B_k\) với mọi \(1 \le k \le Q\).

Phân nhóm

1. Subtask 1 (5 điểm): \(N \le 100\), \(K \le 100\), \(Q \le 50\).
2. Subtask 2 (15 điểm): \(Q \le 50\).
3. Subtask 3 (25 điểm): \(K \le 20\).
4. Subtask 4 (55 điểm): Không có ràng buộc bổ sung.

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 512 MB.

Ví dụ

9 3 3
3
1
1
1
2
2
2
3
3
2 4
4 9
6 7

1
3
0

5 2 1
2
1
1
1
2
1 4

1

15 5 15
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
11 1
5 3
6 11
9 12
15 14
15 2
3 12
2 1
4 8
15 5
12 6
1 13
13 8
14 9

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