Rezolvare completă PbInfo #2676 afise

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.

Cerința

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 trei 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 va conține o singură linie cu două valori val Nk, ce reprezintă lungimea minimă totală folosită și numărul de panouri folosite astfel încât toate zonele deteriorate să fie acoperite.

Restricții și precizări

  • 0 < L ≤ 1000
  • 0 < n ≤ L
  • 0 < k ≤ L / 2

Exemplul 1:

afise.in

25 8 3
3 11 6 4 19 15 20 12

afise.out

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 maximum 3 panouri. Se vor folosi toate cele 3 panouri care vor totaliza 11 unități, acoperind zonele 3-6, 11-15 și 19-20.

Caracterul * reprezintă unitățile de zid acoperite de afișe vechi

Exemplul 2:

afise.in

10 4 6
7 3 8 1

afise.out

4 3

Explicație

Sunt suficiente 3 panouri care totalizează 4 unități acoperind zonele 1, 3 şi 7-8.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema afise:

#include <fstream>
#define InFile  "afise.in"
#define OutFile "afise.out"
#define Max 1001
using namespace std;

struct Afis
{
    int bed, alb;
};

Afis S[Max];
int L, N, K, M;
int Viz[Max];

void Read()
{
  int x, bed, alb, i;
  ifstream in(InFile);

  in>>L>>N>>K;

  for(i=1; i<=N; i++)
    { in>>x; Viz[x]=1; }
  // marcate zonele ce trebuie acoperite
  in.close();

  i=1;
  bed = alb = 0;
  while(!Viz[i] && i<=L) i++;
  while(i <= L)
   { while(Viz[i] && i<=L)  { bed++; i++; }
     while(!Viz[i] && i<=L) { alb++; i++; }
     // determin lungimea zonelor rele urmate de zone ok
     M++;
     S[M].bed = bed;
     S[M].alb = alb;
     bed = alb = 0;
   }
   M--;
}

// ordonare crescatoare dupa zonele ok

int poz(int p, int u)
{
  int st, dr;
  st = p; dr=u;
  Afis aux=S[p];
  while(st < dr)
    { while(st<dr && aux.alb <= S[dr].alb) dr--;
      S[st]=S[dr];
      while(st<dr && aux.alb >= S[st].alb) st++;
      S[dr]=S[st];
    }
  S[st]=aux;
  return st;
}

void Quik(int p, int u)
{
  int m=poz(p,u);
  if(p<m) Quik(p,m-1);
  if(m<u) Quik(m+1,u);
}

void Write()
{
  int i, nK, St;
  ofstream out(OutFile);
  St=nK=0;
  M++;
  for(i=1; i<=M; i++) St+=S[i].bed;
  //zone care obligatoriu trebuie acoperite

  nK = M;
  if(M>K) { i = 1;
        while(nK>K && i<=M)
          { St += S[i].alb; i++; nK--; }
        // folosesc spatiile albe pentru a reduce numarul de panouri
      }
  out<<St<<" "<<nK<<"\n";
  out.close();
}

int main()
{
  Read();
  Quik(1, M);
  Write();

  return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2676 afise

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2676 afise de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!