• Infoarena Monthly 2014
• Format
• Clasament
• Organizatori
• Sponsori si premii
• Regulament
•  
• Runda 1
• Runda 2
• Runda 3
• Runda 4
• Runda 5
• Runda 6
• Runda 7
• Runda 8
• Runda 9
• Runda 10
• Runda 11
• Runda 12

Dreptunghi

Vom aplica un algoritm similar cu Algoritmul lui Euclid pentru determinarea celui mai mic divizor comun. Pentru fiecare dreptunghi de N x M, voi considera că N ≤ M. Vom crea un număr maxim de pătrate de dimensiune N x N. Acest număr maxim de pătrate este egal cu [M / N], iar pentru fiecare din aceste pătrate vom folosi exact N operaţii. Astfel, vom completa un dreptunghi de dimensiune [M / N]*N x N. Mai rămâne să completăm un dreptunghi de dimensiune N x M%N. Vom aplica acelaşi procedeu şi pentru acest dreptunghi, până când terminăm de completat tot dreptunghiul iniţial.

Sumfact

Soluţia se bazează pe faptul că pentru orice număr X, coeficientul lui X! în descompunerea unui număr N poate fi maxim X. Dacă acest coeficient este mai mare, de pildă X+1, vom avea (X+1) * X! = (X+1)!. Având în vedere că al doilea coeficient este mai mic, vom alege să folosim (X+1)! pentru descompunerea lui N. Plecând de la această observaţie, vom parcurge factorialele de la cel mai mare la cel mai mic, vom afla coeficientul fiecăruia împărţind N la acel factorial, urmând să scădem ce am obţinut din N şi să continuăm procedeul până când N devine 0.

K Aparitii

Limita de memorie nu permitea folosirea unei tabelă hash. De aceea, vom reţine pentru fiecare cifră de la 0 la 9, de câte ori apare aceasta ca cifră a unităţilor, a zecilor, a sutelor, ... Pentru a afişa numărul căutat, vom parcurge cifrele în ordine inversă, de la cifra cea mai semnificativă la cifra unităţilor şi pentru fiecare dintre acestea, vom afişa cifra care nu apare de un număr multiplu de K ori.

Rell

Problema se rezolvă cu ajutorul programării dinamice. Vom pregenera o matrice auxiliară cu următoarea semnificaţie:

• d[HP][CD1][CD2][CD3] = timpul minim în care poate fi doborâtă o maimuţă cu $HP puncte de viaţă, având un timpii de refacere rămaşi egali cu CD1 CD2 CD3, în această ordine.

Vom parcurge mai apoi punctele de viaţă de la 1 la 100, iar pentru fiecare punct de viaţă, voi alege timpul minim, iar în caz de egalitate voi alege soluţia care are suma A1 * CD1 + A2 * CD2 + A3 * CD3 minimă. Acestea vor fi reţinute într-o structură auxiliară nouă, pentru a putea răspunde în O(1) la fiecare întrebare.