У меня есть рабочий код, но я подозреваю, что это домашнее задание, и думаю, что если вы поймете его, это поможет вам. Поэтому я опишу эту идею и позволю вам попытаться ее закодировать.
Вы должны решить эту проблему с помощью рекурсии.
Два ваших базовых случая: вы находитесь в первом A или первый B. Вы можете просто сравнить длины. Если k <= len(A), вы находитесь в A. Если k <= len(A) + len(B), то вы находитесь в B. В любом случае вы смотрите на персонажа. (Не удивляйтесь, если правильные базовые случаи включают несколько разовых ошибок, это нормально.)
Ваш рекурсивный случай работает следующим образом. Сначала вы строите список длин строк, пока не найдете тот, в который помещается k. В вашем случае этот список [2, 1, 4, 9]. (Правило таково: lengths[i] = lengths[i-2] + 2*lengths[i-1].
Теперь вы знаете, что находитесь в шаблоне ABB. И вы знаете длины A и B. Вычтите длину A. Вычтите длину первого B, если можете. Затем выполните повторение.
В вашем примере вы находитесь в паттерне ABB, где A имеет длину 1, а B имеет длину 4 Итак, вы начинаете с k=7, вычитаете 1, вычитаете 4 (потому что 4 <6), и теперь вы сталкиваетесь с той же проблемой только с <code>k=2.
Recurse и вы обнаружите, что хотите вторая буква A, то есть b.
Для 10**18 вам нужно всего лишь 29 рекурсивных вызовов. В основном это происходит мгновенно.