TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

stampa.pas    2,493 b      izvorni kod rešenja
stampa.checker.pas    495 b      program za testiranje
stampa.tests.rar    893,273 b      test primeri

zadatak: Štampa

Mika je vlasnik uspešne izdavačke kuće. Posao mu je cvetao dok jednog dana njegov štampar nije zatvorio štampariju zbog nagomilanih dugova rasipničke porodice. Mika je morao da pronađe drugu štampariju pa se obratio svom školskom drugu Joci. Jocina štamparija, međutim, nije savremena, pa se štampa odvija principom zamena na sledeći način: prvo se postavi početno slovo, pa se primeni određen broj koraka takvih da se u svakom koraku primenjuje neka od metoda zamene, kojom se jedno slovom menja nizom slova.

Miki se ovaj način štampe u početku jako svideo, ali je kasnije shvatio da možda ovim načinom ne mogu da se dobiju sve kombinacije parova slova. Pomozite Miki da sazna koje parove susednih slova može da odštampa Jocina štamparija.

Ulaz:

U prvom redu ulaznog tekstualnog fajla stampa.in nalaze se dva prirodna broja, broj zamena N i broj slova u jednoj zameni K. U sledeđih N redova opisane su zamene na sledeći način: prvo slovo u redu je slovo koje se menja, zatim sledi razmak i posle razmaka se nalaze K slova kojima se menja početno slovo. Sva slova su mala slova engleske abecede i važi 1 < N ≤ 10000, 0 < K ≤ 100. U poslednjem, N+2-om redu nalazi se početno slovo.

Izlaz:

U prvi red izlaznog tekstualnog fajla stampa.out upisati X - broj parova susednih slova koja se mogu dobiti na opisani način, a zatim u sledećih X redova upisati parove slova, po jedan par u redu, u leksikografskom poretku.

Primer:

stampa.in          stampa.out
5 2
a bg
g ab
s dr
a ab
b bf
a
    
10
ab
ba
bb
bf
bg
fa
fb
ff
fg
gb
fajl: stampa.pas
{
zadatak: stampa
jezik: pascal
}
program stampa;
type
  TSusedi=array['a'..'z','a'..'z'] of Boolean;
var
  poc,zav,sus:TSusedi;
  s:array[1..10000] of string;
  n,k,i,t,z,j:integer;
  a,b,slovo:char;
  proveren:array['a'..'z'] of Boolean;
  prva:array['a'..'z'] of integer;
  slova:array[1..30] of char;
procedure sort(l,r:integer);
{quicksort}
var
  i,j:integer;
  k,t:string;
begin
  i:=l;
  j:=r;
  k:=s[(i+j) div 2];
  while i<=j do
  begin
    while s[i]<k do inc(i);
    while k<s[j] do dec(j);
    if i<=j then
    begin
      t:=s[i];
      s[i]:=s[j];
      s[j]:=t;
      inc(i);
      dec(j)
    end
  end;
  if i<r then sort(i,r);
  if l<j then sort(l,j)
end;
procedure PostaviSusede(a,b:char);
{glavna procedura, ispituje koji parovi mogu biti susedni}
var
  j:char;
begin
  if  not Sus[a, b] then
  begin
    Sus[a, b] := true;
    for j := 'a' to 'z' do
    if Zav[a, j] then
      postaviSusede(j, b);
    for j := 'a' to 'z' do
    if Poc[b, j] then
      postaviSusede(a, j);
  end
end;
begin
{inicijalizacija}
  for a:='a' to 'z' do
  begin
    proveren[a]:=false;
    prva[a]:=0;
    for b:='a' to 'z' do
    begin
      poc[a,b]:=false;
      zav[a,b]:=false;
      sus[a,b]:=false
    end
  end;
{ucitavanje}
{  assign(input,'stampa.in');
  reset(input);}
  readln(n,k);
  for i:=1 to n do
  begin
    readln(s[i]);
    poc[s[i,1],s[i,3]]:=true;
    zav[s[i,1],s[i,k+2]]:=true
  end;
  readln(slovo);
{  close(input);}
{sortiranje i preprocesiranje}
  sort(1,n);
  prva[s[1,1]]:=1;
  for i:=2 to n do
  if s[i,1]<>s[i-1,1] then
    prva[s[i,1]]:=i;
{ispitivanje slova, prvo je pocetno}
  t:=0;
  z:=1;
  slova[z]:=slovo;
  proveren[slovo]:=true;
  repeat
  inc(t);
  slovo:=slova[t];
  i:=prva[slovo];
  if i>0 then
    while s[i,1]=slovo do
    begin
      for j:=1 to k-1 do
      begin
        PostaviSusede(s[i,2+j],s[i,2+j+1]);
        if not proveren[s[i,2+j]] then
        begin
          inc(z);
          slova[z]:=s[i,2+j];
          proveren[s[i,2+j]]:=true
        end
      end;
      if not proveren[s[i,2+k]] then
        begin
          inc(z);
          slova[z]:=s[i,2+k];
          proveren[s[i,2+k]]:=true
        end;
      inc(i)
    end;
  until t=z;
{konacno prebrojavanje i ispis}
{  assign(output,'stampa.out');
  rewrite(output);}
  t:=0;
  for a:='a' to 'z' do
  for b:='a' to 'z' do
    if sus[a,b] then
    inc(t);
  writeln(t);
  for a:='a' to 'z' do
  for b:='a' to 'z' do
    if sus[a,b] then
    writeln(a,b);
{  close(output)}
end.