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ă
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.
Scrieţi un program care să genereze toate
anagramele unui cuvânt dat, în ordine lexicografică.
Fişierul de intrare ANAG.IN
conţine pe prima linie cuvântul dat.
Fişierul de ieşire
ANAG.OUT va conţine în ordine anagramele cuvântului dat,
câte una pe linie.
§
Cuvântul dat are cel mult 10 de
litere mici.
§
Cuvântul x=x1x2...xn
precede cuvântul y=y1y2...yn
dacă există un indice k apartinand multimii {1,2,...,n}
astfel încât xi=yi,
pentru oricare i apartine lui {1,2,...,k-1},
iar litera xk
precede în alfabet litera yk.
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.