Вычисление рекурсивно определенной строки

Question

Последовательность строк определяется рекурсивно следующим образом:

Уровень 1: S ₁ = 'OuQ'

Уровень k: S _k = 'O' + S _k-1 + 'u' + S _k-1 + 'Q'

Например, S ₂ = 'O' + S ₁ + 'u' + S ₁ + 'Q' = 'OOuQuOuQQ'.

Учитывая 3 целых числа k, l и r, найти все символы S _k [l], S _k [ l + 1], ..., S _k [r − 1], S _k [r] (где 0

Answer 1

Вот нерекурсивное решение. Поскольку l и r могут быть большими, я изменил их на uint64_t.

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>


//  OuQ(k, p) returns the character at position p in S[k].
static char OuQ(int k, uint64_t p)
{
    //  Find the length of S[k-1], treating S[0] as the empty string.
    uint64_t l = 0;
    for (int i = 1; i < k; ++i)
        l = 2*l + 3;

    /*  Identify where p is in O S[k-1] u S[k-1] Q.  If it is one of the
        terminal letters, return that.  Otherwise, adjust p to the position
        within S[k-1], then reduce the problem to that (by adjusting l), and
        repeat.
    */
    while (1)
    {
        if (p < 1)
            return 'O';
        else if (p < 1+l)
            p -= 1;
        else if (p < 1+l+1)
            return 'u';
        else if (p < 1+l+1+l)
            p -= 1+l+1;
        else
            return 'Q';
        l = (l-3)/2;
    }
}


int main()
{
    /*  uint64_t is used for l and r, since they may be large.  SCNu64 is
        defined in <inttypes.h> and provides a conversion specifier for
        uint64_t.
    */
    int k;
    uint64_t l, r;
    scanf("%d%" SCNu64 "%" SCNu64, &k, &l, &r);

    for (uint64_t i = l; i <= r; ++i)
        putchar(OuQ(k, i));
    putchar('\n');
}