Fişierul intrare/ieşire:	cartier2.in, cartier2.out	Sursă	IQ Academy
Autor	Ana Intuneric, Cristian Francu	Adăugată de	Cristian Francu •francu
Timp execuţie pe test	1 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	4/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Cartier2 (clasa a 8-a)

Notă: aceasta este problema cartier cu n mărit şi punctajele parţiale modificate.

Victor este un băiat deştept şi simpatic, dar care se plictiseşte foarte uşor. Tatăl său trebuie să născocească în permanenţă noi jocuri care să îl stimuleze. Ultimul joc, cartier, are trei niveluri şi se joacă utilizând o mulţime de cuburi gri, toate de aceeaşi dimensiune.

La primul nivel, Victor trebuie să construiască un bloc de formă dreptunghiulară format din n cuburi astfel încât suma dintre înălţimea blocului (H) şi lăţimea sa (L) să fie minimă şi L ≤ H. De exemplu, pentru n=6 se pot construi patru blocuri ca în imagine, dar doar primul bloc (B1) respectă condiţiile cerute.

Pentru a finaliza cel de-al doilea nivel al jocului, Victor trebuie să construiască un cartier, având la dispoziţie un număr dat de cuburi pentru fiecare bloc care formează cartierul. Pentru construcţia fiecărui bloc se respectă cerinţele de la primul nivel al jocului. În interiorul cartierului, blocurile sunt aşezate, în ordinea obţinerii lor, lipite unul de celălalt.

La al treilea nivel, Victor trebuie să determine un număr maxim de blocuri alăturate, astfel încât înălţimea primului bloc din şir şi înălţimea ultimului bloc din şir să nu fie numere prime între ele. Ajutaţi-l pe Victor să finalizeze nivelurile doi şi trei ale jocului cartier.

Cerinţă

Scrieţi un program care determină următoarele numere:
a) x, ce reprezintă numărul blocurilor de înălţime maximă construite la nivelul al doilea;
b) y, ce reprezintă suma lăţimilor blocurilor din cartierul construit la nivelul al doilea;
c) z, ce reprezintă numărul de blocuri din şirul determinat la nivelul al treilea.

Date de intrare

Fişierul de intrare cartier2.in conţine pe prima linie un număr natural n (numărul de blocuri de construit) şi pe a doua linie n numere naturale, separate prin câte un spaţiu, reprezentând numărul de cuburi corespunzătoare fiecărui bloc.

Date de ieşire

Fişierul de ieşire cartier2.out conţine numerele x, y şi z, în această ordine, fiecare pe câte o linie.

Restricţii

• 1 ≤ n < 1 000 000
• Numerele naturale citite aparţin intervalului [1, 1 000 000]
• 1 şi x sunt prime între ele oricare ar fi x
• Se acordă punctaje parţiale astfel: pentru punctul a) 20%, pentru punctul b) 20% şi pentru punctul c) 60%.
• Pentru 50% din teste numerele citite vor fi din intervalul [1, 13000]

Exemplu

Explicaţie