Page 15 - MATINF Nr. 1

Concursul de Informatic˘a Programming Day 15

anagrama.in anagrama.out Explicat , ie
2 4 p = 2
mara Cuvintele anagram˘a cu C ˆın
vara aram dica rama aarm rama T sunt aram, rama, aarm s , i
rama. Num˘arul lor este 4.

Timp maxim de execut , ie: 0.2 secunde/test.

Memorie total˘a disponibil˘a 2 MB, din care 1 MB pentru stiv˘a.
Doru Anastasiu Popescu, Costel B˘alc˘au, Pites , ti, Gabriel Boroghin˘a, Bucures , ti
Solut , ie
Cerint , a 1

1. Se citesc C s , i T.

2. Nr = 0.
3. Se determin˘a ˆın i pozit , ia primului spat , iu ˆın T. Dac˘a T are un singur cuvˆant, atunci i
este num˘arul de litere.
ˆ
4. Pentru fiecare vocal˘a se verific˘a dac˘a se g˘ases , te atˆat ˆın C, cˆat s , i ˆın T 0 T 1 . . . T i−1 . In caz
afirmativ Nr = Nr + 1.
5. Se afis , eaz˘a Nr.

Cerint , a 2

1. Se construies , te vectorul de frecvent , e al literelor mici pentru cuvˆantul C, fie acesta
x = (x 0 , x 1 , . . . , x 25 ), x i este num˘arul de aparit , ii a celei de-a i − a liter˘a din alfabet ˆın C.

2. Nr = 0.

3. Pentru fiecare cuvˆant din T se determin˘a vectorul de frecvent , e al literelor mici: y =
(y 0 , y 1 , . . . , y 25 ). Dac˘a x s , i y au aceleas , i componente atunci Nr = Nr + 1.
4. Se afis , eaz˘a Nr.

Problema 2 – cuburi
Ionic˘a are un sac plin cu cuburi, numerotate cu 1, 2, . . . , N s , i M cutii numerotate cu 1, 2, . . . , M
ˆın care ˆıncap x 1 , x 2 , . . . , x M cuburi. Din p˘acate cutiile nu sunt suficiente pentru a introduce
ˆ
cuburile din sac s , i mai r˘amˆan cuburi neintroduse. In fiecare zi dup˘a ce se joac˘a cu cuburile le
introduce ˆın cutii la capacitate maxim˘a s , i ce r˘amˆane le pune ˆın sac. Dup˘a multe zile de joac˘a s , i
as , ezare a cuburilor ˆın cutii, Ionic˘a se ˆıntreb˘a ˆın cˆate moduri diferite poate as , eza cuburile ˆın
cutii, s , tiind c˘a ordinea cuburilor dintr-o cutie nu are important , ˘a.
Cerint , ˘a
Cunoscˆand numerele N, M s , i capacit˘at , ile cutiilor, se cere:

1. num˘arul maxim de cuburi pe care le poate pune ˆın [M/2] cutii;
2. ˆın cˆate moduri diferite se pot as , eza cuburile ˆın cutii, s , tiind c˘a ordinea cuburilor ˆın cutii
nu are important , ˘a.

Date de intrare
Fis , ierul de intrare cuburi.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.