プロジェクトオイラー
http://projecteuler.net/index.php
Q186.
100万人いて、与えられた疑似乱数で電話をかける人とかけられる人を決める。かけた人とかけられた人は友達であるとする。この作業を繰り返し、首相の友達、友達の友達、、、が100万人の99%以上になるには最低何回電話をこの作業を繰り返さなければならないか。
特になんの工夫もない。
首相の友達グループとグラフを用意しておく。グラフは、各人の繋がっている人のリスト。電話をかける人が首相の友達グループなら、かけられる人に繋がっている人を芋づる式に首相の友達グループに入れる。逆も同様。
易問だと思うが、さんざん苦しんだ前の問題より正答者が少ないのはどうしたことだろう。
from itertools import countdef gen_random():
s = [ 0 ]
for k in range(1, 56):
n = int(((300007 * k * k - 200003) * k + 100003) % N)
yield n
s.append(n)
for k in count(56):
n = (s[(k-24)%56] + s[(k-55)%56]) % N
yield n
s[k%56] = ndef extend_group(s, g, ID):
friend_set = set()
stack = [ ]
friend_set.add(ID)
stack.append(ID)
while len(stack):
id = stack.pop()
for friend in g[id]:
if friend not in friend_set:
friend_set.add(friend)
stack.append(friend)
s |= friend_set
return len(s)def f(num_friend_users):
counter = 0
friend_group = set([ PM ])
graph = [ [ ] for i in xrange(N) ]
g = gen_random()
while True:
caller = g.next()
called = g.next()
if caller == called:
continue
counter += 1
if caller in friend_group:
if not called in friend_group:
n = extend_group(friend_group, graph, called)
if n >= num_friend_users:
return counter
else:
if called in friend_group:
n = extend_group(friend_group, graph, caller)
if n >= num_friend_users:
return counter
else:
graph[caller].append(called)
graph[called].append(caller)N = 1000000
PM = 524287
print f(990000)
