Atenție! Aceasta este o versiune veche a paginii., scrisă la 2012-10-31 05:59:14.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire barnrepair.in, barnrepair.out Sursă USACO
Autor autor necunoscut Adăugată de avatar theo Cotet Teodor Mihai theo
Timp de execuție pe test 0.05 sec Limită de memorie 1024 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Barnrepair

Din cauza unei nopti furtunoase fermierului JOHN i s-au rupt portile unor tarcuri de vaci. Din fericire, multe dintre vacile lui erau in concediu, asadar nu toate tarcurile erau ocupate.

Tarcurile sunt asezate in linie dreapta, unele dintre ele avand vaci, altele nu.

Fermierul JOHN trebuie sa faca rapid rost de niste placi de acoperire pentru a inchide vacile ramase. Noul lui furnizor de cherestea ii poate asigura placi de orice dimensiune doreste JOHN, dar intr-un numar limitat. Bineinteles JOHN, fiind econom, doreste sa minimizeze numarul de placi folosite.

Date de intrare

Fisierul de intrare barnrepair.in contine pe prima linie trei numere intregi:

M – numerul total de placi pe care fermierul le poate cumpara (1 <= M <= 50)
S – numerul de tarcuri (1 <= S <= 200)
C – numarul de vaci din tarcuri (1 <= C <= S)

Urmatoarele C linii vor contine cate o valoare reprezentand numarul de ordine al unui tarc ocupat.

Date de ieșire

Afisati numarul minim de tarcuri care trebuiesc blocate astfel incat toate vacile sa fie la adapost(blocate), folosind maxim M placi

Restricții

  • 1 ≤ M ≤ 50
  • 1 ≤ S ≤ 200
  • 1 ≤ C ≤ S

Exemplu

barnrepair.in barnrepair.out
4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43
25

Explicație

Se acopera portiunile 3-8, 14-21, 25-31 ,40-43 astfel fiind blocate un numar minim de grajduri cu doar 4 placi

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii