-
Notifications
You must be signed in to change notification settings - Fork 15
/
golf-gophers.py
83 lines (73 loc) · 2.01 KB
/
golf-gophers.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
# Copyright (c) 2019 kamyu. All rights reserved.
#
# Google Code Jam 2019 Round 1A - Problem B. Golf Gophers
# https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104f1a
#
# Time: O(B * N + BlogM)
# Space: O(B)
#
import sys
import itertools
def mul_inv(a, b):
b0 = b
x0, x1 = 0, 1
if b == 1: return 1
while a > 1:
q = a // b
a, b = b, a%b
x0, x1 = x1 - q * x0, x0
if x1 < 0: x1 += b0
return x1
# https://rosettacode.org/wiki/Chinese_remainder_theorem
def chinese_remainder(n, a): # Time: O(BlogM), len(n) = B, PI(n) = M
sum = 0
prod = reduce(lambda a, b: a*b, n)
for n_i, a_i in itertools.izip(n, a):
p = prod // n_i
sum += a_i * mul_inv(p, n_i) * p
return sum % prod
def golf_gophers(N, M):
modulis, residues = [], []
prod = 1
for n_i in reversed(MODULIS):
print " ".join(map(str, [n_i]*B))
sys.stdout.flush()
modulis.append(n_i)
residues.append(sum(map(int, raw_input().strip().split())) % n_i)
prod *= n_i
if prod >= M:
break
# these modulis work in chinese remainder theorem (each one is prime to the others)
result = chinese_remainder(modulis, residues)
if result == 0:
result = prod
print result
sys.stdout.flush()
verdict = input()
if verdict == -1: # error
exit()
def getPrimes(n):
primes = []
if n < 2:
return []
primes.append(2)
is_prime = [True] * n
for i in xrange(3, n+1, 2):
if not is_prime[i-1]:
continue
primes.append(i)
for j in xrange(i*i, n+1, 2*i):
is_prime[j-1] = False
return primes
B = 18
primes = getPrimes(B)
MODULIS = []
for i in xrange(len(primes)): # Time: O(BlogB)
moduli = 1
while moduli * primes[i] <= B:
moduli *= primes[i]
MODULIS.append(moduli)
MODULIS.sort() # [5, 7, 9, 11, 13, 16, 17]
T, N, M = map(int, raw_input().strip().split())
for case in xrange(T):
golf_gophers(N, M)