Hướng dẫn giải của Văn nghệ (Đề HSG 12 Phú Thọ 2021-2022)
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
Chia n nam và m nữ thành nhiều tổ sao cho số nam và số nữ mỗi tổ bằng nhau và số tổ là lớn nhất. Đọc từ VN.INP, ghi ra VN.OUT: dòng 1 là số tổ, dòng 2 là số nam và số nữ mỗi tổ.
Sub 1: Vét cạn — ~O(min(n, m))~
Số tổ g phải là ước chung của n và m. Thử g từ min(n, m) xuống 1, g đầu tiên chia hết cả n và m là số tổ tối đa. Cách này đúng nhưng với n, m lên tới 10^9 thì chậm.
Kết quả chấm: đạt 12/12 test (SUB ok 8/12, TLE 4, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("VN.INP", "r")) {
freopen("VN.INP", "r", stdin);
freopen("VN.OUT", "w", stdout);
}
long long n, m;
cin >> n >> m;
// Vét cạn: số tổ tối đa g là ước chung lớn nhất, thử g từ min(n,m) xuống 1
long long g = 1;
for (long long d = min(n, m); d >= 1; d--) {
if (n % d == 0 && m % d == 0) {
g = d;
break;
}
}
cout << g << "\n";
cout << n / g << " " << m / g << "\n";
return 0;
}
Sub 2: Ước chung lớn nhất — ~O(log(max))~
Số tổ tối đa là UCLN(n, m). Mỗi tổ có n/g nam và m/g nữ. Dùng hàm __gcd của thư viện.
Kết quả chấm: đạt 12/12 test
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("VN.INP", "r")) {
freopen("VN.INP", "r", stdin);
freopen("VN.OUT", "w", stdout);
}
long long n, m;
cin >> n >> m;
// Số tổ tối đa = UCLN(n, m); mỗi tổ có n/g nam và m/g nữ
long long g = __gcd(n, m);
cout << g << "\n";
cout << n / g << " " << m / g << "\n";
return 0;
}
Bình luận