Inverseaza reviziile

Diferente pentru problema/cover intre reviziile #16 si #1

Diferente intre titluri:

Cover

cover

Diferente intre continut:

== include(page="template/taskheader" task_id="cover") ==

Se considera $N$ intervale inchise, avand extremitatile numere naturale cuprinse intre $1$ si $L$. Fiecare numar natural $i$ din intervalul $[1, L]$ are asociata o pondere $c{~i~}$.
Numim acoperire o multime de numere naturale cuprinse intre $1$ si $L$ cu proprietatea ca fiecare interval contine cel putin un element al multimii. Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.
 
Pentru un set de intervale dat sa se determine costul minim al unei acoperiri.

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare $cover.in$ contine pe prima linie cele doua numere naturale $N L$ separate printr-un spatiu. Pe urmatoarea linie se afla $L$ numere naturale separate prin cate un spatiu $c{~1~} c{~2~} ... c{~L~}$ reprezentand ponderile numerelor naturale din intervalul $[1, L]$. Urmatoarele $N$ linii contin fiecare cate doua numere naturale $a b (1 ≤ a ≤ b ≤ L)$ reprezentand extremitatile intervalelor.

...

h2. Date de iesire

Fisierul de iesire $cover.out$ va contine o singura linie pe care va fi scris un numar natural reprezentand costul minim al unei acoperiri.
 
h2. Restrictii si precizari

...

* $1 ≤ N ≤ 60 000$
* $1 ≤ L ≤ 1 000 000$
* $0 ≤ c{~i~} ≤ 1024$, pentru orice $1 ≤ i ≤ L$
* Pentru @40%@ din teste $N ≤ 1 000$ si $L ≤ 10 000$

h2. Restrictii
* $... ≤ ... ≤ ...$

h2. Exemple

h2. Exemplu

table(example). |_. cover.in |_. cover.out |

| 2 5
100 5 9 6 90
1 3
3 5
| 9 |
| 4 10
1 3 6 4 5 1 0 1 3 2
1 3
3 5
6 9
4 4
| 5 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicatie

# Se construieste acoperirea {{$3$}} care are costul {$9$}. Elementul $3$ apartine ambelor intervale date in fisierul de intrare.
Exista si alte acoperiri posibile de exemplu {{$2, 4$}} dar costul acesteia este $11$ care nu este minim.
# Se construieste acoperirea {{$1, 4, 7$}} care are costul {$5$}.

...

== include(page="template/taskfooter" task_id="cover") ==

 

== SmfTopic(topic_id="...") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

1847