summaryrefslogtreecommitdiff
path: root/13_2020.py
blob: 956805f848622bd12e742dd08045e55c9fb593ae (plain)
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
84
85
86
87
88
89
import fileinput
import re


def gcd(x, y):
    if x == 0:
        return y
    return gcd(y % x, x)


# Compute b**e modulo mod
def mod_pow(b, e, mod):
    if e == 0:
        return 1
    elif e % 2 == 0:
        # If E is even, a**E = (a^2)^(E/2)
        return mod_pow((b * b) % mod, e / 2, mod)
    else:
        return (b * mod_pow(b, e - 1, mod)) % mod


# We want to find x s.t. (a*x)%m == 1
# Number theory fact: if m is prime, then a**(m-1)==1 for any a.
# Therefore, a**(m-2)*a == 1 for every a.
# So a**(m-2) is a modular inverse of a!
def mod_inverse(a, m):
    return mod_pow(a % m, m - 2, m)


lines = list(fileinput.input())
t0 = int(lines[0])
B1 = [int(x) for x in lines[1].strip().split(",") if x != "x"]
best = None
for b in B1:
    t = t0
    while t % b != 0:
        t += 1
    wait_time = t - t0
    if best is None or wait_time < best[0]:
        best = (wait_time, b)
print(best[0] * best[1])

# Part 2. We want to find time T.
B = lines[1].strip().split(",")
# Suppose bus K appears at index I in the list.
# K should depart at time T+I. i.e. T+I should be a multiple of K.
# T+I % K == 0
# T % K == -I
# T % K == (K-(I%K))%K (want 0<=RHS<K)

# Chinese remainder theorem: Let N be the product of the bus IDs in our input.
# There is exactly one T <N satisfying the constraints.

constraints = []
N = 1
for i, b in enumerate(B):
    if b != "x":
        b = int(b)
        i %= b
        constraints.append(((b - i) % b, b))
        N *= b

ans = 0
# x % b = i
for i, b in constraints:
    NI = N / b
    # NI is the product of the *other* bus IDs
    # If we add a multiple of NI to T, it won't affect when the other buses arrive modulo T,
    # since NI is a multiple of each other bus ID.
    # Is there a multiple of NI we can add to T so that T%b==i? Yes!
    # We want to find a multiple of NI s.t. (a*NI)%b == i
    # First find MI s.t. (MI*NI)%b == 1
    # Then (i*MI*NI)%b == i
    assert gcd(NI, b) == 1
    mi = mod_inverse(NI, b)
    assert mi == mod_inverse(NI, b)
    assert (mi * NI) % b == 1
    assert (i * mi * NI) % b == i
    for_b = i * mi * NI
    assert for_b % b == i
    assert for_b % NI == 0
    ans += for_b
    # print(i,ni,mi,b)

ans %= N
for i, b in constraints:
    assert ans % b == i

print(ans)