結果
| 問題 |
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;
}