Ion Petre, ca oricare adolescent, este pasionat atât de jocuri, cât şi de informatică. Ultimul astfel de joc este acela de a elimina dintr-un text cuvinte astfel încât fiecare cuvânt rămas să fie urmat de un cuvânt care începe cu aceeaşi literă cu care se termină cuvântul precedent. Face excepţie de la această regulă numai ultimul cuvânt.

Cerinţă

Pentru un text dat, se cere să se afişeze numărul de cuvinte din text, apoi numărul minim de cuvinte ce pot fi eliminate astfel încât în textul rămas orice cuvânt (cu excepţia ultimului) să se termine cu aceeaşi literă cu care începe cuvântul următor, iar în final să se afişeze cuvintele din text rămase după eliminare, fiecare cuvânt fiind afişat pe câte o linie.

Date de intrare

Fișierul de intrare text.in conține un text scris pe mai multe linii. Pe fiecare linie se află cuvinte formate din litere mici ale alfabetului latin. Cuvintele sunt despărţite între ele prin exact câte un spaţiu.

Date de ieșire

Fișierul de ieșire text.out va conține pe primele doua linii două numerele x şi y, unde x va fi numărul de cuvinte din text, iar y numărul minim de cuvinte ce trebuie eliminate. Pe liniile următoare se vor afişa, în ordine, cuvintele rămase după eliminarea celor y cuvinte, câte un cuvânt pe o linie.

Restricții și precizări

Numărul de cuvinte din text este maximum 20000.
Lungimea maximă a unui cuvânt este 20.
Fiecare linie de text din fişierul de intrare are cel mult 200 de caractere.
În fişier pot exista rânduri goale.
Se acordă 10% din punctaj pentru determinarea corectă a numărului de cuvinte din text.
Se acordă 40% din punctaj pentru rezolvarea corectă a primelor două cerinţe.
Pentru rezolvarea corectă a tuturor cerinţelor se acordă tot punctajul.

Exemplu

text.in

pentru ca nu are 

timp ion spune ca nu urmareste nici
emisiuni interesante si evident nici altfel
de

emisiuni

text.out

19
13
ion
nu
urmareste
emisiuni
interesante
evident

Explicație

Din întregul text care este format din 19 cuvinte se elimină 13 cuvinte şi se obţin, în ordine, cuvintele: ion, nu, urmareste, emisiuni, interesante, evident.

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

const fi='text.in';fo='text.out';
var cuv:array[0..20000]of string[20];
    l,p:array[0..20000]of integer;
    lmax,pmax:array['a'..'z']of integer;
    ncuv,lsol,psol:integer;
    lit:char;
procedure citire;
var f:text;
    s:string;
    i:byte;
begin
    assign(f,fi);reset(f);
    ncuv:=0;
    while not seekeof(f) do begin
        readln(f,s);
        if s='' then continue;
        while s[1]=' ' do delete(s,1,1);
        while s[length(s)]=' ' do delete(s,length(s),1);
        i:=pos(' ',s);
        while i<>0 do begin
              inc(ncuv);
              cuv[ncuv]:=copy(s,1,i-1);
              delete(s,1,i);
              i:=pos(' ',s)
        end;
        inc(ncuv);cuv[ncuv]:=s
    end;
    close(f)
end;
procedure dinamica;
var i:integer;
begin
  for i:=1 to ncuv do begin
      lit:=cuv[i][1];
      l[i]:=lmax[lit]+1;
      p[i]:=pmax[lit];
      lit:=cuv[i][length(cuv[i])];
      if l[i]>lmax[lit] then begin
        lmax[lit]:=l[i];
        pmax[lit]:=i
      end
  end;
  lsol:=0;
  for lit:='a' to 'z' do
      if lmax[lit]>lsol then begin
        lsol:=lmax[lit];
        psol:=pmax[lit]
      end
end;
procedure scriere;
var f:text;
    i:integer;
begin
   assign(f,fo);rewrite(f);
   writeln(f,ncuv,' ',ncuv-lsol);
   i:=psol;
   while p[i]<> 0 do begin
     l[p[i]]:=i;
     i:=p[i];
   end;
   while i<>psol do begin
        write(f,cuv[i],' ');
        i:=l[i]
   end;
   writeln(f,cuv[psol]);
   close(f)
end;
begin
  citire;
  dinamica;
  scriere
end.

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 #1093 Text

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