60 lines
2.1 KiB
Markdown
60 lines
2.1 KiB
Markdown
|
---
|
|||
|
|
id: 5900f5191000cf542c51002b
|
|||
|
|
title: 'Завдання 428: Намисто кіл'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302098
|
|||
|
|
dashedName: problem-428-necklace-of-circles
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Припустимо $a$, $b$ та $c$ — додатні числа.
|
|||
|
|
|
|||
|
|
Тоді $W$, $X$, $Y$, $Z$ будуть чотирма колінеарними точками, де $|WX| = a$, $|XY| = b$, $|YZ| = c$ та $|WZ| = a + b + c$.
|
|||
|
|
|
|||
|
|
Нехай $C_{\text{in}}$ — це коло з діаметром $XY$.
|
|||
|
|
|
|||
|
|
Нехай $C_{\text{out}}$ — коло із діаметром $WZ$.
|
|||
|
|
|
|||
|
|
Триплетом ($a$, $b$, $c$) називають *триплет намиста* — коли $k ≥ 3$ окремі кола $C_1, C_2, \ldots, C_k$ можна розмістити наступним чином:
|
|||
|
|
|
|||
|
|
- $C_i$ немає спільних внутрішніх точок з будь-яким $C_j$ для $1 ≤ i$, $j ≤ k$ та $i ≠ j$,
|
|||
|
|
- $C_i$ дотичне і до $C_{\text{in}}$, і до $C_{\text{out}}$ для $1 ≤ i ≤ k$,
|
|||
|
|
- $C_i$ дотичне до $C_{i + 1}$ для $1 ≤ i < k$, та
|
|||
|
|
- $C_k$ дотикається до $C_1$.
|
|||
|
|
|
|||
|
|
До прикладу, (5, 5, 5) та (4, 3, 2) — триплети намиста, тоді ж як (2, 2, 5), як можна бачити, — ні.
|
|||
|
|
|
|||
|
|
<img class="img-responsive center-block" alt="візуальний приклад триплету намиста" src="https://cdn.freecodecamp.org/curriculum/project-euler/necklace-of-circles.png" style="background-color: white; padding: 10px;" />
|
|||
|
|
|
|||
|
|
Нехай $T(n)$ — це кількість триплетів намиста $(a, b, c)$ таких, як $a$, $b$ та $c$ — додатні цілі числа, а $b ≤ n$. Наприклад, $T(1) = 9$, $T(20) = 732$ та $T(3\\,000) = 438\\,106$.
|
|||
|
|
|
|||
|
|
Знайдіть $T(1\\,000\\,000\\,000)$.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`necklace(1000000000)` має повернути `747215561862`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(necklace(1000000000), 747215561862);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function necklace(n) {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
necklace(1000000000)
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|