Lista de probleme 4

Nivelul concursului: Național

Grupe

Clasa a IX-a Clasele XI-XII

#2250 fact

Pentru un număr natural nenul, definim factorialul său ca fiind produsul tuturor numerelor naturale nenule mai mici sau egale decât el şi îl notăm N! (adică N! = 1*2*…*N). Pentru o bază de numeraţie B şi un număr natural nenul N, se cere determinarea ultimei cifre nenule a scrierii în baza B a lui N!. Se citesc 5 perechi de forma (Ni, Bi), unde 1 ≤ i ≤ 5. Pentru fiecare din cele 5 perechi citite, aflați ultima cifră nenulă a scrierii în baza Bi a factorialului numărului Ni.

Fie A o matrice dreptunghiulară de numere întregi cu N linii numerotate de la 1 la N şi M coloane numerotate de la 1 la M. În matricea A oricare două elemente consecutive de pe aceeaşi linie sunt distincte.
Se defineşte un şir valid de numere întregi ca fiind fie un şir crescător, fie un şir descrescător, fie un şir crescător concatenat cu un şir descrescător, fie un şir descrescător concatenat cu unul crescător. Exemple de şiruri valide sunt: 1 2 3 7, 8 5 2 1, 3 5 6 2, 4 1 5 6.Se defineşte o submatrice a lui A de coordonate (l1, c1, l2, c2) ca fiind matricea formată din toate elementele A(i,j), cu l1 ≤ i ≤ l2 şi c1 ≤ j ≤ c2. O submatrice a lui A este validă dacă liniile sale sunt şiruri valide.
Atenţie! O submatrice validă poate avea pe o linie un şir crescător de numere, pe a doua un şir descrescător, pe a treia un şir crescător concatenat cu unul descrescător etc. Deci, liniile unei submatrice valide nu trebuie să fie neapărat şiruri de acelaşi tip.
Aria unei submatrice este egală cu numărul de elemente din care este formată submatricea. Se cere să se găsească o submatrice validă a lui A de arie maximă.

#2249 panouri

Pe autostrada Soarele Estului sunt aşezate de-a lungul şoselei, la distanţe egale, panouri publicitare ale unor firme. Aceeaşi firmă, poate să aibă mai multe panouri publicitare şi fiecare panou poate să apară în mai multe locuri. Panourile se identifică prin numere naturale, numărul total de panouri fiind N. Firma X Corporation are panouri de T tipuri diferite. Firma a primit aprobarea construirii unui mare complex turistic în apropierea autostrăzii; de aceea, pentru alegerea locului, este interesată şi de următorul aspect: care este lungimea minimă de şosea, în care se pot întâlni, toate cele T tipuri de panouri publicitare ale firmei, indiferent de ordinea acestora, şi indiferent dacă între ele se mai interpun sau nu panouri ale altor firme. Cunoscând N – numărul total de panouri de la marginea autostrăzii şi ordinea amplasării lor, ca şi cele T tipuri de panouri amplasate de firmă, determinaţi numărul minim de intervale dintre două panouri între care firma X Corporation îşi regăsește toate panourile sale.

#2251 Pereti

Localitatea Târgovişte este în plină modernizare. Primăria decide să inventarieze toate clădirile din oraş pentru a renova faţadele acestora. În acest sens analizează harta oraşului şi constată că toţi pereţii sunt aşezaţi doar pe direcţia Nord Sud sau Est Vest. Pereţii vizibili de către turiști sunt doar aceia la care se poate ajunge din exteriorul orașului prin deplasarea pe cele două direcţii date, în oricare din cele patru sensuri (N, E, S, V). Harta oraşului este întocmită pe un caroiaj format din pătrate cu latura 1. Cunoscându-se harta oraşului, determinaţi lungimea pereţilor vizibili ce urmează a fi zugrăviţi.