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
|
#!/usr/bin/python3
seeds = []
maps = []
from os import getenv
file = open("/root/dl/input5")
if getenv("IN") != None:
file = open("in.txt")
seeds.extend([x for x in map(int, file.readline().strip().split(": ")[1].split(" "))])
file.readline().strip()
def read_map():
l = file.readline()
# s = l.split("-")[0] # ne rabimo
# d = l.split("-")[2].split(" ")[0] # ne rabimo
l = file.readline()
v = []
while l != "\n" and l != "":
v.append((int(l.strip().split(" ")[0]), int(l.strip().split(" ")[1]), int(l.strip().split(" ")[2])))
l = file.readline()
maps.append(sorted(v, key=lambda x: x[1]))
if l == "":
return False
return True
while read_map():
pass
def get_next_step(target, steps): # možnost izboljšave z bisekcijo
def helper():
for index in range(len(steps)):
if index+1 == len(steps):
return steps[index]
if steps[index+1][1] > target:
return steps[index]
r = helper()
# print("r", r)
if r[1] > target:
return target
if r[1] + r[2] - 1 < target:
return target
return r[0]+target-r[1]
locations = {}
for s in seeds:
l = get_next_step(s, maps[0])
# print("l", l)
for m in maps[1:]:
l = get_next_step(l, m)
# print("l", l)
locations[s] = l
print(min(locations.items(), key=lambda x: x[1])[1])
from interval import interval, inf
semena = interval()
for i in range(len(seeds)//2):
semena |= interval([seeds[2*i], seeds[2*i]+seeds[2*i+1]])
# print(semena)
def celoštevilski_komplement(intervala):
r = interval()
for i in range(len(intervala)):
if i == 0:
if intervala[i][0] == -inf:
continue
r |= interval([-inf, intervala[i][0]-1])
if i+1 == len(intervala):
if intervala[i][1] == inf:
continue
r |= interval([intervala[i][1]+1, inf])
if i != 0:
r |= interval([intervala[i-1][1]+1, intervala[i][0]-1])
return r
def go_deeper(m, vhod):
r = interval()
porabljeni_sources = interval()
for m in m:
source = interval([m[1], m[1]+m[2]])
# print("source", source, "!source", celoštevilski_komplement(source))
# print("m", m, "source", source, "source^C", celoštevilski_komplement(source))
r |= (source & vhod) + m[0] - m[1]
porabljeni_sources |= source
vhod &= celoštevilski_komplement(porabljeni_sources)
r |= vhod
# print("go_deeper r", r)
return r
for i in range(len(maps)):
semena = go_deeper(maps[i], semena)
print(semena[0][0])
|
