JOI 2018 Final Camp - Ngày 4

Có \(N\) viên kẹo được xếp thành một hàng trên bàn. Mỗi viên kẹo có một giá trị gọi là độ ngon. Độ ngon của viên kẹo thứ \(i\) từ trái sang là \(A_i\).

JOI-chan quyết định ăn một số viên kẹo và muốn tổng độ ngon của những viên mình ăn là lớn nhất. Tuy nhiên, cô cảm thấy việc chỉ chọn những viên ngon nhất không thú vị, nên đặt ra quy tắc: không được chọn đồng thời hai viên kẹo nằm cạnh nhau.

JOI-chan chưa quyết định sẽ ăn bao nhiêu viên. Với mỗi số nguyên \(j\) thỏa mãn \(1 \le j \le \lceil N/2 \rceil\), hãy tính tổng độ ngon lớn nhất có thể đạt được khi cô ăn đúng \(j\) viên kẹo. Ký hiệu \(\lceil x\rceil\) là số nguyên nhỏ nhất lớn hơn hoặc bằng \(x\).

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\), là số viên kẹo trên bàn.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(A_i\), là độ ngon của viên kẹo thứ \(i\) từ trái sang.

Dữ liệu ra

In \(\lceil N/2\rceil\) dòng. Dòng thứ \(j\) chứa tổng độ ngon lớn nhất khi JOI-chan ăn đúng \(j\) viên kẹo mà không chọn hai viên kề nhau.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).

Phân nhóm

1. \(8\) điểm: \(N \le 2000\).
2. \(92\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
3
5
1
7
6

7
12
10

20
623239331
125587558
908010226
866053126
389255266
859393857
596640443
60521559
11284043
930138174
936349374
810093502
521142682
918991183
743833745
739411636
276010057
577098544
551216812
816623724

936349374
1855340557
2763350783
3622744640
4439368364
5243250666
5982662302
6605901633
7183000177
7309502029

Nguồn

JOI 2018, trại huấn luyện mùa xuân, ngày thi 4: Candies.

Sau hàng trăm năm, thành phố JOI đã trở thành phế tích. Nhà thám hiểm IOI-chan đang khám phá nơi từng có thư viện. Qua khảo sát, cô biết được rằng:

• Trên giá sách có \(N\) quyển sách, xếp thành một hàng từ trái sang phải.
• Các quyển sách được đánh số từ \(1\) đến \(N\), nhưng thứ tự trên giá không nhất thiết là thứ tự các số hiệu.
• Trong một thao tác, có thể lấy cùng lúc các quyển sách nằm liên tiếp trên giá.

Đáng tiếc, IOI-chan không tìm thấy những quyển sách cũ. Tuy nhiên, cô tìm được một cỗ máy từng quản lý các thao tác trên giá sách. Khi chỉ định một hoặc nhiều quyển sách bằng số hiệu và gửi truy vấn, máy trả về số thao tác ít nhất cần thực hiện để lấy chỉ những quyển sách được chỉ định khỏi giá.

IOI-chan muốn dùng các truy vấn để xác định thứ tự sách. Nếu đảo ngược thứ tự của toàn bộ \(N\) quyển sách, mọi câu trả lời của máy đều không đổi, nên cô không cần phân biệt thứ tự từ trái sang phải với thứ tự từ phải sang trái. Vì máy đã cũ, cô chỉ được gửi nhiều nhất \(20\,000\) truy vấn.

Hãy viết chương trình xác định thứ tự các quyển sách bằng nhiều nhất \(20\,000\) truy vấn. Có thể trả lời thứ tự theo một trong hai chiều.

Chi tiết cài đặt

Bạn cần nộp một tệp library.cpp, khai báo #include "library.h" và cài đặt hàm:

void Solve(int N);

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu. Tham số N là số quyển sách trên giá. Chương trình của bạn có thể gọi các hàm sau.

int Query(const std::vector<int>& M);

Hàm trả về số thao tác ít nhất để lấy chỉ những quyển sách được chỉ định. Vectơ M có kích thước \(N\). Với mỗi \(1\le i\le N\), M[i-1] = 1 nghĩa là chọn quyển sách số \(i\), còn M[i-1] = 0 nghĩa là không chọn.

• Nếu kích thước M khác \(N\), chương trình bị đánh giá Wrong Answer [1].
• Mọi phần tử phải bằng \(0\) hoặc \(1\), và phải có ít nhất một phần tử bằng \(1\). Nếu vi phạm một trong hai điều kiện này, chương trình bị đánh giá Wrong Answer [2].
• Nếu gọi Query quá \(20\,000\) lần, chương trình bị đánh giá Wrong Answer [3].

void Answer(const std::vector<int>& res);

Hàm này thông báo thứ tự sách. Vectơ res có kích thước \(N\); res[i-1] là số hiệu quyển sách ở vị trí thứ \(i\) từ trái sang phải. Có thể trả lời thứ tự đảo ngược.

• Nếu kích thước res khác \(N\), chương trình bị đánh giá Wrong Answer [4].
• Mỗi phần tử phải là số nguyên từ \(1\) đến \(N\), nếu không chương trình bị đánh giá Wrong Answer [5].
• Các phần tử phải đôi một khác nhau, nếu không chương trình bị đánh giá Wrong Answer [6].
• Khi Solve kết thúc, nếu số lần gọi Answer khác \(1\), chương trình bị đánh giá Wrong Answer [7].
• Nếu thứ tự được trả lời không phải thứ tự thật và cũng không phải thứ tự đảo ngược của nó, chương trình bị đánh giá Wrong Answer [8].

Lưu ý quan trọng

• Bạn có thể cài đặt thêm các hàm dùng nội bộ và sử dụng 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ỳ phương thức nào. Có thể ghi thông tin gỡ lỗi ra luồng lỗi chuẩn.

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

Trang web kỳ thi cung cấp gói tải xuống chứa trình chấm mẫu và mã nguồn mẫu. Đặt grader.cpp, library.cpp và library.h trong cùng thư mục rồi biên dịch bằng lệnh mẫu:

g++ -std=c++14 -O2 -o grader grader.cpp library.cpp

Nếu 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 đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

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

• Dòng đầu chứa số nguyên \(N\), số quyển sách.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(A_i\), số hiệu quyển sách ở vị trí thứ \(i\) từ trái sang phải.

Dữ liệu ra của trình chấm mẫu

Khi chương trình kết thúc bình thường, trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn, không kèm dấu ngoặc kép:

• Nếu câu trả lời đúng, ghi số lần gọi Query, chẳng hạn Accepted : 100..
• Nếu chương trình bị đánh giá sai, ghi loại lỗi, chẳng hạn Wrong Answer [1]..

Nếu có nhiều loại lỗi, trình chấm mẫu chỉ thông báo một loại.

Ràng buộc

• \(1\le N\le 1\,000\).
• \(1\le A_i\le N\) với \(1\le i\le N\).
• \(A_i\ne A_j\) với \(1\le i<j\le N\).

Phân nhóm

1. \(19\) điểm: \(N\le 200\)
2. \(81\) điểm: Không có

Ví dụ giao tiếp

5
4
2
5
3
1

Trình chấm gọi Solve(5). Trong lần gọi này, chương trình thực hiện:

Không cần phân biệt hai chiều của giá sách. Vì vậy, gọi Answer({1,3,5,2,4}) với thứ tự đảo ngược cũng được chấp nhận.

Nguồn

JOI 2017/2018 Spring Training Camp, Contest Day 4, đề tiếng Anh chính thức.

JOI-kun là một chú lợn rừng sống trong khu rừng IOI. Khu rừng có \(N\) trạm thức ăn, được đánh số từ \(1\) đến \(N\), và \(M\) con đường. Con đường thứ \(i\) nối hai trạm \(A_i\) và \(B_i\) theo cả hai chiều; đi hết con đường theo một trong hai chiều đều mất \(C_i\) giờ. Có thể đi từ bất kỳ trạm nào đến bất kỳ trạm nào khác bằng các con đường.

JOI-kun không giỏi quay đầu. Cậu không thể quay đầu giữa một con đường để trở về trạm vừa rời đi. Hơn nữa, khi vừa đến một trạm bằng một con đường, cậu không thể lập tức đi ngược lại trên chính con đường đó để trở về trạm trước đó.

Mỗi ngày, JOI-kun tiếp tế thức ăn theo một kế hoạch gồm dãy \(L\) trạm \(X_1,X_2,\ldots,X_L\). Cậu bắt đầu tiếp tế tại trạm \(X_1\), đến các trạm trong kế hoạch theo đúng thứ tự và kết thúc việc tiếp tế tại \(X_L\). Giữa hai lần tiếp tế, cậu được phép đi qua các trạm khác. Một trạm có thể xuất hiện nhiều lần trong kế hoạch, nhưng \(X_j \ne X_{j+1}\) với mọi \(1 \le j < L\). Có thể có những kế hoạch mà cậu không thực hiện được.

Ban đầu, JOI-kun chọn kế hoạch \(X_1,X_2,\ldots,X_L\). Vào sáng ngày thứ \(k\) trong \(T\) ngày, cậu thay phần tử thứ \(P_k\) của kế hoạch bằng \(Q_k\), tức là gán \(X_{P_k}=Q_k\), rồi thực hiện kế hoạch sau khi thay đổi. Các thay đổi được giữ lại cho những ngày tiếp theo. Đảm bảo rằng sau mỗi thay đổi, hai phần tử liên tiếp của kế hoạch vẫn khác nhau.

Với mỗi ngày, hãy xác định JOI-kun có thể thực hiện kế hoạch hay không. Nếu có, hãy tính thời gian ít nhất cần thiết để hoàn thành kế hoạch đó.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên \(N,M,T,L\): số trạm, số đường, số ngày và độ dài kế hoạch.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,C_i\). Con đường thứ \(i\) nối \(A_i\) với \(B_i\) theo cả hai chiều và mất \(C_i\) giờ để đi hết.
• Trong \(L\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(X_j\), mô tả kế hoạch ban đầu.
• Trong \(T\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên \(P_k,Q_k\), mô tả phép thay đổi \(X_{P_k}=Q_k\) vào sáng ngày thứ \(k\).

Các số trên cùng một dòng được phân cách bằng dấu cách.

Dữ liệu ra

In \(T\) dòng. Dòng thứ \(k\) chứa \(-1\) nếu không thể thực hiện kế hoạch của ngày thứ \(k\); ngược lại, in thời gian ít nhất, tính bằng giờ, để thực hiện kế hoạch đó.

Ràng buộc

• \(2 \le N \le 2000\).
• \(N-1 \le M \le 2000\).
• \(1 \le T \le 100\,000\).
• \(2 \le L \le 100\,000\).
• \(1 \le A_i < B_i \le N\) với \(1 \le i \le M\).
• \((A_i,B_i) \ne (A_j,B_j)\) với \(1 \le i < j \le M\).
• Có thể đi từ bất kỳ trạm nào đến bất kỳ trạm nào khác bằng các con đường.
• \(1 \le C_i \le 1\,000\,000\,000\) với \(1 \le i \le M\).
• \(1 \le X_j \le N\) với \(1 \le j \le L\).
• \(1 \le P_k \le L\) và \(1 \le Q_k \le N\) với \(1 \le k \le T\).
• \(X_j \ne X_{j+1}\) với \(1 \le j < L\), cả trong kế hoạch ban đầu lẫn sau mỗi thay đổi.

Phân nhóm

1. \(12\) điểm: \(N \le 10\), \(M \le 10\), \(T=1\), \(L \le 10\) và \(C_i \le 10\) với mọi \(1 \le i \le M\).
2. \(35\) điểm: \(N \le 500\), \(M \le 500\), \(T=1\).
3. \(15\) điểm: \(T=1\).
4. \(38\) điểm: Không có ràng buộc bổ sung.

Ví dụ

3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1

3

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

5
2
3
-1

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

38

Nguồn

JOI 2018, trại huấn luyện mùa xuân, ngày thi 4: Wild Boar.