58 lines
2.2 KiB
Markdown
58 lines
2.2 KiB
Markdown
---
|
||
id: 5900f4281000cf542c50ff39
|
||
title: 'Завдання 186: Підключення до мережі'
|
||
challengeType: 5
|
||
forumTopicId: 301822
|
||
dashedName: problem-186-connectedness-of-a-network
|
||
---
|
||
|
||
# --description--
|
||
|
||
Ось записи з зайнятої телефонної системи з мільйоном користувачів:
|
||
|
||
| RecNr | Абонент | Дзвонили |
|
||
| ----- | ------- | -------- |
|
||
| 1 | 200007 | 100053 |
|
||
| 2 | 600183 | 500439 |
|
||
| 3 | 600863 | 701497 |
|
||
| ... | ... | ... |
|
||
|
||
Телефонний номер абонента і набраний номер у записі $n$ є $Caller(n) = S_{2n - 1}$ та $Called(n) = S_{2n}$, де ${S}_{1,2,3,\ldots}$ утворюється через "Генератор Фібоначчі":
|
||
|
||
Для $1 ≤ k ≤ 55$, $S_k = [100003 - 200003k + 300007{k}^3]\\;(\text{modulo}\\;1000000)$
|
||
|
||
Для $56 ≤ k$, $S_k = [S_{k - 24} + S_{k - 55}]\\;(\text{modulo}\\;1000000)$
|
||
|
||
Якщо $Caller(n) = Called(n)$ вважається, що користувач помилився номером і стався збій виклику, в іншому випадку виклик успішний.
|
||
|
||
Від початку записів ми кажемо, що будь-яка пара користувачів $X$ та $Y$ - друзі, якщо $X$ телефонує $Y$ або навпаки. Аналогічно $X$ є другом друга $Z$, якщо $X$ є друг $Y$ і $Y$ є другом $Z$; і так далі в довших ланцюжках.
|
||
|
||
Номер телефону прем'єр-міністра - 524287. Після скількох успішних викликів, не рахуючи збої викликів, 99% користувачів (включаючи прем'єр-міністра) будуть друзями, або друзями друзів і т. д. прем'єр-міністра?
|
||
|
||
# --hints--
|
||
|
||
`connectednessOfANetwork()` повинен повернути `2325629`.
|
||
|
||
```js
|
||
assert.strictEqual(connectednessOfANetwork(), 2325629);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function connectednessOfANetwork() {
|
||
|
||
return true;
|
||
}
|
||
|
||
connectednessOfANetwork();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|