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";
    }

}