Hướng dẫn giải của [200 đề thầy Đức] Bài 85: Trò chơi ăn kẹo
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
Trọng tài thực hiện $n$ hành động. Hành động đầu tiên luôn là đặt kẹo. Các lần đặt kẹo sau đó luôn có số kẹo tăng thêm 1 so với lần đặt trước, nên lần đặt thứ $t$ đặt đúng $t$ viên. Các hành động còn lại là lấy ra đúng 1 viên. Cho $n$ và số kẹo còn lại $k$, cần tìm số kẹo đã lấy ra.
Sub 1: Vét cạn — ~O(n)~, dùng khi ~n \le 10^4~
Gọi $p$ là số lần đặt kẹo. Tổng kẹo đã đặt là $1 + 2 + \dots + p = \dfrac{p(p+1)}{2}$, và số lần lấy ra là $n - p$. Từ điều kiện còn lại $k$ ta có $\dfrac{p(p+1)}{2} - (n-p) = k$, tức là $\dfrac{p(p+3)}{2} = n + k$. Thử mọi $p$ từ $1$ đến $n$ và lấy đáp án $n - p$.
Kết quả chạy riêng sub này: đúng 53/53 test.
Sub 2: Tìm nhị phân — ~O(\log n)~
Hàm $\dfrac{p(p+3)}{2}$ tăng theo $p$ nên $p$ là duy nhất và có thể tìm bằng tìm nhị phân trên đoạn $[1, n]$. Đáp án là $n - p$.
Bẫy cần chú ý: $n + k$ có thể đến $2 \cdot 10^9$, còn $p(p+3)/2$ với $p$ đến $10^9$ cần long long.
Chương trình hoàn chỉnh
Chương trình đọc $n, k$. Nếu $n \le 10^4$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi, sub1 vẫn ăn điểm 60% số test nhỏ nếu chưa làm được sub2.
#include <bits/stdc++.h>
using namespace std;
long long n, k;
// Nhận xét: trọng tài đặt kẹo p lần (p >= 1, lần đầu luôn là đặt, các lần đặt có số kẹo 1, 2, ..., p).
// Tổng kẹo đã đặt = p(p+1)/2. Số lần ăn = n - p. Số kẹo còn lại k = p(p+1)/2 - (n - p).
// Suy ra p(p+3)/2 = n + k. Hàm p(p+3)/2 tăng theo p nên p xác định duy nhất.
// Đáp án (số kẹo đã lấy ra) = n - p.
// Sub 1: vét cạn — thử mọi p từ 1 đến n, tìm p thỏa p(p+3)/2 = n + k.
// Dùng khi n <= 10^4
void sub1() {
for (long long p = 1; p <= n; p++)
if (p * (p + 3) / 2 == n + k) {
cout << n - p << "\n";
return;
}
}
// Sub 2: tìm p bằng tìm nhị phân (vì p(p+3)/2 tăng theo p), O(log n)
void sub2() {
long long lo = 1, hi = n;
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (mid * (mid + 3) / 2 >= n + k) hi = mid;
else lo = mid + 1;
}
cout << n - lo << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
if (n <= 10000) sub1(); // n nhỏ: vét cạn
else sub2(); // n lớn: tìm nhị phân
return 0;
}
Bình luận