結果

問題 No.3448 ABBBBBBBBC
コンテスト
ユーザー V_Melville
提出日時 2026-02-20 21:42:11
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 3,196 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,934 ms
コンパイル使用メモリ 341,300 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-02-20 21:42:35
合計ジャッジ時間 4,919 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll count_with_prefix(const string &p, ll N) {
    int m = (int)p.size();
    if (m == 0) return 0;
    if (p[0] == '0') return 0; 
    if (m == 1) {
        return 72LL * N;
    }
    char a = p[0], b = p[1];
    if (b == a) return 0;
    int k = 1;
    for (int i = 2; i <= m; ++i) {
        if (p[i-1] == b) k = i;
        else break;
    }
    int tmin = max(1, m - 2);
    int tmax;
    if (k < m) {
        tmax = min<ll>(N, k - 1);
    } else {
        tmax = (int)min<ll>(N, (ll)N);
    }
    if (tmax < tmin) return 0;
    ll total_t = (ll)tmax - (ll)tmin + 1;
    ll res = 0;
    int special_t = m - 2;
    if (special_t >= tmin && special_t <= tmax) {
        char c = p[m-1];
        if (c != a && c != b) res += 1;
        res += 8LL * (total_t - 1);
    } else {
        res += 8LL * total_t;
    }
    return res;
}

bool is_complete_good(const string &p, ll N) {
    int m = (int)p.size();
    if (m < 3) return false;
    if (m > N + 2) return false;
    if (p[0] == '0') return false;
    char a = p[0];
    char b = p[1];
    if (b == a) return false;
    for (int i = 2; i <= m-1; ++i) {
        if (p[i-1] != b) return false;
    }
    char c = p[m-1];
    if (c == a || c == b) return false;
    return true;
}

void solve() {
    ll N, K;
    cin >> N >> K;
    string pref = "";
    char chosen_a = '1';
    ll remK = K;
    for (char d = '1'; d <= '9'; ++d) {
        string s(1, d);
        ll cnt = count_with_prefix(s, N);
        if (remK > cnt) {
            remK -= cnt;
        } else {
            chosen_a = d;
            pref = s;
            break;
        }
    }
    char chosen_b = '0';
    for (char d = '0'; d <= '9'; ++d) {
        if (d == chosen_a) continue;
        string s = pref + d;
        ll cnt = count_with_prefix(s, N);
        if (remK > cnt) {
            remK -= cnt;
        } else {
            chosen_b = d;
            pref = s;
            break;
        }
    }
    vector<int> small_digits, large_digits;
    for (int dig = 0; dig <= 9; ++dig) {
        char ch = char('0' + dig);
        if (ch == chosen_a || ch == chosen_b) continue;
        if (ch < chosen_b) small_digits.push_back(dig);
        else if (ch > chosen_b) large_digits.push_back(dig);
    }
    ll s_small = (ll)small_digits.size();
    ll s_large = (ll)large_digits.size();
    ll total_small = s_small * N;
    ll t = -1;
    int c_digit = -1;
    if (remK <= total_small) {
        ll idx0 = remK - 1;
        ll depth0 = idx0 / s_small; 
        t = depth0 + 1;
        ll idx_in_block = idx0 % s_small;
        c_digit = small_digits[(size_t)idx_in_block];
    } else {
        ll K2 = remK - total_small; 
        ll idx0 = K2 - 1;
        ll depth_block = idx0 / s_large; 
        ll r = N - depth_block;
        t = r;
        ll idx_in_block = idx0 % s_large;
        c_digit = large_digits[(size_t)idx_in_block];
    }
    ll L = t + 2;
    cout << L << ' ' << (chosen_a - '0') << ' ' << (chosen_b - '0') << ' ' << c_digit << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) solve(); 
    
    return 0;
}
0