Page 12 - MATINF Nr. 3

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

cuvinte.in cuvinte.out Explicat , ie
2 10 p = 2
VARA Lant , urile din tabloul A care sunt anagrame pentru
5 6 cuvˆantul C: VARA, VARA, ARAV, VRAA, AAVR,
VARAXV RAAV, ARAV, AARV, VAAR, RVAA.
MREYAR
EAABAX
TIGDVG
EOGERG

Timp maxim de execut , ie: 0.15 secunde/test.
Memorie total˘a disponibil˘a: 2 MB.
Dimensiunea maxim˘a a sursei: 5 KB

Solut , ie

Pentru prima cerint , ˘a, se parcurge tabloul A s , i se compar˘a fiecare element cu ultima liter˘a
din cuvˆantul C. Dac˘a sunt egale se incrementeaz˘a un contor. Pentru a doua cerint , ˘a se genereaz˘a
toate lant , urile ˆın paralel cu s , tergerea caracterului respectiv din C. Cˆand ˆın lant , litera curent˘a

nu este ˆın C, generarea se ˆıncheie f˘ar˘a succes; dac˘a se ajunge la C =”” atunci avem un lant ,
anagram˘a s , i se contorizeaz˘a.

Problema 2 – partsums
Paul este ˆın vacant , ˘a s , i se plictises , te. De aceea, ˆıncearc˘a s˘a g˘aseasc˘a un nou mod inedit de a-s , i
petrece timpul. El scrie pe o foaie un s , ir format din N valori de 1. Apoi, sub acest s , ir calculeaz˘a
sumele part , iale: 1, 2, 3, . . . , N, obt , inˆand un nou s , ir de N numere. Deoarece plictiseala atinge
cote maxime, alege la ˆıntˆamplare un num˘ar R s , i ˆıs , i propune s˘a calculeze mental care este ultimul
num˘ar (al N-lea) din s , irul obt , inut dup˘a aplicarea operat , iei de R ori, calculˆand de fiecare dat˘a
ˆ
s , irul sumelor part , iale pentru s , irul anterior. Is , i d˘a seama c˘a este greu s˘a determine aceast˘a
valoare, as , a c˘a decide doar s˘a o estimeze, iar apoi s˘a vad˘a cˆat de mult s-a apropiat de valoarea
real˘a. Pentru a calcula valoarea exact˘a, ar avea nevoie de un program, lucru cu care v˘a roag˘a
pe voi s˘a ˆıl ajutat , i.

Cerint , ˘a
Dˆandu-se N – num˘arul de valori din s , ir s , i R – num˘arul de repet˘ari ale operat , iei, se cere:

1. al treilea num˘ar din s , irul obt , inut dup˘a aplicarea operat , iei de R ori, modulo 323333 (prim);
2. ultimul num˘ar din s , irul obt , inut dup˘a aplicarea operat , iei de R ori, modulo 323333 (prim).
Date de intrare
Fis , ierul de intrare partsums.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.

Urmeaz˘a o linie cont , inˆand cele 2 numere N s , i R separate printr-un spat , iu.

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 partsums.out se va scrie un singur num˘ar reprezentˆand valoarea celui de-al 3-lea
num˘ar din s , irul obt , inut dup˘a calcularea repetat˘a de R ori a sumelor part , iale, modulo 323333.
ˆ
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 se va scrie un singur num˘ar reprezentˆand valoarea celui de-al N-lea num˘ar din s , irul
obt , inut dup˘a calcularea repetat˘a de R ori a sumelor part , iale, modulo 323333.