Hướng dẫn giải của Bedao Mini Contest 08 - TRIANGLE
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.
Tác giả:
Subtask 1: ~t \le 10, k \le 8~
Nhận xét: mỗi giá trị xuất hiện trong dãy không quá 2 lần, vì nếu có 3 giá trị giống nhau thì luôn dựng được 1 tam giác đều.
Nếu ~n > 2k~ thì theo định lý dirichlet luôn có ~1~ giá trị xuất hiện trong dãy ~\ge~ 3 lần ~\Rightarrow~ kết quả là
no
.Vì có tối đa 8 giá trị phân biệt và chúng xuất hiện trong dãy ko quá 2 lần, ta dễ dàng duyệt backtrack với độ phức tạp là ~\mathcal{O}(3^k)~ rồi duyệt qua mọi bộ 3 trong dãy vừa sinh để kiểm tra. Thuật toán có độ phức tạp là ~\mathcal{O}(t \times 3^k \times k^3)~.
Subtask 2:
Nhận xét : không mất tính tổng quát, giả sử bộ 3 ta đang xét là ~(a, b, c)~ và ~a \le b \le c~. Bộ 3 này không tạo thành các cạnh tam giác khi và chỉ khi ~a+b \le c~.
Xét dãy ~s[1..n]~ thoả mãn yêu cầu đề bài và có ~s[i] \le s[i+1]~, ta xây dựng ~s[1..n]~ theo thuật toán tham lam để số lớn nhất trong dãy là ~s[n]~ có giá trị tối thiểu:
- Nếu ~i > 2~ và ~s[1..i-1]~ là các số đã biết thì ~s[i]~ tối ưu để thêm vào dãy mà vẫn không thỏa mãn bất đẳng thức tam giác là ~s[i] = s[i-1]+s[i-2]~.
- Dễ thấy nếu ~i \le 2~ thì tốt nhất là đặt ~s[i] = 1~. Nói cách khác, dãy ~s[1..n]~ tối ưu gồm sẽ ~n~ phần tử đầu của dãy fibonacci, ta chỉ cần so sánh số thứ ~n~ trong dãy fibonacci với ~k~ để biết kết quả.
Dễ thấy ~s[i+2] > 2s[i]~ mà ~s[n] \le k \le 10^{18}~ nên một dãy thỏa mãn có nhiều nhất ~2\log_2(10^{18})~ phần tử. Vì vậy thuật toán cuối cùng có độ phức tạp là ~\mathcal{O}(t \times \log_2(10^{18}))~.
Code mẫu
/*#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma")*/ #include <bits/stdc++.h> #define for1(i,a,b) for (int i = a; i <= b; i++) #define for2(i,a,b) for (int i = a; i >= b; i--) #define int long long #define sz(a) (int)a.size() #define pii pair<int,int> #define pb push_back /* __builtin_popcountll(x) : Number of 1-bit __builtin_ctzll(x) : Number of trailing 0 */ const long double PI = 3.1415926535897932384626433832795; const int INF = 1000000000000000000; const int MOD = 1000000007; const int MOD2 = 1000000009; const long double EPS = 1e-6; using namespace std; int d[105]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("cf.inp", "r", stdin); // freopen("cf.out", "w", stdout); d[1] = 1; d[2] = 1; for1(i,3,100) { d[i] = d[i - 1] + d[i - 2]; } int t; cin >> t; while (t--) { int n, k, flag = 1; cin >> n >> k; for1(i,1,n) if (d[i] > k) { flag = 0; break; } if (flag) cout << "yes\n"; else cout << "no\n"; } }
Bình luận