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
|
|||
|
|
```
|