Page 6 - MATINF Nr. 13-14

6 D.A. Popescu, C. B˘alc˘au, D. Constantin

2. num˘arul de cuvinte de lungime N formate cu literele alfabetului A, astfel ˆıncˆat s˘a nu
existe dou˘a litere egale pe pozit , ii vecine.

Date de intrare
Pe prima linie a fis , ierului de intrare cuvinte.in se g˘ases , te C, num˘arul corespunz˘ator cerint , ei
ce se va rezolva (1 sau 2). Pe linia a doua se va afla N.
Date de ies , ire
Pe prima linie a fis , ierului de ies , ire cuvinte.out se va afis , a r˘aspunsul la cerint , a cores-
punz˘atoare fis , ierului de intrare.

Restrict , ii s , i preciz˘ari
1. 1 ≤ N ≤ 30000.
2. Dou˘ litere sunt vecine ˆıntr-un cuvˆant dac˘ se g˘asesc pe pozit , ii consecutive.
a
a
a
3. Pentru rezolvarea corect˘ a cerint , ei 1 se vor acorda 20 de puncte.
4. Pentru rezolvarea corect˘a a cerint , ei 2 se vor acorda 80 de puncte.
Exemplu

cuvinte.in cuvinte.out
1 ZYZ
3
2 6
2

Explicat , ii
Ultimul cuvˆant ˆın ordine alfabetic˘a cu N = 3 litere din alfabetul A, ce respect˘a restrict , ia
din cerint , a C = 1, este ZY Z.

a
Cuvintele ce se pot forma cu N = 2 litere din alfabetul A, ce respect˘ restrict , ia din cerint , a
C = 2 sunt XY , XZ, Y X, Y Z, ZX, ZY .
Timp maxim de execut , ie: 0.1 secunde/test.
Memorie total˘ disponibil˘a: 4 MB.
a
Solut , ie

Cerint , a 1 (20 puncte)

Trebuie afis , at urm˘atorul cuvˆant de lungime N: ZY ZY ZY . . .
a
De exemplu, pentru N = 5 se afis , eaz˘ ZY ZY Z
Cerint , a 2 (80 puncte)

Not˘am cu Nr[N] num˘arul de cuvinte de lungime N cu proprietatea impus˘a. Prima liter˘a
poate fi X, Y sau Z, iar pe fiecare din urm˘atoarele N − 1 pozit , ii putem plasa oricare din
cele dou˘a litere diferite de cea de dinainte, deci Nr[N] = 3 · 2 N−1 . Se calculeaz˘a acest produs,
folosind un vector pentru memorarea cifrelor (operat , ii cu numere mari).

De exemplu, pentru N = 2, avem Nr[2] = 6.