Ramona Dragoș: Pagină nouă: == Enunt == Se consideră N intervale [Ai,Bi], 1 ≤ i ≤ N disjuncte. Tuturor intervalelor li se aplică o operație de extindere la ambele capete cu o valoare naturală x, astfel încât după extindere cu valoarea x, intervalul [Ai,Bi] va deveni intervalul [Ai-x,Bi+x], 1 ≤ i ≤ N. După extindere, spunem că intervalele [Ai,Bi] și [Aj,Bj] aparțin aceluiași grup de intervale dacă ele se intersectează sau dacă există un interval [Ak,Bk] astfel încât [Ai,Bi] se...

2023-12-31T14:34:55Z

Pagină nouă: == Enunt == Se consideră N intervale [Ai,Bi], 1 ≤ i ≤ N disjuncte. Tuturor intervalelor li se aplică o operație de extindere la ambele capete cu o valoare naturală x, astfel încât după extindere cu valoarea x, intervalul [Ai,Bi] va deveni intervalul [Ai-x,Bi+x], 1 ≤ i ≤ N. După extindere, spunem că intervalele [Ai,Bi] și [Aj,Bj] aparțin aceluiași grup de intervale dacă ele se intersectează sau dacă există un interval [Ak,Bk] astfel încât [Ai,Bi] se...

New page

== Enunt ==
Se consideră N intervale [Ai,Bi], 1 ≤ i ≤ N disjuncte.

Tuturor intervalelor li se aplică o operație de extindere la ambele capete cu o valoare naturală x, astfel încât după extindere cu valoarea x, intervalul [Ai,Bi] va deveni intervalul [Ai-x,Bi+x], 1 ≤ i ≤ N.

După extindere, spunem că intervalele [Ai,Bi] și [Aj,Bj] aparțin aceluiași grup de intervale dacă ele se intersectează sau dacă există un interval [Ak,Bk] astfel încât [Ai,Bi] se intersectează cu [Ak,Bk] iar intervalele [Ak,Bk], [Aj,Bj] aparțin aceluiași grup de intervale.
== Cerința ==
Să se determine valoarea minimă x cu care vor trebui să fie extinse toate intervalele astfel încât să se formeze un grup cu cel puțin P intervale.
== Date de intrare ==
Fișierul de intrare intervale3in.txt conține pe prima linie numerele naturale N și P cu semnificația din enunț. Pe următoarele N linii sunt descrise cele N intervale, câte un interval pe linie. Pentru fiecare interval i sunt specificate capetele sale Ai şi Bi.
== Date de ieșire ==
Fișierul de ieșire intervale3out.txt va conţine pe prima linie numărul natural x ce reprezintă valoarea minimă cu care vor trebui extinse intervalele astfel încât să se obțină cel puțin un grup format din cel minimum P intervale.
== Restricții și precizări ==
*2 &les; N &les; 100 000
*-1 400 000 000 &les; Ai < Bi &les; 1 400 000 000
*2 &les; P &les; N
*Două intervale se intersectează dacă au cel puţin un punct comun
*Pentru 30% dintre teste N &les; 10 000
== Exemplu 1 ==
;intervale3in.txt
:7 3
:8 9
:21 25
:14 17
:1 4
:28 32
:35 42
:100 200
;intervale3out.txt
:2
<br>
== Exemplu 2 ==
;intervale3in.txt
:-1 0 0
;intervale3out.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0699 - Intervale3
def read_input(file_name):
try:
with open(file_name, 'r') as file:
N, P = map(int, file.readline().split())
intervals = [list(map(int, file.readline().split())) for _ in range(N)]

return N, P, intervals
except Exception as e:
print(f"Nu au fost respectate cerintele impuse: {str(e)}")
return None

def write_output(file_name, result):
with open(file_name, 'w') as file:
if result is not None:
file.write(str(result) + "\n")

def min_extension(N, P, intervals):
intervals.sort()

left, right = 0, max(intervals[i][1] - intervals[i][0] for i in range(N))
result = 2

while left <= right:
mid = (left + right) // 2
groups = 1
end = intervals[0][1]

for i in range(1, N):
if intervals[i][0] - mid <= end:
end = max(end, intervals[i][1])
else:
groups += 1
end = intervals[i][1]

if groups >= P:
result = min(result, mid)
right = mid - 1
else:
left = mid + 1

return result

def main(input_file, output_file):
result = read_input(input_file)
if result is not None:
N, P, intervals = result
result = min_extension(N, P, intervals)
write_output(output_file, result)

if __name__ == "__main__":
main("intervale3in.txt", "intervale3out.txt")

</syntaxhighlight>

0699 - Intervale3 - Revision history