Hướng dẫn giải của Mua bánh rán (đề HSG 12 Phú Thọ 2024-2025)
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
Tổng tiền mua n cái bánh là k·(1+2+...+n) = k·n(n+1)/2. Mèo Ú cần vay max(0, tổng − x). Giá trị tối đa khoảng 5·10^20 nên cần số nguyên lớn (__int128).
Sub 1: Vét cạn (cộng dồn từng cái) — ~O(n)~
Cộng dồn giá của từng cái bánh i·k với i = 1..n, rồi trừ x. Đạt 20/20 test (chậm với n lớn nhưng vẫn đủ thời gian trong bộ test này).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
long long n, k, x;
cin >> n >> k >> x;
// Vét cạn: cộng dồn giá của từng cái bánh i*k, i = 1..n
// Tổng có thể rất lớn nên dùng __int128
__int128 sum = 0;
for (long long i = 1; i <= n; i++) {
sum += (__int128)i * k;
}
__int128 ans = sum - x;
if (ans < 0) ans = 0;
cout << (long long)ans << "\n";
return 0;
}
Sub 2: Dùng công thức tổng cấp số cộng — ~O(1)~
Tổng = k·n(n+1)/2. Vì n(n+1)·k có thể lên tới ~10^21 nên tính bằng __int128 để không tràn số. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
long long n, k, x;
cin >> n >> k >> x;
// Tổng = k * (1 + 2 + ... + n) = k * n * (n+1) / 2
// n*(n+1)*k có thể lên tới ~1e21 nên dùng __int128 để tránh tràn số
__int128 total = (__int128)k * n * (n + 1) / 2;
__int128 ans = total - x;
if (ans < 0) ans = 0;
cout << (long long)ans << "\n";
return 0;
}
Bình luận