Hướng dẫn giải của [VTT Q4 Contest 11] Bài 4: Qua sông [RIVER]
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Có ~n + 1~ hòn đá, khoảng cách giữa hòn ~i~ và ~i + 1~ là ~d_i = 1 + (i^2 \bmod M)~. Cần đi từ hòn ~0~ đến hòn ~n~ trong không quá ~j~ bước nhảy (được nhảy qua nhiều hòn), tìm độ dài bước nhảy lớn nhất nhỏ nhất. Tổng khoảng cách có thể tới ~10^{15}~ nên dùng ~long long~.
Sub 1: ~j = M = 1~
Mọi ~d_i = 1~ và chỉ có đúng một bước nhảy nên bước đó dài ~n~. Đáp án là ~n~. Nếu chỉ nộp sub này: đúng 5/20 test.
Sub 2: ~j = n~ hoặc ~M = 1~
Khi ~j = n~ có thể nhảy từng hòn một, và mỗi bước nhảy buộc phải vượt ít nhất một khoảng liên tiếp, nên đáp án là ~\max d_i~. Khi ~M = 1~ mọi khoảng cách bằng 1, ~j~ bước chia ~n~ đơn vị nên đáp án là ~\lceil n / j \rceil~. Nếu chỉ nộp sub này: đúng 9/20 test.
Sub 3: Chặt nhị phân đáp án — ~O(n \log (\sum d))~
Nếu tầm nhảy ~L~ đi được thì mọi ~L' > L~ cũng đi được, nên chặt nhị phân ~L~. Để kiểm tra một ~L~, tính vị trí các hòn đá (tổng tiền tố của ~d~) rồi nhảy tham lam: mỗi bước nhảy đến hòn xa nhất có thể; nếu không nhảy được (~L < d~ ở chỗ đó) hoặc số bước vượt ~j~ thì ~L~ không đủ. Mỗi lần kiểm tra duyệt các hòn đá một lần, ~O(n)~. Đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc dữ liệu, tính vị trí các hòn đá rồi chọn: ~j = M = 1~ gọi sub1, ~j = n~ hoặc ~M = 1~ gọi sub2, còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long n, M, J;
long long pos[1000005]; // pos[i] = vị trí hòn đá i
// Sub 1: j = M = 1 — mọi khoảng cách đều bằng 1, chỉ có đúng 1 bước nhảy: L = n
void sub1() { cout << n << "\n"; }
// Sub 2: j = n hoặc M = 1
// j = n: nhảy từng hòn một, L = khoảng cách lớn nhất. M = 1: mọi khoảng cách bằng 1, L = ceil(n/j).
void sub2() {
if (J == n) {
long long mx = 0;
for (long long i = 0; i < n; i++) mx = max(mx, 1 + (i * i) % M);
cout << mx << "\n";
} else cout << (n + J - 1) / J << "\n";
}
// Kiểm tra tầm nhảy L: nhảy tham lam xa nhất có thể, đếm số bước
bool ok(long long L) {
long long cur = 0, steps = 0;
while (cur < n) {
long long nx = cur;
while (nx < n && pos[nx + 1] - pos[cur] <= L) nx++;
if (nx == cur) return false; // không nhảy nổi
cur = nx;
if (++steps > J) return false;
}
return true;
}
// Sub 3: chặt nhị phân trên L
void sub3() {
long long lo = 1, hi = pos[n];
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (ok(mid)) hi = mid; else lo = mid + 1;
}
cout << lo << "\n";
}
int main() {
freopen("RIVER.INP", "r", stdin);
freopen("RIVER.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> M >> J;
pos[0] = 0;
for (long long i = 0; i < n; i++) pos[i + 1] = pos[i] + 1 + (i * i) % M;
if (J == 1 && M == 1) sub1();
else if (J == n || M == 1) sub2();
else sub3();
}
Bình luận