Concurs de pregătire · Informatică · 2021

Subiect și barem · pagina 1

UNIVERSITATEA DE VEST TIMIS, OARA
FACULTATEA DE MATEMATICĂ S, I INFORMATICĂ
Concurs FMI ed. VI-a 2021
Informatică
Problema
Se dau n intervale închise [a1, b1], [a2, b2], . . ., [an, bn] s, i un număr natural k (k < n).
Presupunem că: (i) cele 2n extremităt, i ale intervalelor sunt valori întregi distincte; (ii) niciunul dintre intervale nu
este inclus într-un alt interval.
Propunet, i un algoritm cât mai eficient care să determine câte intervale intersectează exact alte k intervale.
De exemplu, pentru setul de intervale [1, 3], [4, 8], [2, 5], [6, 9] s, i k = 2 există două intervale care satisfac cerint, a: [2,
5] se intersectează cu: [1, 3], [4, 8]; [4, 8] se intersectează cu: [2, 5], [6, 9].
Prezentat,i pe scurt ideea de rezolvare s, i descriet,i solut,ia în pseudocod sau într-un limbaj de programare la alegere
(C/C++, Pascal, Python).
BAREM
Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
Teste valide pe platforma stepik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct.
În urma explicat, iilor de la proba orală
Rezolvare completă
în n2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
sau
în nlog(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct.
Descrierea ideii de rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct.
Implementare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct.
Idee de rezolvare în nlog(n)
Pentru că intervalele nu se pot cont, ine unele pe altele s, i pentru că avem capete unice, un algoritm eficient O(nlog(n))
este:
Pas 1 O(nlog(n)): Sortăm crescător capetele intervalelor a1,b1, a2, b2, . . ., an, bn folosind o sortare de complexitate
nlog(n), păstrând informat, ii despre: tip capăt (stânga - S, dreapta - D) s, i identificator de interval. Pentru exemplul
propus stocăm următoarele informat, ii:
capete interval 1 2 3 4 5 6 8 9
identificator interval (ID) 1 3 1 2 3 4 2 4
tip_capat S S D S D S D D
Pas 2 O(n): Se parcurge s, irul sortat anterior s, i dacă întâlnim un capăt stânga vom nota indexul de pozit, ie într-un
alt vector, iar când intâlnim un capăt dreapta calculăm câte intervale intersecteazâ intervalul dat, prin diferent, a
indicilor extremităt, ilor.
pentru i ← 1, 2n execută
dacă tip_capat[i] = S atunci
intersectii[ID[i]] = i // capatul stang
altfel
intersectii[ID[i]] = i - intersectii[ID[i]] - 1 // capatul stang minus cel drept − 1
Pas 3 O(n): Se parcurge vectorul intersectii s, i se numără câte elemente sunt egale cu k (cerut în enunt, ).
1