Задача 220
Дракон Хейтуэя

Пусть D_(0) будет двухбуквенной строкой "Fa". Для n≥1, D_(n) образуется из D_(n-1) путем следующих правил переписывания строк:

"a" → "aRbFR"
"b" → "LFaLb"

Таким образом, D_(0) = "Fa", D_(1) = "FaRbFR", D_(2) = "FaRbFRRLFaLbFR", и так далее.

Эти строки могут быть истолкованы как инструкции для программы компьютерной графики так, что "F" значит "рисовать на одну единицу вперед", "L" значит "повернуть налево на 90 градусов", "R" значит "повернуть направо на 90 градусов", а "a" и "b" игнорируются. Начальное положение компьютерного курсора (0,0), направление - наверх, на (0,1).

Тогда D_(n) становится необычным рисунком, известным как дракон Хейтуэя порядка n. Например, D_(10) показан ниже; считая каждое "F" как один шаг, выделенная точка на (18,16) является положением, достигнутым в 500 шагов.

Каким будет положение курсора после 10^(12) шагов в D_(50) ?
Дайте ответ в виде x,y без пробелов.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net