Hướng dẫn giải của [200 đề thầy Đức] Bài 113: Xếp kim tự tháp
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 thứ i (từ trên xuống) cần 1 + 2 + ... + i khối. Kim tự tháp cao h cần tổng các tầng từ 1 đến h, nên ta tìm h lớn nhất sao cho tổng này không vượt quá N.
Sub 1: Tính lại tổng cho từng chiều cao — ~O(H^3)~
Với mỗi h tăng dần, tính tổng số khối bằng hai vòng lặp lồng nhau (cộng lại từng tầng). Dừng khi tổng vượt N. Đạt 15/15 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
int ans = 0;
// Vet can: thu chieu cao h tang dan, tinh tong so khoi bang cach cong tung tang
// Tang thu i (tu tren xuong) co 1 + 2 + ... + i khoi
for (int h = 1;; h++) {
long long total = 0;
for (int i = 1; i <= h; i++)
for (int j = 1; j <= i; j++)
total += j;
if (total > N) break;
ans = h;
}
cout << ans << "\n";
return 0;
}
Sub 2: Cộng dồn từng tầng — ~O(H)~
Giữ tổng số khối và số khối của tầng hiện tại (tầng i có tang += i). Nếu tổng cộng thêm tầng này vượt N thì dừng, ngược lại cộng vào và tăng chiều cao. Đạt 15/15 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long N;
cin >> N;
long long tong = 0; // tong so khoi cua cac tang da xep
long long tang = 0; // so khoi cua tang hien tai: 1 + 2 + ... + i
int h = 0;
for (long long i = 1;; i++) {
tang += i; // tang thu i co tang + i khoi
if (tong + tang > N) break; // khong du khoi cho tang nay
tong += tang;
h = (int)i;
}
cout << h << "\n";
return 0;
}
Bình luận