Hướng dẫn giải của [200 đề thầy Đức] Bài 25: Sao chép ảnh
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
Ban đầu có 1 ảnh màu và 0 ảnh đen trắng. Sao ảnh màu: +1 màu và +1 đen trắng. Sao ảnh đen trắng: +2 đen trắng (cần có ít nhất 1 ảnh đen trắng). Số ảnh màu chỉ tăng khi sao ảnh màu nên cần Y - 1 lần sao ảnh màu, tạo ra Y - 1 ảnh đen trắng; sau đó sao đen trắng t lần, mỗi lần thêm 2 ảnh, nên X = (Y - 1) + 2t.
Sub 1: Vét cạn số lần sao đen trắng — ~O(X)~
Thử mọi t = 0, 1, ... với 2t \le X, kiểm tra (Y - 1) + 2t = X. Lưu ý nếu Y = 1 thì chưa có ảnh đen trắng nên t phải bằng 0. Đạt 52/52 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long X, Y;
cin >> X >> Y;
bool ok = false;
// Ban đầu có 1 ảnh màu và 0 ảnh đen trắng. Thao tác 1 (sao ảnh màu): +1 màu, +1 đen trắng.
// Thao tác 2 (sao ảnh đen trắng): +2 đen trắng, cần có ít nhất 1 ảnh đen trắng.
if (Y >= 1) {
long long a = Y - 1; // số lần sao ảnh màu (mỗi lần tạo đúng 1 ảnh màu)
// Vét cạn: thử mọi số lần t sao ảnh đen trắng
for (long long t = 0; 2 * t <= X; t++) {
if (t > 0 && a == 0) break; // chưa có ảnh đen trắng nào để sao
if (a + 2 * t == X) { // đúng X ảnh đen trắng
ok = true;
break;
}
}
}
cout << (ok ? "Yes" : "No") << "\n";
return 0;
}
Sub 2: Công thức — ~O(1)~
- Y = 0: không thể (luôn có ảnh gốc) nên in No.
- Y = 1: chỉ làm được khi X = 0.
- Y \ge 2: cần X \ge Y - 1 và X - (Y - 1) là số chẵn.
Đạt 52/52 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long X, Y;
cin >> X >> Y;
bool ok;
if (Y < 1) {
ok = false; // luôn có ít nhất ảnh gốc
} else if (Y == 1) {
ok = (X == 0); // không sao ảnh màu thì không có ảnh đen trắng nào
} else {
// Sao ảnh màu Y-1 lần tạo ra Y-1 ảnh đen trắng; sau đó mỗi lần sao đen trắng thêm 2 ảnh
long long a = Y - 1;
ok = (X >= a) && ((X - a) % 2 == 0);
}
cout << (ok ? "Yes" : "No") << "\n";
return 0;
}
Bình luận