Hướng dẫn giải của [200 đề thầy Đức] Bài 19: Đi bộ
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
An đi N viên gạch với k bước, mỗi bước 1 hoặc 2 viên. Với k bước, tổng đi được là một số nguyên trong [k, 2k], nên cần k \le N \le 2k. Cần tìm k nhỏ nhất là bội của M.
Sub 1: Vét cạn theo số bước — ~O(N)~
Thử k = 1, 2, ..., N theo thứ tự, lấy k đầu tiên thỏa N \le 2k và k chia hết cho M. Nếu không có thì in -1. Đạt 35/35 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long N, M;
cin >> N >> M;
// Vét cạn: thử từng số bước k = 1, 2, ..., N
// Đi k bước với mỗi bước 1 hoặc 2 viên thì tổng N khi và chỉ khi k <= N <= 2k
for (long long k = 1; k <= N; k++) {
if (N <= 2 * k && k % M == 0) {
cout << k << "\n";
return 0;
}
}
cout << -1 << "\n";
return 0;
}
Sub 2: Làm tròn lên — ~O(1)~
Số bước ít nhất là k0 = ~\lceil N/2 \rceil~. Bội nhỏ nhất của M không nhỏ hơn k0 là ~\lceil k_0 / M \rceil \cdot M~. Nếu nó vượt quá N thì in -1. Đạt 35/35 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long N, M;
cin >> N >> M;
// Số bước ít nhất là k0 = ceil(N/2) (toàn bước 2 viên)
long long k0 = (N + 1) / 2;
// Bội của M nhỏ nhất không nhỏ hơn k0
long long k = (k0 + M - 1) / M * M;
// Số bước nhiều nhất là N (toàn bước 1 viên); nếu vượt quá thì không thực hiện được
if (k <= N) cout << k << "\n";
else cout << -1 << "\n";
return 0;
}
Bình luận