Fișierul intrare/ieșire afise.in, afise.out Sursă OJI 2007 clasa a 8-a
Autor Adăugată de avatar andreicoman Andrei Coman andreicoman
Timp de execuție pe test 0.05 sec Limită de memorie 1024 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Afise (clasa a 8-a)

Campania electorală s-a terminat de mult, dar zidul din parcul central al orașului în care au fost puse afișele este încă într-o formă dezolantă. Ploile și vântul au acționat și au urâțit și mai mult această zonă pe care altă dată erau afișe frumos colorate. Primăria a decis să se ocupe de această problemă. A format o comisie și a decis realizarea unor panouri reclamă care să ascundă porțiunile deteriorate.

Deoarece fondurile sunt mici s-a decis să fie alocate doar un anumit număr de panouri publicitare care trebuie să ocupe o suprafață cât mai mică posibil. Comisia a primit datele din teren sub forma: lungime zid, câte unități sunt ocupate cu afișe ce trebuie acoperite și care este numărul de panouri pe care le poate folosi. De asemenea se primesc ca date și care sunt unitățile de zid ocupate cu afișe deja deteriorate.

Fiind date lungimea zidului, câte unități sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite și care sunt unitățile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona și câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unități de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităților de zid deteriorate, nu este neapărat necesar să se folosească toate panourile. Numărul de panouri folosite fiind limitat există posibilitatea să fie acoperite și zone din zid care sunt curate.

Date de intrare

Fișierul de intrare afise.in conține pe prima linie 3 valori separate prin câte un spațiu L n k, cu semnificația: L lungimea totală a zidului, n numărul de unități ce urmează a fi acoperite și k numărul maxim de panouri ce pot fi folosite. Pe a doua linie separate prin câte un spațiu sunt n valori x1, x2, ..., xn, unde xi reprezintă unitatea din zid care este acoperită de un afiș vechi. Valorile x1, x2, ..., xn, apar într-o ordine aleatoare.

Date de ieșire

Fișierul de ieșire afise.out conține o singură linie cu două valoari ce reprezintă lungimea minimă totală folosită și numărul de panouri folosite astfel încât toate zonele deteriorate să fie acoperite.

Restricții

  • 0 < L ≤ 1 000
  • 0 < n ≤ L
  • 0 < k ≤ L / 2

Exemplu

afise.in afise.out
25 8 3
3 11 6 4 19 15 20 12
11 3

Explicație

Zidul are lungimea egală cu 25 de unități, iar 8 dintre ele conțin afișe care trebuiesc acoperite cu maxim 3 panouri. Se vor folosi toate cele 3 panouri care vor totaliza 11 unități, acoperind zonele 3-6, 11-15 și 19-20.

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

Indicii de rezolvare

Arată 2 categorii