Lista de probleme 2

Nivelul concursului: Național

Grupe

Clasele VII-VIII Seniori

Etichete

#2861 puncte4

Zăhărel a desenat pe o foaie de hârtie N puncte în plan. Curios din fire, şi-a ales încă M puncte pe axa OX şi s-a întrebat pentru fiecare dintre cele M puncte de pe axa Ox care dintre cele N puncte este cel mai apropiat (situat la distanță minimă). Se consideră că distanța dintre două puncte (x1, y1) şi (x2, y2) este (x1-x2)2 + (y1-y2)2. Scrieți un program pentru Zăhărel care să determine pentru fiecare dintre cele M puncte de pe axa OX, care este distanța la cel mai apropiat punct dintre cele N desenate pe hârtie.

#2431 cover

Se consideră N intervale închise, având extremităţile numere naturale cuprinse între 1 şi L. Fiecare număr natural i din intervalul [1, L] are asociată o pondere c[i]. Numim acoperire o mulţime de numere naturale cuprinse între 1 şi L cu proprietatea că fiecare interval conţine cel puţin un element al mulţimii. Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.
Pentru un set de intervale dat să se determine costul minim al unei acoperiri.