Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | equicover.in, equicover.out | Sursă | Lot Botosani 2012 - Baraj 2 Seniori |
| Autor | Adrian Panaete | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | equicover.out |
|---|---|
| 16 | 5 |
Explicaţie
Cele 5 poligoane sunt:
Următoarele poligoane sunt congruente cu unul dintre cele 5:
