
IX.1. GENERARE. Fie n un numar natural strict pozitiv. Sa se determine toate
numerele naturale N, scrise in baza 10 sub forma a1a2...an cu ai  {1,2},
i=1..n, si care se divid la 2.
Intrare. Se va citi de la tastatura numarul n.
Iesire. Se va afisa pe ecran:
- pe prima linie, numarul k de numere care satisfac conditia;
- urmeaza k linii, fiecare continand cate un numar care satisface conditia
ceruta.



IX.2. URBANISM. Primarul Iasiului, asaltat de numeroasele cereri de nfiintare
de filiale de banci (b), restaurante (r) si cazinouri (c), decide sa solicite
Serviciului de Urbanism sa nu aprobe dechiderea respectivelor localuri decat
daca sunt satisfacute conditiile:
- nu trebuie sa existe pe o strada nici o secventa de tip b r c (consecutiv,
in ordinea aceasta);
- nu trebuie sa existe repetitii imediate ale aceleiasi secvente (de genul
b r b r sau c r c b r c b).
Scrieti, in ajutorul Serviciului Urbanism, un program care:
a)
- sa citeasca de la tastatura o prima linie continand numarul L de localuri si
de pe linia urmatoare, secventa de L litere semnificand o succesiune propusa a
tipurilor de localuripe o anumita strada;
- sa afiseze pe ecran fie decizia propunere corecta fie, pe o prima linie, 
numarul k de incalcari ale celor doua reguli si apoi k linii, fiecare 
continand cate un subsir gasit care incalca regulile.
b)
- sa genereze pe ecran cat mai multe secvente corecte (exista un numar
finit!), sub forma: pe o prima linie numarul de secvente gasite, apoi pe cate
o linie fiecare secventa gasita.

-------------------

X.1. TRANSPORTUL IN COMUNA. In comuna Ciudad de Townsvillestadt, intre statiile
de transport in comun se poate calatori cu tramvaiul (t),cu autobuzul (a), cu
troleibuzul (b) sau cu maxi-taxi (m), fiecare la alt pret. Vom numi drumul
dintre doua statii consecutive drum elementar, pe fiecare drum elementar se
poate circula doar cu unele dintre mijloacele de transport si la anumite pre-
turi. Se cere sa se determine o multime de drumuri elementare si mijloacele
de transport de utilizat astfel incat orice statie sa poata fi atinsa pe dru-
murile elementare selectate, iar suma costurilor folosirii mijloacelor de
transport alese pe drumurile elementare sa fie minima.
  Intrarea se va face de pe un fisier al carui nume se citeste de la tastatura
si care contine K+1 linii:
- pe prima linie, numarul K de statii;
- pe fiecare linie i din cele K urmatoare, o structura de tipul:
i,(1,t,4,a,3),(3,b,2,m,5),(6,t,3,a,4,m,6)
cu semnificatia: din statia i se poate ajunge pe drumuri elementare la statiile: 
1-cu tramvaiul, costand 4 dolire, sau cu autobuzul, costand 3 dolire; 
3-cu troleibuzul, costand 2 dolire sau cu maxi-taxi, costand 5 dolire; 
6-cu tramvaiul, costand 3 dolire, cu autobuzul, costand 4 dolire, sau cu maxi-taxi,
costand 6 dolire.
  Iesirea se va face intr-un fisier al carui nume se citeste de la tastatura si
care contine o singura inregistrare, cu structura de tipul:
(1,2,t),(1,3,b),(3,4,a),(3,5,t),(5,6,m),64
semnificand faptul ca solutia aleasa contine drumuri elementare care leaga
statiile 1 cu 2 (tramvai), 1 cu 3 (troleibuz), 3 cu 4 (autobuz), 3 cu 5 (tram-
vai), 5 cu 6 (maxi-taxi), costul acestor drumuri elementare cu aceste mijloace
de transport fiind 64.

X.2. DEPLASARI. Consideram urmatoarele operatii elementare asupra sirurilor de
biti, ilustrate prin efectul lor asupra sirului 1101:
1.deplasarea logica stanga cu o pozitie: 0110 (sirul se deplaseaza cu o pozi-
  tie spre stanga, bitul cel mai semnificativ se pierde iar cel mai putin sem-
  nificativ devine 0);
2.deplasarea logica dreapta cu o pozitie: 0101 (sirul se deplaseaza cu o pozi-
  tie spre dreapta, bitul cel mai semnificativ devine 0 iar cel mai putin sem-
  nificativ se pierde);
3.deplasarea aritmetica stanga cu o pozitie: 1110 (analog cu 1., dar bitul cel
  mai semnificativ isi pastreaza valoarea);
4.deplasarea aritmetica dreapta cu o pozitie: 1001 (analog cu 2., dar bitul
  cel mai semnificativ isi pastreaza valoarea);
5.deplasarea circulara stanga cu o pozitie: 0111 (analog cu 1., dar valoarea
  bitului celui mai semnificativ este adusa pe ultima pozitie);
6.deplasarea circulara dreapta cu o pozitie: 1101 (analog cu 2., dar valoarea
  bitului celui mai putin semnificativ este adusa pe prima pozitie).
Dandu-se doua siruri de biti de lungime egala, sa se decida daca al doilea
poate fi obtinut din primul prin prin aplicari succesive ale acestor sase ope-
ratii elementare si, in caz afirmativ, sa se gaseasca o succesiune de astfel
de operatii.
Intrarea se face de pe un fisier cu numele citit de la tastatura si cu struc-
tura: primul sir pe prima linie, al doilea sir pe a doua linie.
Iesirea se face pe un fisier al carui nume se citeste de la tastatura si care
are structura: pe prima linie numarul de aplicari ale operatiilor elementare,
a doua inregistrare continand succesiunea acestora, dupa numerotarea de mai
sus. Daca nu exista solutie, atunci fisierul contine doar linia-mesaj:
Nici o solutie
Exemplu. Intrare:
11001100
10001100
Iesire:
4
2,2,2,6

-------------------


        XI 1. PROBLEMA PIRAMIDEI
              ^^^^^^^^^^^^^^^^^^

    Recent s-a descoperit o proprietate interesanta legata de piramidele
din Egipt si anume ca blocurile de piatra de pe fetele laterale din care sunt
construite aceste piramide sunt etichetate cu numere naturale strict pozitive
astfel incat un bloc de pe un nivel dat, etichetat cu numarul K se sprijina pe
doua jumatati de blocuri ale nivelului precedent etichetate cu K1, respectiv
K2, astfel incat K = K1+K2; etichetele unui nivel sunt distincte. Din cauza
intemperiilor, nu se cunoaste decat eticheta blocului situat pe primul nivel
(cel mai de sus) si numarul de niveluri. Precizati (prin program) toate modu-
rile de etichetare a celorlalte blocuri.

Exemplu: Daca numarul de nivele este 4 si eticheta blocului din varful pirami-
dei este 22, atunci iata doua astfel de piramide:
      22                22
     8 14              9 13
    3 5 9             3 6 7
   1 2 3 6           1 2 4 3
  Intrarea se va face citind de la tastatura N si E, unde N reprezinta numarul
de nivele iar E este eticheta blocului din varful piramidei.

  Iesirea se va face intr-un fisier text al carui nume se citeste de la tasta-
tura; fisierul va avea urmatoarea structura:
..
i m1 m2 ...mi
..
unde i este numarul nivelului iar numerele mj reprezinta succesiunea etichete-
lor blocurilor de pe acest nivel.





        XI 2. RADICALI CU RIGLA SI COMPASUL
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    Se stie ca folosind teorema lui Pitagora, se pot construi segmente ce
au lungimea sqrt(n), (n fiind numar natural), pornind doar cu segmente de
lungimi numere naturale.

Exemple: Pentru a obtine un segment de lungime sqrt(2) putem considera
doua segmente de lungime 1.
Pentru a obtine un segment de lungime sqrt(7) putem avea pasii:
  (1 ,2, sqrt5), (1, 1, sqrt2), (sqrt5, sqrt2, sqrt7) sau (1, 1, sqrt2), (sqrt2, sqrt7, 3) etc.

    Sa se scrie un program, care avand la intrare n un numar natural,
determina numarul minim de pasi (echivalent- de aplicari ale teoremei lui
Pitagora) pentru obtinerea unui segment de lungime sqrtn, avand la dispozitie
segmente de orice lungime numar natural si segmentele construite la pasii
anteriori.

       Intrarea se va face citind de la tastatura numarul n.
       Iesirea se va face intr-un fisier al carui nume se citeste de la tasta-
tura si care contine m pe prima linie (numarul de pasi), iar pe urmatoarele m
linii structuri de tipul:
(a, b, c)
unde sqrt(a)+sqrt(b)=sqrt(c).
Structura (a, b, c) de pe ultima linie trebuie sa aiba unul din termeni
egali cu sqrt(n).



---------------------


XII 1.                  CAI ALBI SI NEGRI

    Se da tabla 3*3 similar celei de sah, avand in cele patru colturi cte 
un cal, care se poate muta la fel ca la sah. Cei doi cai albi, notati
mai jos cu A, sunt Albu' si Altu', iar cei doi negri, notati cu N, sunt Nera
si Nerva. Configuratia initiala fiind:
               -------------
               | A |   | A |
               -------------
               |   |   |   |
               -------------
               | N |   | N |
               -------------
se cere sa se listeze cel putin dua siruri minimale de muatari  in urma
caror se ajunge la configuratia finala:
               -------------
               | N |   | N |
               -------------
               |   |   |   |
               -------------
               | A |   | A |
               -------------
    Iesirea se va face intr-un fisier text al carui nume se citeste
de la tastatura; fisierul va avea uramtoarea strtura:
..
i, m1 m2 ...mr
..
unde i este numarul de ordine al solutiei, iar fiecare mj repreznta o
mutare din sirul solutie sub forma:
(c,p)
c desemneaza calul ce se mta, iar p pozita in care se ajunge in urma
mutari.

XII 2.          CONCURSUL OLIMPICILOR

    Cei K elevi din tabara olimpicilor informaticieni de la
Costinesti doresc sa e intreaca intr-un campionat pe nisip de tras la
franghie,inP  echipe. Cunoscand greuatile celor K elevi date intr-un vector L,sa se
formeze cele P echipe din indicii corespunzator din L, astfel ca echipele
sa fiecat mai echilibrate.
Intrarea se va face intr-un fisier al carui nume se citeste de la
tastatura si care contine pe prima linie K si P sub forma:
K,P.
iar pe urmatoarea linie, vectorul L sub forma:
G1, G2, ..., Gk.
Iesirea se va face ntr-un fisier al crui nume se citeste de la tastatur si
care contine P linii, fiecare linie avand structura:
i1, i2, ...,im
constnd din indicii celor m membri ai echipei respective.

--------------------

