Hướng dẫn giải của [200 đề thầy Đức] Bài 79: Giảm về 0
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
Với hai số ~a, b~, mỗi thao tác chọn ~x > 0~ rồi trừ ~x~ và ~2x~ theo một trong hai cách. Hỏi có thể đưa cả ~a, b~ về 0 không.
Sub 1: Thử số thao tác kiểu 1 — ~O(a)~, dùng khi ~a, b \le 10^6~
Gọi ~t~ là tổng ~x~ của thao tác kiểu 1 (trừ ~x~ ở ~a~, ~2x~ ở ~b~), ~s~ là tổng ~x~ của kiểu 2. Khi đó ~a = t + 2s~ và ~b = 2t + s~. Thử mọi ~t~ từ 0 đến ~a~, kiểm tra ~a - t~ chia hết cho 2 rồi xem ~2t + (a-t)/2~ có bằng ~b~ không.
Nếu chỉ nộp sub này: đúng 3/21 test.
Sub 2: Công thức — ~O(1)~, dùng khi mọi trường hợp còn lại
Giải hệ ~t = (2b - a)/3~, ~s = (2a - b)/3~. Đáp án YES khi ~a + b~ chia hết cho 3 và cả hai giá trị không âm (~2b \ge a~, ~2a \ge b~).
Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc ~T~ rồi từng cặp ~a, b~. Nếu ~a, b \le 10^6~ thì gọi sub1, ngược lại gọi sub2. Mỗi thao tác chỉ làm thay đổi tổng theo quy luật cố định nên điều kiện trên là đủ.
#include <bits/stdc++.h>
using namespace std;
long long a, b;
// Moi thao tac kieu 1 (a-x, b-2x) va kieu 2 (a-2x, b-x).
// Goi t = tong x cua kieu 1, s = tong x cua kieu 2 (t, s >= 0, tong cac x duong nen moi gia tri nguyen >= 0 deu dat duoc).
// Khi do a = t + 2s, b = 2t + s. Dat duoc (0,0) khi tim duoc t, s nguyen khong am nhu vay.
// Sub 1: vet can. Thu moi t = 0..a, suy ra s = (a - t) / 2 (can chia het), roi kiem tra 2t + s = b.
// O(a), dung khi a, b <= 10^6.
void sub1() {
for (long long t = 0; t <= a; t++) {
long long rest = a - t;
if (rest % 2 != 0) continue;
long long s = rest / 2;
if (2 * t + s == b) {
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
// Sub 2: cong thuc. Giai he: t = (2b - a) / 3, s = (2a - b) / 3.
// Can chia het cho 3 (tuong duong (a+b) chia het cho 3) va ca hai khong am. O(1).
void sub2() {
bool ok = ((a + b) % 3 == 0) && (2 * b >= a) && (2 * a >= b);
cout << (ok ? "YES" : "NO") << "\n";
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> a >> b;
if (a <= 1000000 && b <= 1000000) sub1();
else sub2();
}
return 0;
}
Bình luận