*[[Problem 186:http://projecteuler.net/problem=186]] 「あるネットワークの連結性」 [#ya42e894]
今, 100万人のユーザをもつ電話システムの通信記録がある.

|Rec Nr	|Caller	|Called|
|1	|200007	|100053|
|2	|600183	|500439|
|3	|600863	|701497|
|...	|...	|...|

n番目の記録の掛けた側と掛けられた側の電話番号は Caller(n) = &tex{S_{2n-1}}; と Called(n) = &tex{S_{2n}};で与えられる. &tex{S_{1}, S_{2}, ...};は“ラグ付きフィボナッチ生成器”で定義される.

1 ≤ k ≤ 55については, &tex{S_{k} = [100003 - 200003k + 300007k^{3}] (modulo 1000000)};

56 ≤ kでは, &tex{S_{k} = [S_{k-24} + S_{k-55}] (modulo 1000000)};である.

もしCaller(n) = Called(n)であれば, ユーザは間違って電話を掛けたとされ通信は切断される. そうでない場合には, 通信は成功している.

XがYに電話を掛けるかその逆のときに, ユーザXとユーザYが友達であると呼ぶ. 同様に, XがYの友達であるかつYがZの友達であるとき, XがZの友達の友達であると呼ぶ. 同様にして長い連鎖が得られる.

首相の電話番号は524287である. 何回電話を掛けると99%のユーザ (首相自身も含む) が首相の友達になるだろうか?

''(注: 切断された通信は数えない.)''


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS