JOI 2021 - Tuyển chọn mùa xuân - Ngày 3

Anna và Bruno là hai nhà khảo cổ học đang khai quật tàn tích của vương quốc IOI. Tại khu di tích A, Anna tìm thấy bản thiết kế một cỗ máy cổ. Tại khu di tích B, Bruno tìm thấy chính cỗ máy đó.

Cỗ máy gồm \(N\) thiết bị gắn thành một hàng trên dây điện. Có ba loại thiết bị, gọi là X, Y, Z. Từ trái sang phải, các thiết bị được đánh số từ \(0\) đến \(N-1\). Loại của thiết bị \(i\) là \(S_i\), một trong ba ký tự X, Y, Z.

Cỗ máy quá lớn, nên Bruno quyết định tháo từng thiết bị ra. Tuy nhiên, chúng tương tác với nhau qua dây điện, nên thứ tự tháo cần được lựa chọn cẩn thận.

Ta định nghĩa lần tháo tốt như sau:

• Giả sử các thiết bị \(x,y,z\) (\(0\le x<y<z\le N-1\)) chưa bị tháo, \(S_x=\mathrm{X}\), \(S_y=\mathrm{Y}\), \(S_z=\mathrm{Z}\). Đồng thời, mọi thiết bị có chỉ số \(j\) với \(x<j<y\) đã bị tháo, và mọi thiết bị có chỉ số \(k\) với \(y<k<z\) đã bị tháo. Nếu tất cả điều kiện này thỏa mãn, việc tháo thiết bị \(y\) được gọi là một lần tháo tốt.
• Mọi cách tháo một thiết bị khác đều không phải lần tháo tốt.

Bruno phải tháo cả \(N\) thiết bị sao cho số lần tháo tốt lớn nhất có thể. Nhưng ba loại thiết bị trông giống nhau nên Bruno không phân biệt được chúng.

Anna có bản thiết kế nên biết loại của từng thiết bị. Cô sẽ dùng máy phát để giúp Bruno bằng cách gửi một dãy ký tự, mỗi ký tự là \(0\) hoặc \(1\).

Hãy viết các chương trình thực hiện chiến lược của Anna và Bruno để đạt số lần tháo tốt lớn nhất có thể. Trong bài này, Anna gửi càng ít ký tự cho Bruno thì điểm càng cao.

Chi tiết cài đặt

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

Tệp Anna.cpp cài đặt chiến lược của Anna, nạp Anna.h bằng chỉ thị #include và cài đặt hàm:

void Anna(int N, std::vector<char> S);

Hàm được gọi đúng một lần lúc bắt đầu mỗi bộ dữ liệu. N là số thiết bị; S là mảng độ dài \(N\), trong đó S[i] là loại thiết bị \(i\), bằng 'X', 'Y' hoặc 'Z'.

Anna có thể gọi hàm sau để gửi một ký tự cho Bruno:

void Send(int a);

• a phải bằng \(0\) hoặc \(1\); nếu không, chương trình bị chấm Wrong Answer [1].
• Không được gọi Send quá \(200000\) lần; nếu vượt quá thì bị chấm Wrong Answer [2].

Tệp Bruno.cpp cài đặt chiến lược của Bruno, nạp Bruno.h bằng chỉ thị #include và cài đặt:

void Bruno(int N, int L, std::vector<int> A);

Sau lời gọi Anna, hàm này được gọi đúng một lần. N là số thiết bị; L là số ký tự Anna đã gửi; A là mảng độ dài \(L\) chứa các ký tự đó theo đúng thứ tự A[0], A[1], ..., A[L-1]. Mỗi phần tử là \(0\) hoặc \(1\).

Bruno có thể gọi hàm sau để chỉ ra thứ tự tháo:

void Remove(int d);

• d là chỉ số thiết bị được tháo. Phải có \(0\le d\le N-1\); nếu không, bị chấm Wrong Answer [3].
• Không được gọi Remove với cùng một giá trị d nhiều lần; nếu không, bị chấm Wrong Answer [4].
• Phải gọi Remove đúng \(N\) lần. Khi Bruno kết thúc, nếu số lời gọi khác \(N\) thì bị chấm Wrong Answer [5].
• Sau khi tháo cả \(N\) thiết bị, số lần tháo tốt phải lớn nhất có thể. Nếu không đạt điều này, bị chấm Wrong Answer [6].

Lưu ý quan trọng

• Bạn có thể viết thêm hàm nội bộ hoặc dùng biến toàn cục. Hai tệp nộp được biên dịch cùng grader thành một tệp thực thi. Mọi hàm nội bộ và biến toàn cục cần nằm trong namespace không tên để tránh xung đột với tệp khác. Khi chấm thực tế, Anna và Bruno chạy trong hai tiến trình và không thể chia sẻ biến toàn cục.
• Chương trình 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. Đượ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ử

Trang cuộc thi cung cấp gói gồm grader mẫu và các tệp chương trình mẫu. Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng thư mục, rồi biên dịch:

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

Nếu thành công, tệp thực thi grader được tạo. Grader thực tế khác grader mẫu. Grader 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

Grader mẫu đọc theo định dạng:

N
S_0 S_1 ... S_{N-1}

Hai ký tự \(S_i,S_{i+1}\) liên tiếp (\(0\le i\le N-2\)) được phân cách bằng một dấu cách.

Dữ liệu ra

Khi chương trình kết thúc bình thường, grader mẫu ghi:

• Nếu vi phạm một trong các lỗi Wrong Answer [1] đến Wrong Answer [5]: loại lỗi, chẳng hạn Wrong Answer [1].
• Nếu không: Accepted: L D, trong đó \(L\) là số lần gọi Send, còn \(D\) là số lần tháo tốt. Grader mẫu không kiểm tra tính tối ưu, tức không kiểm tra lỗi Wrong Answer [6]; đây là điểm khác với grader thực tế.

Nếu chương trình thỏa mãn nhiều loại lỗi trong các lỗi \(1\) đến \(5\), grader mẫu chỉ thông báo một loại.

Ràng buộc

• \(3\le N\le100000\).
• \(S_i\) là một trong các ký tự X, Y, Z với mọi \(0\le i\le N-1\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N\le18\).
• Nhóm 2 (95 điểm): Không có ràng buộc bổ sung. Điểm được tính như dưới đây.

Gọi \(L\) là số lần gọi Send lớn nhất trên tất cả bộ dữ liệu của nhóm 2.

Ở đây, \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Ví dụ giao tiếp

Ví dụ 1

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

4
X Y X Z

Lời gọi hàm

Giải thích

Các thiết bị được tháo như sau:

1. Ban đầu, dãy thiết bị là X Y X Z.
2. Tháo thiết bị \(2\), dãy trở thành X Y - Z. Dấu - biểu thị vị trí đã tháo.
3. Tháo thiết bị \(1\), dãy trở thành X - - Z. Bộ \((x,y,z)=(0,1,3)\) thỏa mãn điều kiện, nên đây là lần tháo tốt.
4. Tháo thiết bị \(0\), dãy trở thành - - - Z.
5. Cuối cùng, tháo thiết bị \(3\), dãy trở thành - - - -.

Có \(1\) lần tháo tốt. Với đầu vào này, không thể có nhiều hơn \(1\) lần tháo tốt.

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

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 3. Đề 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.

Phố JOI là một con phố dài theo hướng tây - đông, được xem là trục số.

Sắp tới, \(N\) nhân vật quan trọng (VIP), đánh số từ \(1\) đến \(N\), sẽ đi bộ trên phố. VIP \(i\) xuất phát từ tọa độ \(A_i\) vào thời điểm \(T_i\) và đi đến tọa độ \(B_i\) với tốc độ \(1\) đơn vị khoảng cách mỗi đơn vị thời gian. Nếu \(A_i<B_i\), người đó đi theo chiều dương với tốc độ không đổi; nếu \(A_i>B_i\), người đó đi theo chiều âm với tốc độ không đổi.

Công việc của vệ sĩ là đi trên phố và bảo vệ các VIP. Để bảo vệ một VIP, vệ sĩ phải đi cùng người đó trong một khoảng thời gian. Có thể bắt đầu bảo vệ giữa hành trình hoặc ngừng trước khi VIP đến đích. Thời điểm bắt đầu hoặc kết thúc bảo vệ không nhất thiết là số nguyên. Tuy nhiên, kể cả khi nhiều VIP ở cùng tọa độ, một vệ sĩ chỉ có thể bảo vệ tối đa một VIP tại một thời điểm.

Vệ sĩ có thể tự do di chuyển trên phố với tốc độ không quá \(1\). Sau khi bảo vệ một VIP, vệ sĩ được phép di chuyển đến nơi khác rồi bảo vệ VIP khác. Khi đi cùng VIP \(i\), vệ sĩ nhận \(C_i\) yên cho mỗi đơn vị khoảng cách đã bảo vệ người đó. Bảo đảm \(C_i\) là số nguyên chẵn.

Bạn làm việc tại một công ty bảo vệ và đang lên \(Q\) kế hoạch, đánh số từ \(1\) đến \(Q\). Trong kế hoạch \(j\), một vệ sĩ bắt đầu làm việc tại tọa độ \(X_j\) vào thời điểm \(P_j\). Hãy tính tổng thù lao lớn nhất có thể nhận được cho từng kế hoạch.

Với các ràng buộc của bài, có thể chứng minh rằng tổng thù lao lớn nhất của mỗi kế hoạch luôn là số nguyên.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Mọi giá trị đều là số nguyên.

N Q
T_1 A_1 B_1 C_1
...
T_N A_N B_N C_N
P_1 X_1
...
P_Q X_Q

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) (\(1\le j\le Q\)) chứa số nguyên là tổng thù lao lớn nhất của kế hoạch \(j\).

Ràng buộc

• \(1\le N\le2800\).
• \(1\le Q\le3000000\).
• \(1\le T_i,A_i,B_i,C_i\le10^9\) với mọi \(1\le i\le N\).
• \(A_i\ne B_i\) với mọi \(1\le i\le N\).
• \(C_i\) là số nguyên chẵn với mọi \(1\le i\le N\).
• \(1\le P_j,X_j\le10^9\) với mọi \(1\le j\le Q\).

Phân nhóm

• Nhóm 1 (6 điểm): \(T_i,A_i,B_i\le3000\) với mọi \(1\le i\le N\); \(P_j,X_j\le3000\) với mọi \(1\le j\le Q\).
• Nhóm 2 (7 điểm): \(Q=1\).
• Nhóm 3 (15 điểm): \(Q\le3000\).
• Nhóm 4 (20 điểm): \(Q\le40000\).
• Nhóm 5 (52 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

8
2

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

15
0

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

30
27
48
30
48

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 3. Đề 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.

Có \(N\) hòn đảo, đánh số từ \(1\) đến \(N\), mỗi đảo có một chú hải ly sinh sống. Các đảo được nối bởi \(N-1\) cây cầu hai chiều, đánh số từ \(1\) đến \(N-1\). Cầu \(i\) nối đảo \(A_i\) với đảo \(B_i\). Có thể đi giữa hai đảo bất kỳ qua các cây cầu.

Thỉnh thoảng, hải ly ở một số đảo tụ họp tại một đảo để tổ chức cuộc họp. Khi danh sách tham dự đã được xác định, địa điểm họp được chọn trong các đảo thỏa mãn:

Tổng số cây cầu mà những người tham dự phải đi qua để đến đảo được chọn là nhỏ nhất.

Mỗi người tham dự đi từ đảo mình sống đến địa điểm họp bằng hành trình qua ít cầu nhất.

Những người tham dự càng mong chờ cuộc họp nếu có nhiều địa điểm có thể được chọn. Khi danh sách tham dự đã cố định, độ mong chờ của cuộc họp là số đảo có thể làm địa điểm họp và thỏa mãn điều kiện tối thiểu hóa tổng số cầu ở trên.

Với mỗi số nguyên \(j\) từ \(1\) đến \(N\), hãy tìm độ mong chờ lớn nhất trong các cuộc họp có đúng \(j\) hải ly tham dự.

Cho thông tin các đảo và cầu, hãy tính giá trị đó cho mọi số lượng người tham dự.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Mọi giá trị đều là số nguyên.

N
A_1 B_1
...
A_{N-1} B_{N-1}

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(j\) (\(1\le j\le N\)) chứa độ mong chờ lớn nhất của một cuộc họp có \(j\) người tham dự.

Ràng buộc

• \(1\le N\le200000\).
• \(1\le A_i,B_i\le N\) với mọi \(1\le i\le N-1\).
• \(A_i\ne B_i\) với mọi \(1\le i\le N-1\).
• Có thể đi giữa hai đảo bất kỳ qua các cây cầu.

Phân nhóm

• Nhóm 1 (4 điểm): \(N\le16\).
• Nhóm 2 (16 điểm): \(N\le4000\).
• Nhóm 3 (80 điểm): Không có ràng buộc bổ sung.

Ví dụ

5
1 2
2 3
4 2
3 5

1
4
1
2
1

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

1
5
1
3
1
2
1

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 3. Đề 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.