Page 104 - REVISTA MATINF Nr. 5

˘
104 PROBLEME DE INFORMATICA PENTRU CONCURSURI

Exemplu

codificare.in codificare.out
1 2 4 5 3 Bafta
1 1 0 1 1
Cbfxb

Timp maxim de execut , ie: 0.1 sec./test. Memorie total˘a disponibil˘a 2 MB.

Doru Anastasiu Popescu, Pites , ti

I 69 (permnefixe). Se dau n s , i k dou˘a numere naturale. Prin permutare far˘a puncte fixe
ˆınt , elegem o permutare a mult , imii {1, 2, . . . , n} ˆın care orice element al ei este diferit de pozit , ia
pe care se afl˘a. De exemplu pentru n = 4 permut˘arile (2, 1, 4, 3) s , i (3, 1, 4, 2) nu au puncte fixe.
Dintre toate permut˘arile f˘ar˘a puncte fixe ne intereseaz˘a a k-a permutare a mult , imii ˆın ordine
lexicografic˘a.

Cerint , ˘a
Pentru n s , i k date se cere a k-a permutare f˘ar˘a puncte fixe ˆın ordine lexicografic˘a.

Date de intrare

Fis , ierul de intrare permnefixe.in cont , ine pe prima linie n s , i k separate printr-un spat , iu.

Date de ies , ire
Fis , ierul de ies , ire permnefixe.out va cont , ine pe prima linie a k-a permutare f˘ar˘a puncte
fixe ˆın ordine lexicografic˘a; elementele ei vor fi separate prin cˆate un spat , iu. Dac˘a nu exist˘a o
astfel de permutare se va scrie cifra 0.

Restrict , ii s , i preciz˘ari
• 1 ≤ n ≤ 20
• 1 ≤ k ≤ 200

Exemplu

permnefixe.in permnefixe.out
4 2 2 3 4 1

Timp maxim de execut , ie: 0.1 sec./test. Memorie total˘a disponibil˘a 2 MB.
Ion Alexandru Popescu, Bucures , ti

I 70 (zerouri). Se d˘a n, num˘ar natural. Not˘am cu Nr num˘arul de funct , ii bijective de forma
f : {1, 2, ..., n} → {1, 2, ..., n}.

Cerint , ˘a

Pentru n dat afis , at , i num˘arul de zerouri ˆın care se termin˘a Nr.
Date de intrare

Fis , ierul de intrare zerouri.in cont , ine pe prima linie n.

Date de ies , ire
Fis , ierul de ies , ire zerouri.out va cont , ine num˘arul de zerouri ˆın care se termin˘a Nr.