Hướng dẫn giải của [2526 VTT THPT KS2] Bài 1: Đường cắt xoắn ốc [SPIRCUT]
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Đường cắt xoắn ốc gồm các đoạn xen kẽ: lên, sang phải, xuống, sang trái, ... Đoạn lên thứ k dài m - k, đoạn ngang thứ k dài n - 1 - k. Cắt dừng khi đoạn tiếp theo có độ dài không dương, lúc đó đoạn cắt tiếp sẽ làm mảnh giấy bị rời ra. Ví dụ 5 \times 6: 4 + 4 + 3 + 3 + 2 + 2 + 1 + 1 = 20.
Sub 1: Mô phỏng từng đoạn — ~O(\min(m, n))~, dùng khi ~\min(m, n) \le 2000~
Lặp k = 1, 2, ... và cộng dần độ dài đoạn lên và đoạn ngang, dừng khi gặp đoạn có độ dài không dương. Đúng 41/41 test.
Sub 2: Công thức đóng — ~O(1)~
Đặt S(A, K) = tổng (A - k) với k = 1..K = K \cdot A - K(K+1)/2. Nếu m \le n - 1 thì đáp án là S(m, m-1) + S(n-1, m-1). Nếu m \ge n thì đáp án là S(m, n-1) + S(n-1, n-2). Đúng 41/41 test.
Chương trình hoàn chỉnh
Hàm main đọc m, n. Nếu \min(m, n) \le 2000 gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
long long m, n;
// Đường cắt gồm các đoạn xen kẽ: lên, phải, xuống, trái, ... Đoạn lên thứ k dài m - k,
// đoạn ngang thứ k dài n - 1 - k. Cắt dừng khi đoạn tiếp theo có độ dài <= 0
// (đoạn tiếp theo sẽ cắt rời mảnh giấy).
// Ví dụ 5 x 6: 4+4+3+3+2+2+1+1 = 20.
// Sub 1: mô phỏng từng đoạn, O(min(m, n)). Dùng khi min(m, n) <= 2000.
void sub1() {
long long total = 0;
for (long long k = 1;; k++) {
long long up = m - k;
if (up <= 0) break;
total += up;
long long across = n - 1 - k;
if (across <= 0) break;
total += across;
}
cout << total << "\n";
}
// Sub 2: công thức đóng. S(A, K) = tổng (A - k) với k = 1..K = K*A - K(K+1)/2.
long long S(long long A, long long K) {
if (K <= 0) return 0;
return K * A - K * (K + 1) / 2;
}
void sub2() {
long long total;
if (m <= n - 1) {
// dừng do đoạn lên thứ m (dài 0); các đoạn lên k = 1..m-1 và ngang k = 1..m-1
total = S(m, m - 1) + S(n - 1, m - 1);
} else {
// m >= n: dừng do đoạn ngang thứ n-1 (dài 0); lên k = 1..n-1 và ngang k = 1..n-2
total = S(m, n - 1) + S(n - 1, n - 2);
}
cout << total << "\n";
}
int main() {
freopen("SPIRCUT.inp", "r", stdin);
freopen("SPIRCUT.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
if (min(m, n) <= 2000) sub1();
else sub2();
return 0;
}
Bình luận