Wrong question collection 6 – listen to your words, if you listen to your words

Hits: 0

Article directory

Topic information

Problem solving ideas

  • O(n) recursively calculate the length of each string to determine whether k is legal or not.
  • Use the length to find the law, and O(n) time to find the answer.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const string s1 = " words"; // size = 5
const string s2 = " Listeningtoyour";   // size = 15
const string s3 = " likelisteningtothe"; // size = 18
ll l[105];
char get(ll n, ll k) {
    if (n == 0) {
        return s1[k];
    }
    if (k <= 15) {
        return s2[k];
    }
    if (k <= 15 + l[n - 1]) {
        return get(n - 1, k - 15);
    }
    if (k <= 33 + l[n - 1]) {
        return s3[k - l[n - 1] - 15];
    }
    return get(n - 1, k - l[n - 1] - 33);
}
int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    l[0] = 5;
    for (int i = 1; i <= 100; ++i) {
        l[i] = 33 + 2 * l[i - 1];
        if (l[i] > 1e18) {
            l[i] = 1e18;
        }
    }
    int T;
    cin >> T;
    while (T--) {
        ll n, k;
        cin >> n >> k;
        if (l[n] < k) {
            cout << "*\n";
        } else {
            cout << get(n, k) << '\n';
        }
    }
    return 0;
}

You may also like...

Leave a Reply

Your email address will not be published.