58 lines
2.2 KiB
Markdown
58 lines
2.2 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4481000cf542c50ff5b
|
|||
|
|
title: 'Завдання 220: Крива Дракона'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 301863
|
|||
|
|
dashedName: problem-220-heighway-dragon
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Нехай $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 кроків.
|
|||
|
|
|
|||
|
|
<img class="img-responsive center-block" alt="малюнок Кривої Дракона після 500 кроків" src="https://cdn.freecodecamp.org/curriculum/project-euler/heighway-dragon.gif" style="background-color: white; padding: 10px;" />
|
|||
|
|
|
|||
|
|
Де буде розташовано курсор після ${10}^{12}$ кроків в $D_{50}$? Дайте свою відповідь у вигляді рядка `x,y` без пробілів.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`heighwayDragon()` має повернути рядок.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(typeof heighwayDragon() === 'string');
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
`heighwayDragon()` має повернути рядок `139776,963904`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(heighwayDragon(), '139776,963904');
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function heighwayDragon() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
heighwayDragon();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|