◂ 5 décembre 2025 ▸
Cafeteria : Calculer combien de valeurs données tombent dans des intervalles, puis combien de valeurs totales sont dans ces intervalles
512859921084892-514321322528165
11256263100164-12830604534729
⋮
142458197886533-142780858100993
329928111646776
96135717389080
525241827868042
⋮
Sans trier les intervalles, ni les valeurs, on a un algorithme en O(m·n) pour la partie 1 et O(m²) pour la partie 2.
Mais avec des listes déjà triées comme dans
code_sort.py, l'algorithme est en O(m+n) et O(m).
Pour la partie 2, plutôt que de fusionner les intervalles qui se superposent, on peut juste utiliser une liste des débuts et des fins des intervalles, qu'on parcourt comme une suite de parenthèses (()(())) () (()), les intervalles finaux correspondant aux parenthèses les plus extérieures. Implémentation dans le code
code_optim.py.
Exemple :
3-5
10-14
16-20
12-18
3 5 10 12 14 16 18 20
| | | | | | | |
### ####### #######
| | | | | | | |
| | | ########## |
| | | | | | | |
( ) ( ( ) ( ) )
( ) ( )
3-5 10-------------20
(Remarque générale : si on commence par la partie 2, la partie 1 est un peu plus rapide, puisqu'il y a moins d'intervalles.)
- code.py
- code_sort.py
- code_optim.py
ranges = []
values = []
with open("input.txt", 'r', encoding='utf-8') as f:
for line in f:
line = line.strip()
if '-' in line:
ranges.append([int(v) for v in line.split('-')])
elif line:
values.append(int(line))
rep1 = 0
for v in values:
for s,e in ranges:
if s <= v <= e:
rep1 += 1
break
print("Réponse partie 1:", rep1)
changes = True
while changes:
changes = False
i = 0
while i < len(ranges) - 1:
j = i + 1
s1, e1 = ranges[i]
while j < len(ranges):
s2, e2 = ranges[j]
if not (s2>e1 or s1>e2):
changes = True
ranges[i] = [s1:=min(s1,s2), e1:=max(e1,e2)]
ranges.pop(j)
else:
j += 1
i += 1
rep2 = sum(e-s+1 for (s,e) in ranges)
print("Réponse partie 2:", rep2)