Hướng dẫn giải của [VTT Q4 Contest 08] Bài 1: Pytago [PYTAGO]
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 xâu chữ số ~X~ (tối đa 24 chữ số) được ghép từ ba số theo một thứ tự nào đó. Cần tìm mọi cách cắt ~X~ thành ba đoạn liên tiếp mà ba số tạo thành bộ Pytago, rồi lấy số lớn nhất trong ba số, tối đa hóa trên mọi cách cắt.
Sub 1: Vét cạn mọi cách cắt — ~O(L^2)~, ~L \le 24~
Vì ghép theo hoán vị bất kỳ nên chỉ cần xét cách cắt xâu ~X~ thành ba đoạn liên tiếp ~(a, b, c)~; thứ tự của chúng không quan trọng vì ta sắp xếp lại ba số. Có không quá ~\binom{23}{2}~ cách cắt. Mỗi đoạn không được bắt đầu bằng chữ số 0 (trừ khi chỉ có một chữ số). Với mỗi cách cắt, sắp xếp ba số ~v_0 \le v_1 \le v_2~ và kiểm tra ~v_0^2 + v_1^2 = v_2^2~.
Bẫy: bình phương số lớn có thể vượt ~64~ bit, dùng __int128. Cạnh huyền ~v_2~ luôn nhỏ hơn ~\sqrt{2}~ lần cạnh lớn kia nên không quá 13 chữ số, do đó chỉ cần xét đoạn tối đa 18 chữ số là bình phương vẫn nằm trong __int128. Nếu chỉ nộp sub này: đúng 20/20 test.
Bài quá nhỏ (chỉ ~O(L^2)~ cách cắt, không có hướng vét cạn hợp lý hơn) nên chỉ có một sub.
Chương trình hoàn chỉnh
main đọc xâu ~X~ rồi gọi sub1.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef __int128 LL;
string s;
// Chuyển xâu con s[l..r) thành số (đã đảm bảo tối đa 18 chữ số)
ull val(int l, int r) {
ull v = 0;
for (int i = l; i < r; i++) v = v * 10 + (s[i] - '0');
return v;
}
// Sub 1: duyệt mọi cách cắt X thành 3 đoạn, kiểm tra bộ ba Pytago
void sub1() {
int L = s.size();
ull best = 0;
for (int i = 1; i < L; i++)
for (int j = i + 1; j < L; j++) {
int len[3] = {i, j - i, L - j};
int st[3] = {0, i, j};
bool ok = true;
for (int t = 0; t < 3; t++)
if (len[t] > 18 || (len[t] > 1 && s[st[t]] == '0')) ok = false; // không có số 0 đứng đầu
if (!ok) continue;
ull a = val(0, i), b = val(i, j), c = val(j, L);
ull v[3] = {a, b, c};
sort(v, v + 3);
// v[2] là cạnh lớn nhất: kiểm tra v0^2 + v1^2 = v2^2 bằng __int128
if ((LL)v[0] * v[0] + (LL)v[1] * v[1] == (LL)v[2] * v[2]) best = max(best, v[2]);
}
cout << best << "\n";
}
int main() {
freopen("PYTAGO.INP", "r", stdin);
freopen("PYTAGO.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> s;
// Bài chỉ có O(L^2) cách cắt (L <= 24) nên chỉ cần 1 sub vét cạn
sub1();
}
Bình luận