Olimpiada Nationala de Informatica Timisoara, 23-30 martie 1997
CLASA  a IX-a
ZIUA 1

Problema 2 (Baze ascunse)
Se dau n numere naturale, x1, x2,..,xn, de cate cel mult 9 cifre. Fiecare numar 
xi este reprezentat intr-o baza bi (2<=bi<= 10), care nu este cunoscuta. Sa se 
determine pentru fiecare numar xi o baza bi astfel incat intervalul  de valori, 
[a,b], in care sunt cuprinse toate cele n numere sa fie de lungime minima. 
Prin lungimea unui interval se intelege diferenta dintre capetele 
intervalului in valoare absoluta.
Intrare:
Datele de intrare se vor citi din fisierul INPUT.TXT cu structura:
n                           - numarul de numere
x1 x2..xn      - numerele (separate printr-un spatiu)
Iesire:
Rezultatele vor fi scrise in fisierul OUTPUT.TXT cu structura:
x1 b1
x2 b2
.....
xn bn
a b
Exemplu:
Pentru fisierul de intrare INPUT.TXT
5
35  27  100  13  19
Iesirea in fisierul OUTPUT.TXT
35  6
27  8
100  4
13  10
19  10
13  23

Nota: Datele de intrare se presupun corecte.
Timp de executie: 10 sec. pentru un test.
================================
program Analizator_Problema_1_Ziua_1_Clasa_IX;
var fi,fo,fa,fr:text;
    si,so,sa,sr:string;
    ja,a,r,ex:array[1..1000] of longint;
    b:array[1..1000] of byte;
    corect:boolean;
    bazecorect,intcorect:boolean;
    i,j,n,m,pct,pct0,pct1:integer;
    k,l,u,i1,i2,rd,mine,maxe:longint;

procedure eroare(st:string);
 begin
  writeln('EROARE : ',st);
 end;

procedure verificabaze;
 begin
  mine:=maxlongint;
  maxe:=0;
  for i:=1 to n do { Testare numar nu se poate reprez. in baza data }
   begin
    if (r[i]<2) or (r[i]>10) or (a[i]<0)
     then begin
      eroare('Baza <2 sau >10 sau numar negativ !');
      bazecorect:=false;
     end else begin
      k:=a[i];
      l:=0;
      u:=1;
      while k>0 do
       begin
        if k mod 10 >= r[i] then
           begin
            writeln('EROARE : Numarul ',a[i],' are cifre mai mari decat baza ',r[i]); { Cifra < baza }
            bazecorect:=false;
           end;
        l:=l+(k mod 10)*u; { Calculez nr. in baza data (l) }
        u:=u*r[i];
        k:=k div 10;
       end;
      if l>maxe then maxe:=l;
      if l<mine then mine:=l;
      if (l<i1) or (l>i2) then
       begin
        writeln('EROARE : Numarul ',l,' nu este in intervalul dat !!!'); { Numar in interval }
        intcorect:=false;
       end;
      j:=1;
      while (j<=n) and ((ex[j]=1) or (ja[j]<>a[i])) do j:=j+1;
      if j<=n then ex[j]:=1;
     end;
    end;
   j:=0;
   for i:=1 to n do if ex[i]=0 then j:=j+1;
   if j>0 then
    begin
     eroare('Unele numere nu se gasesc in raspuns');
     bazecorect:=false;
    end;
  if maxe-mine<>rd then
   begin
    eroare('Bazele gasite nu au intrval minim !');
    bazecorect:=false;
   end;
 end;

begin
si:=paramstr(1);
so:=paramstr(2);
sa:=paramstr(3);
sr:=paramstr(4);
writeln(si,' ',so,' ',sa,' ',sr);
assign(fi,si);
reset(fi);
assign(fo,so);
reset(fo);
assign(fa,sa);
reset(fa);
assign(fr,sr);
rewrite(fr);
corect:=true;
intcorect:=true;
bazecorect:=true;
if eof(fo) then
 begin
  eroare('Fisier GOL !!!');
  intcorect:=false;
  bazecorect:=false;
 end;
readln(fi,n);
for i:=1 to n do read(fi,ja[i]);
for i:=1 to n do
 begin
  if eoln(fo) then
   begin
    eroare('Fisier incomplet !!!');
    bazecorect:=false;
   end;
  readln(fo,a[i],r[i]);
 end;
if eoln(fo) then
 begin
  eroare('Fisier incomplet la interval !!!');
  intcorect:=false;
 end;
pct:=0;
readln(fo,i1,i2);
readln(fa,rd);
readln(fa,pct0);
readln(fa,pct1);
intcorect:=true;
if rd<i2-i1 then
 begin
  eroare('Diferenta este mai MARE !!!');
  intcorect:=false;
 end;
if rd>i2-i1 then
 begin
  eroare('Diferenta este mai MICA !!!');
  intcorect:=false;
 end;
if (i1<=0) or (i2<=0) then
 begin
  intcorect:=false;
  eroare('Interval cu nr negative !');
 end;
verificabaze;
pct:=0;
if intcorect then
 begin
  writeln('Interval corect   O.K.');
  pct:=pct+pct0;
 end;
if bazecorect then
 begin
  writeln('Baze corecte   O.K. ');
  pct:=pct+pct1;
 end;
write(fr,pct);
readln;
close(fi);
close(fo);
close(fa);
close(fr);
end.
===============================
program Problema_2_Clasa_IX_Ziua_1;
type tipa=array[1..9] of byte;
     tip=record
       n10:longint;
       baza:byte;
       nr:integer;
       rep:tipa;
      end;
var i,j,l,n,m,max,ib,ie:integer;
    k,min:longint;
    fi,fo:text;
    a:array[1..1000] of tip;
    ap:array[1..1000] of byte;
    tr:tipa;
    sw:boolean;

begin
assign(fi,'INPUT.TXT');
reset(fi);
assign(fo,'OUTPUT.TXT');
rewrite(fo);
readln(fi,n);
m:=0;
for i:=1 to n do
 begin
  read(fi,k);
  m:=m+1;
  for j:=1 to 9 do
   begin
    a[m].rep[j]:=k mod 10;
    k:=k div 10;
   end;
  max:=2;
  for j:=1 to 9 do if a[m].rep[j]+1>max then max:=a[m].rep[j]+1;
  for j:=max to 10 do
   begin
    a[m+j-max].nr:=i;
    a[m+j-max].baza:=j;
    a[m+j-max].rep:=a[m].rep;
    a[m+j-max].n10:=0;
    k:=1;
    for l:=1 to 9 do
     begin
      a[m+j-max].n10:=a[m+j-max].n10+a[m].rep[l]*k;
      k:=k*j;
     end;
   end;
  m:=m+10-max;
 end;
sw:=true;
while sw do
 begin
  sw:=false;
  for i:=1 to m-1 do if a[i].n10>a[i+1].n10 then
   begin
    sw:=true;
    k:=a[i].nr;
    a[i].nr:=a[i+1].nr;
    a[i+1].nr:=k;
    k:=a[i].n10;
    a[i].n10:=a[i+1].n10;
    a[i+1].n10:=k;
    j:=a[i].baza;
    a[i].baza:=a[i+1].baza;
    a[i+1].baza:=j;
    tr:=a[i].rep;
    a[i].rep:=a[i+1].rep;
    a[i+1].rep:=tr;
   end;
 end;
min:=MaxLongInt;
for i:=1 to m do
 begin
  j:=i;
  for k:=1 to n do ap[k]:=0;
  k:=0;
  while (k<n) and (j<=m) do
   begin
    if ap[a[j].nr]=0 then
     begin
      ap[a[j].nr]:=1;
      k:=k+1;
     end;
    j:=j+1;
   end;
  if (k=n) and (a[j-1].n10-a[i].n10<min) then
   begin
    min:=a[j-1].n10-a[i].n10;
    ib:=i;
    ie:=j-1;
   end;
 end;
for i:=1 to n do
 begin
  j:=ib;
  while a[j].nr<>i do j:=j+1;
  k:=9;
  while a[j].rep[k]=0 do k:=k-1;
  for l:=k downto 1 do write(fo,a[j].rep[l]);
  writeln(fo,' ',a[j].baza);
 end;
writeln(fo,a[ib].n10,' ',a[ie].n10);
close(fi);
close(fo);
end.
--------------------------------
program Problema_2_Clasa_IX_Ziua_1;
type tipa=array[1..9] of byte;
     tip=record
       n10:longint;
       baza:byte;
       nr:integer;
       rep:tipa;
      end;
var i,j,l,n,m,max,ib,ie:integer;
    k,min:longint;
    fi,fo:text;
    a:array[1..1000] of tip;
    ap:array[1..1000] of byte;
    tr:tipa;
    sw:boolean;
    st:string;

begin
write('* = ');
readln(st);
assign(fi,'INPUT.'+st);
reset(fi);
assign(fo,'OUTPUT.'+st);
rewrite(fo);
readln(fi,n);
m:=0;
for i:=1 to n do
 begin
  read(fi,k);
  m:=m+1;
  for j:=1 to 9 do
   begin
    a[m].rep[j]:=k mod 10;
    k:=k div 10;
   end;
  max:=2;
  for j:=1 to 9 do if a[m].rep[j]+1>max then max:=a[m].rep[j]+1;
  for j:=max to 10 do
   begin
    a[m+j-max].nr:=i;
    a[m+j-max].baza:=j;
    a[m+j-max].rep:=a[m].rep;
    a[m+j-max].n10:=0;
    k:=1;
    for l:=1 to 9 do
     begin
      a[m+j-max].n10:=a[m+j-max].n10+a[m].rep[l]*k;
      k:=k*j;
     end;
   end;
  m:=m+10-max;
 end;
sw:=true;
while sw do
 begin
  sw:=false;
  for i:=1 to m-1 do if a[i].n10>a[i+1].n10 then
   begin
    sw:=true;
    k:=a[i].nr;
    a[i].nr:=a[i+1].nr;
    a[i+1].nr:=k;
    k:=a[i].n10;
    a[i].n10:=a[i+1].n10;
    a[i+1].n10:=k;
    j:=a[i].baza;
    a[i].baza:=a[i+1].baza;
    a[i+1].baza:=j;
    tr:=a[i].rep;
    a[i].rep:=a[i+1].rep;
    a[i+1].rep:=tr;
   end;
 end;
min:=MaxLongInt;
for i:=1 to m do
 begin
  j:=i;
  for k:=1 to n do ap[k]:=0;
  k:=0;
  while (k<n) and (j<=m) do
   begin
    if ap[a[j].nr]=0 then
     begin
      ap[a[j].nr]:=1;
      k:=k+1;
     end;
    j:=j+1;
   end;
  if (k=n) and (a[j-1].n10-a[i].n10<min) then
   begin
    min:=a[j-1].n10-a[i].n10;
    ib:=i;
    ie:=j-1;
   end;
 end;
for i:=1 to n do
 begin
  j:=ib;
  while a[j].nr<>i do j:=j+1;
  k:=9;
  while a[j].rep[k]=0 do k:=k-1;
  for l:=k downto 1 do write(fo,a[j].rep[l]);
  writeln(fo,' ',a[j].baza);
 end;
writeln(fo,a[ib].n10,' ',a[ie].n10);
close(fi);
close(fo);
end.
==============================
TESTE:
Input 1:
4
19 79 29 39
=======================
Input 2:
5
1101 23 15 21 13
=======================
Input 3:
5
11 101 22 202 33
========================
Input 4
6
7172 7100 1007 777 66007 7
==============================
Input 5
4
100000001 101010011 110111 111111111
=========================================
Iesire 1:
19 10
79 10
29 10
39 10
19 79
========================
Iesire 2:
1101 2
23 5
15 8
21 6
13 10
13 13
========================
Iesire 3:
11 10
101 4
22 5
202 3
33 4
11 20
==========================
Iesire 4:
7172 8
7100 8
1007 8
777 8
66007 8
7 8
7 27655
============================
Iesire 5:
100000001 2
101010011 2
110111 3
111111111 2
257 511
=============================
