Hướng dẫn giải của Đèn chiếu sáng (Đề tuyển sinh 10 Chuyên Quảng Trị 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
Cho lưới n x m (n, m, k ≤ 10^9), mỗi bóng đèn chiếu một hình vuông k x k. Tìm số bóng ít nhất để chiếu sáng toàn bộ sân.
Sub 1: Vét cạn, đặt từng bóng theo lưới — ~O((n/k)(m/k))~
Đặt bóng theo lưới các bước k trên cả hai chiều, đếm từng bóng một. Đúng nhưng với k nhỏ số bóng rất lớn nên chỉ đạt một phần test.
Kết quả chấm: 7/10 (SUB ok 7/10, TLE 3, WA 0)
#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, m, k;
cin >> n >> m >> k;
long long cnt = 0;
// Vet can: dat tung bong den theo luoi buoc k, dem tung bong mot
for (long long x = 0; x < n; x += k)
for (long long y = 0; y < m; y += k)
cnt++;
cout << cnt << "\n";
return 0;
}
Sub 2: Công thức ceil — ~O(1)~
Theo chiều n cần ceil(n / k) bóng, theo chiều m cần ceil(m / k) bóng. Tích hai số là đáp án. Tính ceil bằng (n + k - 1) / k.
Bẫy: tích có thể tới 10^18 nên dùng long long.
Kết quả chấm: 10/10
#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, m, k;
cin >> n >> m >> k;
// Theo mot chieu can ceil(n / k) bong, chieu kia ceil(m / k) bong; tich la so bong it nhat
long long hang = (n + k - 1) / k;
long long cot = (m + k - 1) / k;
cout << hang * cot << "\n";
return 0;
}
Bình luận