Hướng dẫn giải của [VT Thiếu nhi] BÀI 19: MAXTICH
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
Cho các số nguyên dương n. Tìm hai số tự nhiên u, v sao cho u + v = n và tích u * v lớn nhất. In ra tích u * v cho mỗi bộ dữ liệu. Đọc từ file MAXTICH.INP và ghi ra file MAXTICH.OUT.
Cách làm
Với tổng u + v cố định, tích u * v lớn nhất khi hai số gần bằng nhau nhất. Vì vậy chọn u = n chia 2 (lấy phần nguyên) và v = n - u.
Bẫy: n có thể tới 10^9 nên tích lên tới khoảng 2.5 * 10^17, phải dùng long long.
#include <bits/stdc++.h>
using namespace std;
int main() {
// Đọc từ file MAXTICH.INP, ghi ra file MAXTICH.OUT
freopen("MAXTICH.INP", "r", stdin);
freopen("MAXTICH.OUT", "w", stdout);
int t;
cin >> t;
// Với mỗi bộ dữ liệu
for (int i = 1; i <= t; i++) {
long long n;
cin >> n;
// Tích u*v lớn nhất khi u và v gần bằng nhau nhất
long long u = n / 2;
long long v = n - u;
// Nhớ dùng long long vì tích có thể lên tới khoảng 2.5 * 10^17
cout << u * v << "\n";
}
return 0;
}
Bình luận