---
# System prepended metadata

title: 12602 - OuQ String
tags: [NTHUOJ]

---

# 12602 - OuQ String
## 題解:
用遞迴解才不會TLE，共拆成五個部分來判斷，
“O” + sk−1 + “u” + sk−1 + “Q”，
用l跟r的位置來看要不要處理那個部分。
## Code:
```c=1
#include <stdio.h>
#define min(a, b) (a > b ? b : a)
#define max(a, b) (a > b ? a : b)
#define ll long long

ll len[51];

void init(){
    // calculate length
    len[1] = 3;
    for(int i=2; i<=50; i++)
        len[i] = 2 * len[i-1] + 3;
}

void solve(ll k, ll l, ll r){
    char s[] = "OuQ";
    if(k == 1){
        for(int i=l; i<=r; i++)
            printf("%c", s[i]);
        return;
    }
    ll temp = 0; // position
    /* O */
    if(l == 0) printf("%c", s[0]);
    // Sk-1
    if(l<=len[k-1] && r>=1)
        solve(k-1, max(l-1, 0), min(r-1, len[k-1]-1));
    temp = 1 + len[k-1]; // position of u
    /* u */
    if(l<=temp && r>=temp) printf("%c", s[1]);
    // Sk-1
    if(l<=temp+len[k-1] && r>=temp+1)
        solve(k-1, max(l-temp-1, 0), min(r-temp-1, len[k-1]-1));
    /* Q */
    if(r == len[k]-1) printf("%c", s[2]);
}

int main(){
    init();
    ll k, l, r;
    while(scanf("%lld%lld%lld", &k, &l, &r) != EOF){
        solve(k, l, r);
        printf("\n");
    }
    return 0;
}
```
###### tags: `NTHUOJ`