2
|
Задача 355. Телефонные звонкипостоянный адрес задачи: http://www.diofant.ru/problem/1292/показать код для вставки на свой сайт >> |
Задачу решили:
4
всего попыток:
8
поделиться задачей:
|
|
|
Задача опубликована:
17.01.11 08:00
Прислал:
admin
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
1
сложность:
1
класс:
8-10
баллы: 100
Темы:
арифметика
|
|
|
В некотором городе построили телефонную сеть на миллион абонентов с шестизначными телефонными номерами. Данные о телефонных звонках фиксировали в базе данных. Перед вами несколько первых записей из нее:
| Порядковый номер звонка, n |
Кто звонит, S2n-1 |
Кому звонят, S2n |
| 1 | 200007 | 100053 |
| 2 | 600183 | 500439 |
| 3 | 600863 | 701497 |
| ... | ... | ... |
Номера абонентов S2n-1 и S2n для данной таблицы мы получили с помощью генератора псевдослучайных чисел Фибоначчи с запаздыванием:
При 1 ≤k≤55, Sk = [100003 - 200003k + 300007k3] (mod 1000000)
При 56 ≤k, Sk = [Sk-24 + Sk-55] (mod 1000000)
(p(mod q) означает остаток от деления p на q)
При необходимости полученные числа дополняли до шести знаков нулями слева.
Мы будем считать, что если X позвонил Y, или наоборот, Y позвонил X, X и Y становятся друзьями. Если X является другом Y, а Y другом Z, то мы также считаем X и Z друзьями, и так далее для сколь угодно длинных цепочек.
Телефонный номер мэра города – 100000. После очередного звонка количество друзей мэра превысило половину населения города. Сколько в этот момент у него оказалось друзей (включая его самого)?
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
k-24 и k-55, очевидно, индексы?
Население города ровно 1 миллион? Или может быть меньше?