Fișierul intrare/ieșire:	cartier2.in, cartier2.out	Sursă	IQ Academy
Autor	Ana Întuneric, Cristian Frâncu	Adăugată de	Cristian Francu •francu
Timp execuție pe test	1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	4/5

Poți vedea testele pentru această problemă accesând atașamentele.

Vezi soluțiile 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