Programozás‎ > ‎Feladatok‎ > ‎

Részhalmaz összegek

Ha 1 <= N <= 39, akkor lehetséges, hogy az {1, 2, 3, .., N} halmaz két egyenlő összegű részhalmazra bontható. Például N=3 esetén az {1, 2, 3} halmaz megfelelő felbontása: {3} és {1,2}. (Ez egy eset, a halmazok sorrendje nem számít.)

Ha N=7, akkor már négyféle módon bontható az {1, 2, 3, ... 7} halmaz két azonos összegű részre:

{1,6,7} és {2,3,4,5}
{2,5,7} és {1,3,4,6}
{3,4,7} és {1,2,5,6}
{1,2,4,7} és {3,5,6}

Feladat

Írjunk programot, ami adott N-re megadja az egyenlő összegű felbontások számát. Ha nem adható jó felbontás, akkor 0-át kell kiírni.

Bemenet

A bemenet N értéket tartalmazza.

Kimenet

Egyetlen szám, a felbontások száma.

Példa

Bemenet  Kimenet
7
4


Tesztadatok

Címkék

A feladat forrása: USACO training material, Subset Sums
Algoritmusok: 

megoldás