2.2 KiB
id, title, challengeType, forumTopicId, dashedName
id | title | challengeType | forumTopicId | dashedName |
---|---|---|---|---|
5900f4281000cf542c50ff39 | Завдання 186: Підключення до мережі | 5 | 301822 | 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
.
assert.strictEqual(connectednessOfANetwork(), 2325629);
--seed--
--seed-contents--
function connectednessOfANetwork() {
return true;
}
connectednessOfANetwork();
--solutions--
// solution required