La firma de publicitate „Catchy” s-au primit N comenzi pentru realizarea de bannere publicitare (acestea au fost numerotate de la 1 la N). Angajații firmei au observat că se poate economisi foarte mult material dacă refolosesc cuvinte care au fost scrise pe bannere publicitare mai vechi, care au fost deja folosite, au fost recuperate şi au fost depozitate în magazia firmei. Acest lucru este posibil, deoarece ei folosesc întotdeauna acelaşi font, aceeaşi culoare şi aceeaşi dimensiune pentru textele scrise pe bannere. În magazia firmei sunt depozitate K bannere vechi. Cuvintele de pe acestea pot fi decupate integral şi reasamblate pentru a forma textul noilor bannere comandate. Caracterele speciale care separă cuvintele nu vor fi refolosite, pentru că nu este rentabil. Pentru că își doresc să fie cât mai eficienți, ei vor realiza iniţial dintre bannerele comandate doar un singur banner pentru care textul este format numai din cuvinte care se află deja scrise pe bannerele depozitate în magazie. Dacă există mai multe astfel de bannere, vor alege un banner pentru care numărul de exemplare identice ce pot fi realizate este maxim. Şi dacă şi în acest caz există mai multe bannere posibile, se va realiza bannerul cu numărul de ordine cel mai mic.

Cerința

Cunoscând textele scrise pe cele K bannere depozitate în magazia firmei, precum și textele care trebuie să fie scrise pe cele N bannere nou comandate, scrieţi un program care să determine bannerul care urmează să fie realizat, în condiţiile descrise în enunţul problemei.

Date de intrare

Pe prima linie a fișierului catchy.in se află numărul natural K reprezentând numărul de bannere din magazie. Pe următoarele K linii sunt scrise textele bannerelor aflate în magazia firmei, câte un text pe o linie. Pe a treia linie este scris un număr natural N reprezentând numărul de bannere noi. Pe următoarele N linii sunt scrise textele de pe bannerele noi, câte un text pe o linie.

Date de ieșire

Fișierul de ieşire catchy.out va conţine două linii. Pe prima linie va fi scris numărul de ordine al bannerului ce va fi realizat. Pe a doua linie va fi scris numărul maxim de exemplare identice ce pot fi realizate din acest banner.

Restricții și precizări

1 ≤ k, n ≤ 150;
Textul scris pe orice banner este nevid şi are cel mult 1500 de caractere cu coduri ASCII cuprinse între 32 şi 127;
Caracterele : , : ; ) ( . ? ! > < } { şi spaţiul sunt considerate caractere speciale, deoarece sunt separatori;
Un cuvânt este format dintr-o succesiune nevidă de maxim 25 de caractere diferite de separatori;
Oricare două cuvinte succesive în text sunt separate de unul sau mai mulţi separatori;
Se face distincţie între literele mici şi literele mari;
Pentru datele de test va exista cel puţin un banner care poate să fie realizat;

Exemplu

catchy.in

5
Acum avem multe  de castigat,    "recuperand" aceste cuvinte.
Folosim cuvinte, multe cuvinte, cuvinte din multe bannere folosite.
cuvintele folosite sunt multe valoroase; ele se 'pastreaza'.
Noi avem multe bannere in magazie care pot fi folosite.
Cuvintele sunt: cu litere mari, mici, acelasi font, fara diacritice.
6
dorim s-avem bannere valoroase.
multe cuvinte sunt valoroase.
sunt   multe, multe cuvinte.
Noi,   "recuperand" cuvintele, avem de castigat.
Vasile e de acord
avem multe.

catchy.out

3
2

Explicație

Există 5 bannere în magazie şi avem 6 comenzi pentru bannere noi. Bannerul nou cu numărul de ordine 1 nu poate fi realizat deoarece cuvintele din care este format nu se regăsesc toate în textul bannerelor vechi (cuvintele dorim şi s-avem nu există). De asemenea bannerul nou cu numărul de ordine 6 nu poate fi realizat. Bannerele cu numerele de ordine 2, 3 şi 4 pot fi realizate. Bannerul 2 poate fi realizat într-un singur exemplar, deoarece cuvântul valoroase poate fi decupat o singură dată. Bannerul 3 poate fi realizat în două exemplare:

Bannerul 4 poate fi realizat într-un singur exemplar. Bannerul 6 poate fi şi el realizat în două exemplare, dar deoarece bannerul 3 are numărul de ordine mai mic, îl vom alege pe acesta.

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 Catchy:

#include <fstream>
#include <cassert>
#include <cstring>
#define DMAX 120000
#define LGMAX 26
#define LMAX 1504

using namespace std;
ifstream fin("catchy.in");
ofstream fout("catchy.out");

struct cuvant {char c[LGMAX]; int nr; };
struct icuvant {int poz, nr;};
cuvant D[DMAX];
icuvant B[LMAX/2];
int nrd, K, nrb, nrmax, N, exmax;

char s[LMAX];
char sep[]=":,;)(.?!><}{ ";

int cauta(char *p);
void insereaza (char *p, int poz);
int cautaB(int p);
void insereazaB (int poz, int Bpoz);

int main()
{int i, j, buna, minim, poz, Bpoz;
 char *p;
 fin>>K; fin.get();
 for (i=0; i<K; i++)
      {fin.getline(s,LMAX);
       p=strtok(s,sep);
       while (p)
             {poz=cauta(p);
              if (poz==nrd || strcmp(D[poz].c,p))
                  insereaza(p, poz);
                  else
                  D[poz].nr++;
              p=strtok(NULL,sep);
             }
      }
 fin>>N; fin.get();
 for (i=1; i<=N; i++)
      {fin.getline(s,LMAX);
       p=strtok(s,sep);
       buna=1; nrb=0;
       while (p)
             {poz=cauta(p);
              if (poz==nrd || strcmp(D[poz].c,p))
                  {buna=0; break;}
              Bpoz=cautaB(poz);
              if (Bpoz==nrb || B[Bpoz].poz!=poz)
                  insereazaB(poz, Bpoz);
                  else
                  B[Bpoz].nr++;
              p=strtok(NULL,sep);
             }

        if (buna)
           {minim=DMAX+1;
            for (j=0; j<nrb; j++)
                    if (D[B[j].poz].nr/B[j].nr<minim)
                        minim=D[B[j].poz].nr/B[j].nr;
            if (minim>exmax) {exmax=minim; nrmax=i;}
           }
      }

 fout<<nrmax<<'\n'<<exmax<<'\n';
 fout.close();
 return 0;
}

int cauta(char *p)
{int st=-1, dr=nrd, mijloc;
 while (dr-st>1)
        {
          mijloc=(st+dr)/2;
          if (strcmp(D[mijloc].c, p)<0) st=mijloc;
             else dr=mijloc;
        }
 return dr;
}

void insereaza (char *p, int poz)
{int i;
 for (i=nrd; i>poz; i--) D[i]=D[i-1];
 D[poz].nr=1;
 strcpy(D[poz].c,p);
 nrd++;
}


int cautaB(int p)
{int st=-1, dr=nrb, mijloc;
 while (dr-st>1)
        {
          mijloc=(st+dr)/2;
          if (B[mijloc].poz<p) st=mijloc;
             else dr=mijloc;
        }
 return dr;
}

void insereazaB (int poz, int Bpoz)
{int i;
 for (i=nrb; i>Bpoz; i--) B[i]=B[i-1];
 B[Bpoz].nr=1;
 B[Bpoz].poz=poz;
 nrb++;
}

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 #2565 Catchy

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2565 Catchy 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!

Rezolvare completă PbInfo #2565 Catchy