Hướng dẫn giải của [200 đề thầy Đức] Bài 18: Số bước đi của rùa
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
Rùa đi từ (0, 0) đến (a, b) bằng s bước, mỗi bước đổi x hoặc y đúng 1. Khoảng cách Manhattan d = |a| + |b| là số bước ít nhất. Mỗi bước đổi |x| + |y| đúng 1 nên s bước đi được khi và chỉ khi s \ge d và s - d chẵn (phần thừa được triệt tiêu bằng việc đi tới rồi lùi).
Chỉ viết 1 sub vì đã là công thức O(1) đơn giản; các cách vét cạn theo lưới không khả thi với tọa độ 10^9. Đạt 40/40 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b, s;
cin >> a >> b >> s;
// Khoảng cách Manhattan từ (0,0) đến (a,b)
long long d = llabs(a) + llabs(b);
// Mỗi bước đổi tổng |x| + |y| đúng 1, nên cần s >= d và s - d chẵn
bool ok = (s >= d) && ((s - d) % 2 == 0);
cout << (ok ? "Yes" : "No") << "\n";
return 0;
}
Bình luận