JOI 2013 Final Camp - Ngày 3

JOI và IOI là hai anh em sinh đôi. JOI vừa nướng xong một chiếc bánh thì IOI ngửi thấy mùi thơm và chạy đến, nên hai người quyết định chia bánh.

Chiếc bánh có dạng hình tròn. JOI cắt bánh bằng các đường xuất phát từ một điểm, tạo thành \(N\) miếng, rồi đánh số các miếng từ \(1\) đến \(N\) theo chiều ngược kim đồng hồ. Miếng \(i\) kề với miếng \(i-1\) và miếng \(i+1\), trong đó miếng \(0\) được hiểu là miếng \(N\), còn miếng \(N+1\) được hiểu là miếng \(1\). Kích thước miếng \(i\) là \(A_i\). Các giá trị \(A_i\) đôi một khác nhau.

Hai người lấy bánh theo các quy tắc sau:

• Đầu tiên, JOI được chọn một miếng bất kỳ trong \(N\) miếng.
• Sau đó, bắt đầu từ IOI, hai người luân phiên lấy mỗi lượt một miếng còn lại cho đến khi hết bánh.
• Trong mỗi lượt sau lượt đầu tiên, chỉ được lấy một miếng có ít nhất một trong hai miếng kề nó đã được lấy. Nếu có nhiều miếng như vậy, người đang đến lượt phải lấy miếng lớn nhất. Quy tắc này áp dụng cho cả JOI và IOI.

Yêu cầu

Với từng miếng bánh, hãy tính tổng kích thước các miếng JOI nhận được nếu chọn miếng đó ở lượt đầu tiên.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa số nguyên \(A_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(i\) chứa tổng kích thước các miếng JOI nhận được nếu lấy miếng \(i\) đầu tiên.

Giới hạn

• \(2 \le N \le 300\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• Các giá trị \(A_i\) đôi một khác nhau.
• Thời gian: 1,5 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm và đáp ứng giới hạn thời gian, bộ nhớ.

• Bài toán con 1 (10 điểm): \(N \le 5\,000\).
• Bài toán con 2 (90 điểm): Không có giới hạn bổ sung.

Ví dụ

5
2
8
1
10
9

13
18
12
13
12

Nếu JOI lấy miếng \(1\) đầu tiên, các lượt tiếp theo diễn ra như sau:

• IOI có thể lấy miếng \(2\) hoặc \(5\) và phải chọn miếng \(5\) vì \(9 > 8\).
• JOI có thể lấy miếng \(2\) hoặc \(4\) và phải chọn miếng \(4\) vì \(10 > 8\).
• IOI có thể lấy miếng \(2\) hoặc \(3\) và phải chọn miếng \(2\) vì \(8 > 1\).
• JOI lấy miếng \(3\) còn lại.

Thứ tự lấy các miếng là \(1,5,4,2,3\). JOI nhận các miếng \(1,4,3\), có tổng kích thước \(2+10+1=13\).

Trên một con đường thẳng có nhà của chủ tịch K và cựu chủ tịch M của JOI. Chú koala IOI dự định nhảy từ nhà chủ tịch K đến nhà cựu chủ tịch M.

Xem con đường là một trục số. Hai ngôi nhà có tọa độ lần lượt là \(K\) và \(M\). Giữa chúng có \(N\) ngôi nhà của các trợ giảng JOI; nhà của trợ giảng thứ \(i\) có tọa độ \(T_i\).

IOI xuất phát tại tọa độ \(K\) với thể lực bằng \(0\). Trong mỗi lần nhảy, IOI tiến về phía nhà ở tọa độ \(M\) một khoảng cách nguyên \(d\) thỏa mãn \(1 \le d \le D\). Mỗi lần nhảy làm thể lực giảm \(A\); thể lực được phép âm.

Nếu đáp xuống đúng vị trí nhà của một trợ giảng, IOI có thể nghỉ lại tại đó một lần. Nghỉ tại nhà của trợ giảng thứ \(i\) làm thể lực tăng \(B_i\). IOI muốn đến đúng tọa độ \(M\) với thể lực lớn nhất có thể.

Yêu cầu

Tính giá trị thể lực lớn nhất IOI có thể có khi đến nhà ở tọa độ \(M\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa năm số nguyên \(K,M,D,A,N\): tọa độ xuất phát, tọa độ đích, khoảng cách nhảy tối đa, lượng thể lực mất sau mỗi lần nhảy và số nhà trợ giảng.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(T_i,B_i\): tọa độ nhà của trợ giảng thứ \(i\) và lượng thể lực nhận được khi nghỉ tại đó.

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

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: thể lực lớn nhất có thể có khi IOI đến tọa độ \(M\).

Giới hạn

• \(1 \le D \le 1\,000\,000\,000\).
• \(1 \le A \le 1\,000\,000\,000\).
• \(1 \le N \le 100\,000\).
• \(0 \le K < T_1 < T_2 < \cdots < T_N < M \le 1\,000\,000\,000\).
• \(1 \le B_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• Thời gian: 2 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm và đáp ứng giới hạn thời gian, bộ nhớ.

• Bài toán con 1 (20 điểm): \(N \le 1\,000\).
• Bài toán con 2 (30 điểm): \(D \le 100\).
• Bài toán con 3 (50 điểm): Không có giới hạn bổ sung.

Ví dụ

0 10 4 10 2
3 10
8 5

-20

Một cách di chuyển tối ưu:

• Nhảy \(3\) đơn vị đến tọa độ \(3\), thể lực còn \(-10\).
• Nghỉ tại nhà trợ giảng thứ \(1\), thể lực trở thành \(0\).
• Nhảy \(4\) đơn vị đến tọa độ \(7\), thể lực còn \(-10\).
• Nhảy \(3\) đơn vị đến tọa độ \(10\), thể lực còn \(-20\).

3 42 9 10 8
10 5
12 9
26 7
27 2
30 8
34 6
36 8
40 10

-25

Một cách di chuyển tối ưu:

• Nhảy \(9\) đơn vị đến tọa độ \(12\), thể lực còn \(-10\).
• Nghỉ tại nhà trợ giảng thứ \(2\), thể lực trở thành \(-1\).
• Nhảy \(9\) đơn vị đến tọa độ \(21\), thể lực còn \(-11\).
• Nhảy \(9\) đơn vị đến tọa độ \(30\), thể lực còn \(-21\).
• Nghỉ tại nhà trợ giảng thứ \(5\), thể lực trở thành \(-13\).
• Nhảy \(6\) đơn vị đến tọa độ \(36\), thể lực còn \(-23\).
• Nghỉ tại nhà trợ giảng thứ \(7\), thể lực trở thành \(-15\).
• Nhảy \(6\) đơn vị đến tọa độ \(42\), thể lực còn \(-25\).

Chính phủ IOI thành lập một đội cứu hộ chuyên trách núi IOI. Một ngày nọ, đội nhận được tin báo rằng những người bị nạn đang ở một vị trí có độ cao \(X\).

Núi IOI được biểu diễn bằng một lưới có \(R\) hàng và \(C\) cột. Ô \((r,c)\) nằm ở hàng \(r\) tính từ trên xuống và cột \(c\) tính từ trái sang, với chỉ số bắt đầu từ \(1\). Mỗi ô có một độ cao cố định. Địa hình thỏa mãn các tính chất sau:

• Độ cao của các ô đôi một khác nhau.
• Mỗi độ cao là một số nguyên từ \(1\) đến \(1\,000\,000\,000\).
• Ô \((R_S,C_S)\) là đỉnh núi, tức là ô có độ cao lớn nhất.
• Hai ô kề nhau nếu chúng có chung một cạnh. Trong hai ô kề nhau, ô có khoảng cách đến đỉnh núi lớn hơn luôn có độ cao nhỏ hơn.

Khoảng cách giữa hai ô được định nghĩa bởi

Đội cứu hộ biết vị trí đỉnh núi nhưng chưa biết độ cao của bất kỳ ô nào, kể cả đỉnh. Thiết bị đo có thể cho biết độ cao của một ô được chỉ định. Có đúng một ô có độ cao \(X\), và đội cần tìm ô đó bằng nhiều nhất \(1\,000\) lần đo.

Yêu cầu

Cài đặt hàm Rescue để xác định ô có độ cao \(X\), sử dụng không quá \(1\,000\) lời gọi Measure, rồi báo vị trí bằng Pinpoint.

Giao diện cài đặt

Nộp tệp mountain.c hoặc mountain.cpp, có chỉ thị

#include "grader.h"

Header grader.h khai báo đúng hai hàm do trình chấm cung cấp:

int Measure(int RM, int CM);
void Pinpoint(int RP, int CP);

Bạn phải định nghĩa hàm có chữ ký sau, không tự viết hàm main:

void Rescue(int R, int C, int RS, int CS, int X);

Trình chấm gọi Rescue đúng một lần cho mỗi bộ dữ liệu. R và C là số hàng, số cột; RS và CS là hàng, cột của đỉnh núi; X là độ cao cần tìm. Hàm có kiểu trả về void; kết quả được báo bằng lời gọi Pinpoint.

Trong khi thực hiện Rescue, bạn được gọi:

• Measure(RM, CM): Đo ô ở hàng RM, cột CM, với \(1 \le RM \le R\) và \(1 \le CM \le C\). Hàm trả về độ cao của ô đó dưới dạng int. Mỗi lời gọi hợp lệ được tính là một lần đo, kể cả khi đo lại một ô. Tổng số lần gọi không được vượt quá \(1\,000\).
• Pinpoint(RP, CP): Báo rằng người bị nạn ở ô hàng RP, cột CP, với \(1 \le RP \le R\) và \(1 \le CP \le C\). Phải gọi hàm này đúng một lần. Hàm không trả về giá trị; trình chấm kiểm tra đáp án rồi kết thúc chương trình ngay trong lời gọi này.

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

Với Measure, trình chấm kiểm tra tọa độ trước khi kiểm tra giới hạn số lần đo. Nếu Pinpoint chỉ đúng ô có độ cao \(X\), đáp án được chấp nhận và chương trình kết thúc.

Dữ liệu vào

Mã dự thi nhận dữ liệu qua các tham số của Rescue và các giá trị trả về từ Measure. Ma trận độ cao được giữ trong trình chấm; mã dự thi không đọc ma trận từ đầu vào chuẩn.

Để thử chương trình, chạy grader mẫu bằng đầu vào chuẩn có định dạng sau:

• Dòng đầu tiên chứa năm số nguyên \(R,C,R_S,C_S,X\), phân cách bằng dấu cách.
• Trong \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(C\) số nguyên; số thứ \(j\) là độ cao ô \((i,j)\).

Grader mẫu đọc toàn bộ dữ liệu này, đóng luồng đầu vào, đặt bộ đếm số lần đo về \(0\), rồi gọi Rescue(R, C, RS, CS, X).

Dữ liệu ra

Mã dự thi báo kết quả duy nhất qua Pinpoint(RP, CP); không in tọa độ ra đầu ra chuẩn.

Grader mẫu ghi một dòng ra đầu ra chuẩn: Accepted nếu đáp án đúng, hoặc một trong các thông báo Wrong Answer [1] đến Wrong Answer [5] trong bảng trên. Với đáp án sai vị trí, dòng được in chính xác là Wrong Answer [4]. Grader mẫu kết thúc với mã thoát \(0\) khi chấp nhận, hoặc mã thoát bằng số lỗi khi chấm sai.

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

Biên dịch cùng grader.c hoặc grader.cpp và đặt grader.h trong thư mục biên dịch:

gcc -O2 -lm grader.c mountain.c -o grader

hoặc

g++ -O2 grader.cpp mountain.cpp -o grader

Chạy ./grader, cung cấp dữ liệu cho grader qua đầu vào chuẩn và nhận kết quả của grader qua đầu ra chuẩn. Trình chấm dùng khi chấm bài có thể khác grader mẫu nhưng tuân theo giao diện và giới hạn của bài.

Giới hạn

• \(1 \le R,C \le 200\).
• \(1 \le R_S \le R\) và \(1 \le C_S \le C\).
• \(1 \le X \le 1\,000\,000\,000\).
• Độ cao của mọi ô nằm trong đoạn từ \(1\) đến \(1\,000\,000\,000\) và thỏa mãn các tính chất địa hình đã nêu.
• Có một ô có độ cao \(X\).
• Được gọi Measure nhiều nhất \(1\,000\) lần trong mỗi bộ dữ liệu.
• Thời gian: 1 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình tìm đúng vị trí trong tất cả bộ dữ liệu của nhóm, tuân thủ giao diện, giới hạn số lần đo, thời gian và bộ nhớ.

• Bài toán con 1 (20 điểm): \(R \le 50\) và \(C \le 50\).
• Bài toán con 2 (80 điểm): Không có giới hạn bổ sung.

Ví dụ tương tác

Grader mẫu nhận dữ liệu sau từ đầu vào chuẩn:

5 5 3 3 76
14 59 84 62 28
15 73 92 76 35
68 97 100 89 75
58 67 86 79 55
17 25 71 10 5

Grader gọi Rescue(5, 5, 3, 3, 76). Một chuỗi lời gọi hợp lệ trong hàm này là:

Chuỗi lời gọi trên minh họa giao diện tương tác và không quy định chiến lược phải sử dụng.