Có \(N\) số nguyên không âm chưa biết:

với \(A_N\le10^{18}\). Hãy tìm khoảng cách lớn nhất giữa hai số liên tiếp:

Các số \(A_i\) không được cung cấp trực tiếp. Chương trình chỉ có thể truy cập chúng qua hàm MinMax.

Yêu cầu cài đặt

Bạn phải cài đặt hàm:

long long findGap(int T, int N);

• T là số phân nhóm, bằng 1 hoặc 2.
• N là số lượng số nguyên ẩn.
• Hàm phải trả về khoảng cách lớn nhất.

Bạn có thể gọi:

void MinMax(long long s, long long t, long long *mn, long long *mx);

Sau lời gọi với \(s\le t\):

• mn nhận số nhỏ nhất trong tập \(\{A_i\mid s\le A_i\le t\}\);
• mx nhận số lớn nhất trong tập đó;
• nếu không có số nào trong đoạn \([s,t]\), cả mn và mx nhận -1.

Nếu gọi với \(s>t\), chương trình bị chấm lỗi. Bài nộp chỉ cần chứa phần cài đặt các hàm yêu cầu, không viết hàm main và không tự cài đặt MinMax. Có thể dùng:

# include "gap.h"

Ví dụ tương tác

Xét \(T=2\), \(N=4\) và dãy ẩn \(2,3,6,8\). Đáp án là \(3\). Một chuỗi lời gọi hợp lệ là:

• MinMax(1, 2, &mn, &mx), nhận mn = mx = 2;
• MinMax(3, 7, &mn, &mx), nhận mn = 3, mx = 6;
• MinMax(8, 9, &mn, &mx), nhận mn = mx = 8.

Grader mẫu trong tệp đính kèm đọc:

2 4
2 3 6 8

Nó in giá trị trả về của findGap và chi phí truy vấn. Dữ liệu này chỉ dùng để thử nghiệm; grader chính không truyền trực tiếp dãy ẩn cho lời giải.

Chấm điểm

Ngoài việc trả về đáp án đúng, tổng chi phí \(M\) của các lời gọi MinMax phải đủ nhỏ.

• Nhóm 1, 30 điểm: mỗi lời gọi cộng \(1\) vào \(M\). Nhận đủ điểm của một test nếu

• Nhóm 2, 70 điểm: nếu đoạn truy vấn chứa \(k\) số ẩn thì lời gọi đó cộng \(k+1\) vào \(M\). Điểm của một test là \(70\) nếu \(M\le3N\); nếu không, điểm test là

Điểm của mỗi nhóm là điểm nhỏ nhất trên tất cả test thuộc nhóm đó.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2016, bài Gap. Hệ thống sử dụng grader chữ ký C++ tương đương grader chính thức.