Fişierul intrare/ieşire:equicover.in, equicover.outSursăLot Botosani 2012 - Baraj 2 Seniori
AutorAdrian PanaeteAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Equicover

A fost o dată un om aşa de sărac, încât unica sa avere era un număr de n triunghiuri echilaterale de latură 1. Aceste triunghiuri aveau proprietatea că se puteau lipi unul de altul de-a lungul unei laturi formând astfel diverse figuri geometrice plane. Împăratul a dat sfoară în ţară că va da jumătate de împărăţie şi pe fata sa de soţie celui care va forma cel mai frumos poligon convex folosind exact n triunghiuri echilaterale de latură 1. Omul nostru a observat că există multe moduri în care pot fi formate poligoane convexe. Totuşi el nu este sigur dacă a calculat bine numărul de poligoane convexe, necongruente două câte două, ce se pot construi cu triunghiurile sale. Acum se teme că a uitat să-l numere exact pe cel dorit de împărat şi că astfel va pierde ocazia de a scăpa de sărăcie şi mai cu seamă de a se căsători cu frumoasa prinţesă.

Cerinţă

Să se determine numărul poligoanelor convexe, necongruente două câte două care se pot acoperi perfect folosind un număr dat de triunghiuri echilaterale de latură 1.

Date de intrare

Fişierul de intrare equicover.in conţine pe prima linie numărul natural n.

Date de ieşire

Fişierul de ieşire equicover.out va conţine pe prima linie un număr natural reprezentând numărul de poligoane convexe, necongruente două câte două care se pot acoperi perfect folosind n triunghiuri echilaterale de latură 1.

Restricţii şi precizări

  • 1 ≤ n ≤ 1 000 000

Exemplu

equicover.inequicover.out
16
5

Explicaţie

Cele 5 poligoane sunt:

Următoarele poligoane sunt congruente cu unul dintre cele 5:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?