Page 165 - MATINF Nr. 1

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 165

I 12 (cuvinte). Se consider˘a dou˘a cuvinte formate numai din litere mici ale alfabetului englez,
notate cu c 1 si c 2 . Pentru aceste cuvinte se dores , te s˘a se rezolve dou˘a cerint , e.

Prima cerint , ˘a este legat˘a de verificarea condit , iei de subs , ir de caractere a lui c 2 ˆın c 1 , adic˘a

dac˘a se pot s , terge caractere din c 1 astfel ˆıncˆat s˘a se obt , in˘a c 2 . Dac˘a c 2 este subs , ir ˆın c 1 se dores , te
s , irul de pozit , ii pe care se afl˘a, f˘ar˘a spat , ii. Num˘arul obt , inut se va numi POZ. De exemplu
pentru c 1 =ababcd s , i c 2 =abd, r˘aspunsul este afirmativ, POZ putand fi 126 sau 346. Pozit , iile
ˆın cuvinte sunt 1, 2, 3, . . . .

A doua cerint , ˘a este s˘a se construiasc˘a un nou cuvˆant c 3 cu litere distincte sau cu o singur˘a
liter˘a care s˘a se repete de dou˘a ori, astfel ˆıncˆat s˘a respecte regulile:

1. literele din c 3 trebuie s˘a apar˘a ˆın c 1 sau c 2 ;
2. litera care se repet˘a trebuie s˘a apar˘a ˆın total de cel put , in dou˘a ori ˆın c 1 s , i c 2 .

Cerint , ˘a

Cunoscˆand cele dou˘a cuvinte c 1 s , i c 2 se cere:

1. s˘a se verifice dac˘a c 2 este subcuvˆant ˆın c 1 s , i s˘a se determine cel mai mic num˘ar POZ, ˆın
caz afirmativ, altfel se va afis , a cifra 0;

2. num˘arul de cuvinte c 3 distincte ce se pot construi cu regulile din enunt , , de la a doua
cerint , ˘a.

Date de intrare
Fis , ierul de intrare cuvinte.in cont , ine pe prima linie un num˘ar natural p. Pentru toate testele
de intrare, num˘arul p poate avea doar valoarea 1 sau 2.

Pe linia a doua se afl˘a cuvˆantul c 1 , iar pe linia a treia cuvˆantul c 2 .

Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.

ˆ
In acest caz, ˆın fis , ierul de ies , ire cuvinte.out se va scrie rezultatul de la cerint , a 1, adic˘a 0
sau cel mai mic POZ cu semnificat , ia din enut , .

Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.

ˆ
In acest caz, ˆın fis , ierul de ies , ire cuvinte.out se va scrie num˘arul de la cerint , a 2, modulo
9901.

Restrict , ii s , i preciz˘ari

• 1 ≤ num˘ar caractere din c 1 ≤ 250,
• 1 ≤ num˘ar caractere din c 2 ≤ 250

• Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 20% din punctaj

• k modulo p reprezint˘a restul ˆımp˘art , irii ˆıntregi a lui k la p