Hướng dẫn giải của Gà và chó (Đề HSG Quảng Bình 2021)
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
Gọi g là số gà, c là số chó. Ta có hai điều kiện: g + c = N (tổng số con) và 2g + 4c = K (tổng số chân chẵn). Cần tìm g, c thỏa mãn hoặc in -1 nếu không có nghiệm.
Sub 1: Vét cạn — ~O(N)~
Thử lần lượt mọi số chó c từ 0 đến N, suy ra g = N - c, rồi kiểm tra 2g + 4c = K. Gặp nghiệm đầu tiên thì in ra, nếu hết vòng lặp mà không có thì in -1.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CD.INP", "r")) { freopen("CD.INP", "r", stdin); freopen("CD.OUT", "w", stdout); }
long long n, k;
cin >> n >> k;
// Vet can: thu moi so cho c (so cho) tu 0..N, tinh so ga g = N - c,
// roi kiem tra tong so chan: 2*g + 4*c == K
for (long long c = 0; c <= n; c++) {
long long g = n - c;
if (2 * g + 4 * c == k) {
cout << g << " " << c << "\n";
return 0;
}
}
cout << -1 << "\n";
return 0;
}
Sub 2: Giải hệ phương trình — ~O(1)~
Thay g = N - c vào 2g + 4c = K ta được 2c = K - 2N, tức c = (K - 2N) / 2. Cần kiểm tra: hiệu K - 2N không âm, là số chẵn, và g = N - c không âm. Nếu thỏa mãn thì in g và c, ngược lại in -1. Dùng long long cho an toàn.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CD.INP", "r")) { freopen("CD.INP", "r", stdin); freopen("CD.OUT", "w", stdout); }
long long n, k;
cin >> n >> k;
// Goi c la so cho, g la so ga: g + c = N va 2g + 4c = K
// Suy ra 2c = K - 2N => c = (K - 2N) / 2
long long diff = k - 2 * n;
// K phai chan, c >= 0 va g = N - c >= 0
if (diff < 0 || diff % 2 != 0) {
cout << -1 << "\n";
return 0;
}
long long c = diff / 2;
long long g = n - c;
if (g < 0) {
cout << -1 << "\n";
return 0;
}
cout << g << " " << c << "\n";
return 0;
}
Bình luận