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
Tesztadatok
Címkék
A feladat forrása: USACO training material, Subset Sums
Algoritmusok:
megoldás |
|