Olimpiada Naţională de Informatică pentru Gimnaziu

Clasa a VIII-a

Problema 1 – Şir

Se consideră următorul şir, construit astfel încât fiecare element al lui, cu excepţia primului, se obţine din cel precedent: 1, 11, 21, 1211, 111221, ...

Termenii din şir sunt numerotaţi începând cu 1.

Cerinţă

Dat n, un număr natural, să se determine cel de-al n-lea termen din şirul dat.

Date de intrare

Din fişierul text SIR.IN se citeşte numărul natural n.

Date de ieşire

Pe prima linie a fişierului text SIR.OUT se va scrie al n-lea termen al sirului.

Restricţii

· 4 <= n <= 35

· numărul de cifre ale unui termen nu depăşeşte 17000.

Exemple

SIR.IN	SIR.OUT
4	1211

SIR.IN	SIR.OUT
5	111221

Timp maxim de execuţie/test: 1 secundă

Problema 2 – Anagrame

Se dă un cuvânt format numai din litere mici.

Numim anagramă un cuvânt format din literele cuvântului dat, schimbând eventual ordinea literelor.

De exemplu o anagramă a cuvântului tamara este cuvântul armata. Evident, un cuvânt poate fi considerat o anagramă a lui însuşi.

Cerinţă

Scrieţi un program care să genereze toate anagramele unui cuvânt dat, în ordine lexicografică.

Date de intrare

Fişierul de intrare ANAG.IN conţine pe prima linie cuvântul dat.

Date de ieşire

Fişierul de ieşire ANAG.OUT va conţine în ordine anagramele cuvântului dat, câte una pe linie.

Restricţii şi precizări

§ Cuvântul dat are cel mult 10 de litere mici.

§ Cuvântul x=x₁x₂...x_n precede cuvântul y=y₁y₂...y_n dacă există un indice k apartinand multimii {1,2,...,n} astfel încât x_i=y_i, pentru oricare i apartine lui {1,2,...,k-1}, iar litera x_k precede în alfabet litera y_k.

Exemplu

ANAG.IN	ANAG.OUT
Ana	Aan ana naa

Timp maxim de execuţie: 1 secundă/test (pe un calculator Duron 850 MHz).

Notă:

Timp de lucru: 3 ore. Fiecare problemă se punctează cu 100 puncte.