Fișierul intrare/ieșire | semisume.in, semisume.out | Sursă | USACO |
---|---|---|---|
Autor | autor necunoscut | Adăugată de | Radu Muntean • heracle |
Timp de execuție pe test | 0.05 sec | Limită de memorie | 512 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Semisume
Pentru mai multe multimi de numere naturale consecutive de la 1 la n, se pot imparti in 2 submultimi(a caror intersectie este multimea vida si reuniune multimea nr nat de la 1 la n) care sa aiba suma elementelor egala.
De exemplu daca n=3, multimea este {1,2,3}, iar singura varianta pentru cele 2 submultimi ar fi {1,2} si {3}. Se considera valida numai aceasta varianta, nu si {3} cu {1,2}, deoarece acestea sunt identice.
Cerinta
Faceti un program care sa calculeze numarul de moduri distincte in care poate fi impartita multimea astfel incat suma elementelor din fiecare multime sa fie egala. Daca nu se poate realiza nicio varianta corecta se va afisa valoarea 0;
Date de intrare
Fisierul de intrare semisume.in conține o singură linie, cu un singur număr întreg n.
Date de ieșire
Fisierul de iesire semisume.out contine tot o singura linie unde se va afisa raspunsul la cerinta.
Restricții
1<=n<=39;
Exemplu
semisume.in | semisume.out |
---|---|
7 |
4 |
Explicație
Dacă N = 7, există patru moduri de a împărți mulțimea {1, 2, 3, ... 7}, astfel încât fiecare partiție are aceeași sumă:
{1,6,7} și {2,3,4,5}
{2,5,7} și {1,3,4,6}
{3,4,7} și {1,2,5,6}
{1,2,4,7} și {3,5,6}