#1083981 (C++17) No.2868 Another String of yuusaan

• 問題: No.2868 Another String of yuusaan
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:12:58
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 7,391 bytes
• コンパイル時間: 647 ms
• コンパイル使用メモリ: 78,448 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:13:46
• 合計ジャッジ時間: 1,503 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 18

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// Use unsigned long long for N, K, and string lengths, as they can exceed 2^63.
typedef unsigned long long ull;

// Store precomputed lengths L_i. L_vals[i] will store the length of the level i yuu-string.
vector<ull> L_vals;

// Recursive function to find the k-th character of the level n yuu-string (S_n).
char recursive_solve(ull n, ull k) {
    // Base case: The first character of any S_n (n >= 1) is always 'y'.
    // This is because S_n starts with 'y' followed by expansions derived from S_{n-1}.
    if (k == 1) {
        return 'y';
    }

    // Base case: For n=1, the string is S_1 = "yuusaan".
    if (n == 1) {
        string s1 = "yuusaan";
        // k is 1-based index. Access character at k-1 (0-based index).
        // Check if k is within the valid range [1, 7] for S_1.
        if (k >= 1 && k <= 7) {
             return s1[k - 1];
        } else {
             // This state should not be reached if K is valid for S_N and logic is correct.
             // Return an error indicator? For robustness.
             return '?'; 
        }
    }

    // For n > 1, S_n is constructed based on S_{n-1} using the rule:
    // S_n = 'y' + S_{n-1} + S_{n-1} + 's' + S_{n-1} + S_{n-1} + 'n'
    // The lengths of these components are: 1, L_{n-1}, L_{n-1}, 1, L_{n-1}, L_{n-1}, 1.
    // We need the length L_{n-1}, which should be precomputed and stored in L_vals.
    // Since the reduction logic ensures N_final is relatively small, n-1 will be a valid index.
    ull len_prev = L_vals[n - 1]; 

    // Determine which block the k-th character falls into based on cumulative lengths.

    // Block 1: 'y' (length 1). Handled by the k == 1 check at the beginning.

    // Block 2: First S_{n-1} instance (length len_prev). Covers indices [2, 1 + len_prev].
    // Calculate end position of block 2.
    ull pos_block2_end = 1 + len_prev;
    if (k <= pos_block2_end) {
        // k is in this block. The character is the (k-1)-th character of S_{n-1}.
        return recursive_solve(n - 1, k - 1);
    }
       
    // Block 3: Second S_{n-1} instance (length len_prev). Covers indices [2 + len_prev, 1 + 2 * len_prev].
    // Calculate end position of block 3.
    ull pos_block3_end = 1 + 2 * len_prev;
    if (k <= pos_block3_end) {
        // k is in this block. The character is the (k - (1 + len_prev))-th character of S_{n-1}.
        // The index relative to this S_{n-1} block start is k minus the end position of block 2.
        return recursive_solve(n - 1, k - pos_block2_end);
    }
       
    // Block 4: 's' (length 1). Position: 2 + 2 * len_prev.
    // Calculate the position of 's'.
    ull pos_block4 = 2 + 2 * len_prev;
    if (k == pos_block4) {
        // k matches this position exactly. The character is 's'.
        return 's';
    }
       
    // Block 5: Third S_{n-1} instance (length len_prev). Covers indices [3 + 2 * len_prev, 2 + 3 * len_prev].
    // Calculate end position of block 5.
    ull pos_block5_end = 2 + 3 * len_prev;
    if (k <= pos_block5_end) {
        // k is in this block. The character is the (k - pos_block4)-th character of S_{n-1}.
        // Index relative to this block start is k minus the position of block 4 character ('s').
        return recursive_solve(n - 1, k - pos_block4);
    }
       
    // Block 6: Fourth S_{n-1} instance (length len_prev). Covers indices [3 + 3 * len_prev, 2 + 4 * len_prev].
    // Calculate end position of block 6.
    ull pos_block6_end = 2 + 4 * len_prev;
    if (k <= pos_block6_end) {
       // k is in this block. The character is the (k - pos_block5_end)-th character of S_{n-1}.
       // Index relative to this block start is k minus the end position of block 5.
       return recursive_solve(n - 1, k - pos_block5_end); 
    }

    // Block 7: 'n' (length 1). Position: 3 + 4 * len_prev. This is the last character of S_n.
    // If k was not found in blocks 1 through 6, it must be the final character 'n'.
    // The position check `k == 3 + 4 * len_prev` is implicitly true here given K is valid index.
    return 'n'; 
}


int main() {
    // Use faster I/O operations.
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ull N, K;
    cin >> N >> K;

    // Handle the simplest case: K=1. The first character is always 'y'.
    if (K == 1) {
        cout << 'y' << endl;
        return 0;
    }

    // Precompute lengths L_i = length of S_i.
    // L_vals[0] is unused (or dummy). L_vals[i] stores L_i.
    L_vals.push_back(0); // Dummy value for index 0.
    L_vals.push_back(7); // L_1 = 7.

    ull current_L = 7;
    int min_level_k = -1; // Tracks the smallest level idx >= 1 such that L[idx] >= K.
    // Check if L_1 itself is already >= K.
    if (current_L >= K) {
        min_level_k = 1;
    }

    // Compute L_i using the recurrence L_i = 4 * L_{i-1} + 3 for i >= 2.
    // Continue up to a level sufficient for K (e.g., level 65) or until overflow is imminent.
    // For K <= 10^15, level ~26 is sufficient. Level 65 is generous.
    for (int i = 2; i <= 65; ++i) { 
        // Check for potential overflow before computing 4*current_L + 3.
        // ull(-1) gives the maximum value for unsigned long long.
        if (current_L > ((ull)(-1) - 3) / 4) { 
             break; // Stop computation if overflow is detected.
        }
        
        ull next_L = 4 * current_L + 3;
        // Additional safety check against unexpected wrap-around (unlikely with check above).
        if (next_L < current_L) break; 

        current_L = next_L;
        L_vals.push_back(current_L); // Store the computed length L_i.
        
        // Update min_level_k if this is the first level found where L_i >= K.
        if (min_level_k == -1 && current_L >= K) {
            min_level_k = i;
            // We could potentially stop early after finding min_level_k, but computing
            // a few more levels doesn't hurt performance significantly and simplifies logic.
        }
    }

    // Determine the threshold level n_0. For N >= n_0, the problem can be reduced.
    // n_0 is the level such that S_{n_0-1} is the first string with length >= K.
    ull n_0;
    if (min_level_k == -1) {
         // If K is larger than L_65, something is unexpected given K <= 10^15 constraint.
         // Handle defensively: set n_0 high to prevent incorrect reduction.
         n_0 = 70; // Higher than max computed level index.
    } else {
        n_0 = (ull)min_level_k + 1;
    }
    
    // Initialize final N and K values to the input N and K.
    ull N_final = N;
    ull K_final = K;

    // If N is large enough (N >= n_0), apply the reduction step.
    // This step handles cases where N is very large, reducing N towards n_0 and K towards 1.
    if (N >= n_0) {
        // Calculate max steps N can be reduced (down to n_0).
        ull diff_N = N - n_0; 
        // Calculate max steps K can be reduced (down to 1).
        ull diff_K = K - 1; 
        // The actual number of reduction steps is the minimum of these two.
        ull delta = min(diff_N, diff_K);
        
        // Apply the reduction to N and K.
        N_final = N - delta;
        K_final = K - delta;
    }
    
    // Call the recursive solver with the final (potentially reduced) N and K.
    cout << recursive_solve(N_final, K_final) << endl;

    return 0;
}