Hướng dẫn giải của [TKNP] MINK
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
Bảng có ô (i, j) = i \cdot j với 1 \le i \le N, 1 \le j \le M. Cần tìm số nhỏ thứ K trong toàn bảng.
Ý chính: với một giá trị v, đếm số ô có giá trị \le v là \sum_{i=1}^{N} \min(M, \lfloor v / i \rfloor). Hàm đếm này tăng theo v, nên đáp án là giá trị v nhỏ nhất sao cho số ô \le v đạt ít nhất K. Tìm v bằng nhị phân trên đoạn [1, N \cdot M].
Sub 1: Vét cạn — ~O(NM \log(NM))~, dùng khi N, M \le 1000
Tạo đủ N \cdot M giá trị, sắp xếp, lấy phần tử thứ K. Nếu chỉ nộp sub này: đúng 6/20 test.
Sub 2: Nhị phân + đếm theo hàng — ~O(N \log(NM))~, dùng khi N \le 10^6
Nhị phân trên v, mỗi lần đếm bằng công thức \sum_{i=1}^{N} \min(M, \lfloor v / i \rfloor). Nếu chỉ nộp sub này: đúng 8/20 test (các test có N lớn nhưng M nhỏ chạy quá giờ).
Sub 3 (đầy đủ): Đổi chiều cho nhỏ — ~O(\min(N, M) \log(NM))~
Bảng là đối xứng (i \cdot j = j \cdot i) nên có thể coi số hàng là min(N, M) \le 10^6 và số cột là max(N, M). Công thức đếm vẫn đúng, còn thời gian chỉ phụ thuộc vào cạnh nhỏ hơn.
Bẫy: N \cdot M có thể tới 10^{12}, dùng long long cho mọi biến liên quan.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc N, M, K. Nếu N, M \le 1000 gọi sub1; nếu N \le 10^6 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, K; // bang N hang, M cot; can so nho thu K
// So o trong bang co gia tri <= v, bang cach duyet cac hang i = 1..rows:
// hang i co cac gia tri i*j voi j = 1..cols, so gia tri <= v la min(cols, v / i).
long long countLE(long long v, long long rows, long long cols) {
long long c = 0;
for (long long i = 1; i <= rows; i++) c += min(cols, v / i);
return c;
}
// Sub 1: vet can - tao het N*M gia tri, sap xep, lay phan tu thu K. Dung khi N, M <= 1000.
void sub1() {
vector<long long> v;
v.reserve(N * M);
for (long long i = 1; i <= N; i++)
for (long long j = 1; j <= M; j++) v.push_back(i * j);
sort(v.begin(), v.end());
cout << v[K - 1] << "\n";
}
// Sub 2: tim nhi phan gia tri v nho nhat co countLE(v) >= K, moi lan dem duyet N hang. Dung khi N <= 10^6.
void sub2() {
long long lo = 1, hi = N * M;
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (countLE(mid, N, M) >= K) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
}
// Sub 3: day du - bang doi xung (i*j = j*i) nen duyet theo chieu nho hon (min(N, M) <= 10^6).
void sub3() {
long long rows = min(N, M), cols = max(N, M);
long long lo = 1, hi = N * M;
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (countLE(mid, rows, cols) >= K) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
}
int main() {
freopen("MINK.inp", "r", stdin);
freopen("MINK.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M >> K;
if (N <= 1000 && M <= 1000) sub1();
else if (N <= 1000000) sub2();
else sub3();
return 0;
}
Bình luận