Hướng dẫn giải của Sinh nhật (KS2)
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 biết chiếc bánh có cherry ở vị trí nào sau khi xử lý hết các bước. Mô phỏng cho thấy đáp số luôn là lũy thừa 2 lớn nhất không vượt quá n (ví dụ n = 4 cho 4, n = 5 cho 4, n = 8 cho 8).
Sub 1: Mô phỏng vét cạn - ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi k từ 2 đến n, tìm ước lớn nhất bằng cách thử mọi số rồi đổi chỗ thật hai chiếc bánh. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Sàng và theo dõi cherry - ~O(n \log \log n)~, dùng khi ~n \le 10^6~
Sàng ước nguyên tố nhỏ nhất để có ước lớn nhất ~k / spf(k)~ trong O(1). Chỉ cần theo dõi vị trí của cherry: nếu cherry ở k thì chuyển sang d, nếu ở d thì chuyển sang k. Đúng 14/20 test (các test lớn hơn miền thì quá giờ).
Sub 3: Công thức - ~O(\log n)~
Đáp số là lũy thừa 2 lớn nhất không vượt quá n. Bẫy: n lên tới ~10^{14}~ nên dùng long long. Đúng 20/20 test.
Chương trình hoàn chỉnh
Bài có file BIRTHDAY.INP và BIRTHDAY.OUT nên main dùng freopen đúng tên. Nếu ~n \le 1000~ gọi sub1, nếu ~n \le 10^6~ gọi sub2, còn lại gọi sub3.
#include <bits/stdc++.h>
using namespace std;
long long n;
// Sub 1: vet can - mo phong dung mang vi tri. Voi moi k = 2..n: tim uoc lon nhat d cua k (d < k) bang cach
// thu tat ca cac so, roi hoan doi hai chiec banh o vi tri k va d. Dung khi n <= 1000.
void sub1() {
vector<int> pos(n + 1);
for (int i = 1; i <= n; i++) pos[i] = i; // pos[p] = so hieu chiec banh dang o vi tri p
for (long long k = 2; k <= n; k++) {
long long d = 1;
for (long long x = k - 1; x >= 1; x--)
if (k % x == 0) { d = x; break; }
swap(pos[k], pos[d]);
}
for (int p = 1; p <= n; p++)
if (pos[p] == 1) { cout << p << "\n"; return; }
}
// Sub 2: sang so nguyen to nho nhat (spf) de co uoc lon nhat d = k / spf(k), chi theo doi vi tri cua cherry.
// Cherry dang o vi tri c: neu c = k thi chuyen sang d; neu c = d thi chuyen sang k. O(n). Dung khi n <= 10^6.
void sub2() {
int N = (int)n;
vector<int> spf(N + 1, 0);
for (int i = 2; i <= N; i++)
if (spf[i] == 0)
for (int j = i; j <= N; j += i)
if (spf[j] == 0) spf[j] = i;
long long c = 1; // cherry bat dau o vi tri 1
for (long long k = 2; k <= n; k++) {
long long d = k / spf[k];
if (c == k) c = d;
else if (c == d) c = k;
}
cout << c << "\n";
}
// Sub 3: cong thuc. Tu quan sat: vi tri cuoi cung cua cherry la luy thua 2 lon nhat khong vuot qua n.
// Dung cho moi n <= 10^14.
void sub3() {
long long p = 1;
while (p * 2 <= n) p *= 2;
cout << p << "\n";
}
int main() {
freopen("BIRTHDAY.INP", "r", stdin);
freopen("BIRTHDAY.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
if (n <= 1000) sub1();
else if (n <= 1000000) sub2();
else sub3();
return 0;
}
Bình luận