Vemo, koliko je ura (v minutah od bogvekdaj) in kateri avtobusi so na razpolago.
939
7,13,x,x,59,x,31,19
To pravi, da je ura 939, vozijo avtobusi 7, 13, 59, 31 in 19. Vsi avtobusi so odpeljali s postaje ob času 0, nato pa 7 odpelje vsakih 7 minut, 13 vsakih 13 minut, 59 vsakih 59 minut. Ostanek razumete.
Tisti x
bodo postali pomembni v prvem delu naloge, zato
jih bomo razložili takrat. Za zdaj povejmo le, da potrebujemo številke
avtobusov in mesta, na katerih se pojavijo, torej
[(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]
.
= open("example.txt")
f = int(f.readline())
start = [(int(x), i) for i, x in enumerate(f.readline().split(",")) if x != "x"]
buses
buses
[(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]
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.
= min(((start + bus - 1) // bus * bus, bus) for bus, _ in buses)
departure, bus print(departure, bus, (departure - start) * bus)
944 59 295
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):
= 1, 0
sp, tp = 0, 1
s, t while b:
= a // b
k = b, a % b
a, b = s, sp - k * s
sp, s = t, tp - k * t
tp, t return a, sp, tp
def chinese(conds):
= 0, 1
a1, n1 for n2, a2 in conds:
= egcd(n1, n2)
_, m1, m2 = a1 * m2 * n2 + a2 * m1 * n1
a1 *= n2
n1 %= n1
a1 return a1
= open("input.txt")
f = int(f.readline())
start = [(int(bus), int(bus) - delay) for delay, bus in enumerate(f.readline().split(",")) if bus != "x"]
buses print(chinese(buses))
626670513163231