60 lines
3.2 KiB
Markdown
60 lines
3.2 KiB
Markdown
---
|
||
id: 5900f48b1000cf542c50ff9e
|
||
title: 'Проблема 287: Кодування Дерева квадратів (простий алгоритм стиснення)'
|
||
challengeType: 5
|
||
forumTopicId: 301938
|
||
dashedName: problem-287-quadtree-encoding-a-simple-compression-algorithm
|
||
---
|
||
|
||
# --description--
|
||
|
||
Кодування дерева квадратів дозволяє описати чорно-біле зображення $2^N×2^N$ як послідовність бітів (0 та 1). Ці послідовності читаються зліва направо - так:
|
||
|
||
- перший біт укладається з повною базою $2^N×2^N$ регіону;
|
||
- "0" показує розділення:
|
||
- поточна площа $2^n×2^n$ поділена на 4 півплощі виміру $2^{n - 1}×2^{n - 1}$,
|
||
- наступні біти містять опис верхнього лівого верхнього лівого і правого верхнього та нижнього правого підплощ - в такому порядку;
|
||
- "10" вказує на те, що поточна площа містить лише чорні пікселі;
|
||
- "11" вказує, що поточна площа містить лише білі пікселі.
|
||
|
||
Розглянемо зображення 4×4 (кольорові марки означають місце, де може відбутися розділ):
|
||
|
||
<img class="img-responsive center-block" alt="Зображення 4х4 з кольоровими позначками позначають, де можуть з'явитися розділи" src="https://cdn.freecodecamp.org/curriculum/project-euler/quadtree-encoding-a-simple-compression-algorithm.gif" style="background-color: white; padding: 10px;" />
|
||
|
||
Це зображення може бути описано декількома послідовностями, Наприклад,"<strong><span style="color: red">0</span></strong><strong><span style="color: blue">0</span></strong>10101010<strong><span style="color: green">0</span></strong>1011111011<strong><span style="color: orange">0</span></strong>10101010", довжиною 30, або "<strong><span style="color: red">0</span></strong>10<strong><span style="color: green">0</span></strong>101111101110", довжиною 16, якою є мінімальна послідовність для цього зображення.
|
||
|
||
Для позитивного цілого $N$визначте $D_N$ як $2^N×2^N$ зображення з наступною кольоровою схемою:
|
||
|
||
- піксель з координатами $x = 0$, $y = 0$ відповідає нижньому лівому пікселю,
|
||
- якщо ${(x - 2^{N - 1})}^2 + {(y - 2^{N - 1})}^2 ≤ 2^{2N - 2}$ тоді, піксель чорний,
|
||
- інакше піксель - білий.
|
||
|
||
Яка довжина мінімальної послідовності, що описує $D_{24}$?
|
||
|
||
# --hints--
|
||
|
||
`quadtreeEncoding()` має повернути `313135496`.
|
||
|
||
```js
|
||
assert.strictEqual(quadtreeEncoding(), 313135496);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function quadtreeEncoding() {
|
||
|
||
return true;
|
||
}
|
||
|
||
quadtreeEncoding();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|