f = open("example.txt")
start = int(f.readline())
buses = [(int(x), i) for i, x in enumerate(f.readline().split(",")) if x != "x"]

buses
[(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]

Prvi del: prvi večkratnik

Zanima nas, kateri avtobus bo odpeljal naslednji.

Najprej za vsak avtobus izpišimo, kdaj odpelje naslednjič. Za vsak avtobus bi lahko izračunali, za koliko smo ga zamudili (start % bus); naslednji bo odpeljal čez start + (bus - start % bus) minut ... razen, če je start % bus ravno 0, se pravi, če avtobus odpelje zdaj.

Da ne kompliciramo, se raje lotimo tako: (start + bus - 1) // bus * bus: k trenutnemu času prišetejemo bus - 1. V času od start do (vključno) start + bus - 1 bo peljal natančno en avtobus. Če ta čas celoštevilsko delimo z bus in pomnožimo nazaj z bus, bomo dobili prvi večkratnik bus-a po start.

for bus, _ in buses:
    print(bus, (start + bus - 1) // bus * bus)
7 945
13 949
59 944
31 961
19 950

Izmed teh je potrebno poiskati tistega, ki odpelje prvi in izračunati produkt njegove številke in časa čakanja.

Prav. Gornje pare bomo obrnili, tako da bo spredaj čas odhoda. Iz teh parov poiščemo minimum, in iz para razberemo številko in čas odhoda.

departure, bus = min(((start + bus - 1) // bus * bus, bus) for bus, _ in buses)
print(departure, bus, (departure - start) * bus)
944 59 295

Drugi del: Kitajski ostanki

Zdaj poglejmo celo spremenljivko buses.

buses
[(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]

Zanima nas, za kateri čas velja, da bo avtobus 7 odpeljal točno ob tem času, 13 odpelje eno minuto kasneje, 59 odpelje 4 minute kasneje in tako naprej. Čas, ki ga iščemo, je precej velik, tako da kakšno iskanje po vrsti ne pride v poštev.

Najprej obrnimo: 7 ujememo, 13 smo zamudili za 13 - 1 = 12 minut, 59 smo zamudili za 59 - 4 = 55 minut in tako naprej.

To pomeni: iščemo tak čas t, da je ostanek po deljenju t s 7 enak 0, ostanek po deljenju t s 13 je enak 12, ostanek po deljenju t z 59 je enak 55 in tako naprej.

V splošnem, imamo seznam števil ni in ai, in naloga je najti x, za katerega velja, da je ostanek po deljenju x z vsakim ni enak ai. Iščemo rešitev problema kitajskih ostankov. Stvar je popolnoma matematična: sprogramirati je potrebno razširjeni Evklidov algoritem in ga uporabljati na parih števil.

def egcd(a, b):
    sp, tp = 1, 0
    s, t = 0, 1
    while b:
        k = a // b
        a, b = b, a % b
        sp, s = s, sp - k * s
        tp, t = t, tp - k * t
    return a, sp, tp

def chinese(conds):
    a1, n1 = 0, 1
    for n2, a2 in conds:
        _, m1, m2 = egcd(n1, n2)
        a1 = a1 * m2 * n2 + a2 * m1 * n1
        n1 *= n2
        a1 %= n1
    return a1

f = open("input.txt")
start = int(f.readline())
buses = [(int(bus), int(bus) - delay) for delay, bus in enumerate(f.readline().split(",")) if bus != "x"]
print(chinese(buses))
626670513163231