Revizia anterioară Revizia următoare
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
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.
