Հայկը մասնակցում է ինֆորմատիկայի միջազգային օլիմպիադային և նրան բաժին է ընկել հետևյալ խնդիրը։ Տրված են n դրական ամբողջ թվեր, անհրաժեշտ է հաշվել թե քանի ձևով է հնարավոր բոլոր թվերը բաժանել խմբերի այնպես, որ յուրաքանչյուր թիվ գտնվի ճիշտ մեկ խմբում և բոլոր խմբերի էլեմենտների գումարը լինի նույնը։ Հայկը միանգամից հասկացավ խնդրի լուծումը և սկսեց ռեալիզացնել այն։ Հերթը ձերն է։
Մուտքային տվյալներ
Մուտքի առաջին տողում տրված է n բնական թիվը։ Երկրորդ տողում տրված են n ամբողջ թվեր բաժանված բացատով, որոնց անհրաժեշտ է բաժանել խմբերի։
Ելքային տվյալներ
Ելքի միակ տողում տողում անհրաժեշտ է արտածել մեկ ամբողջ թիվ՝ բաժանման հնարավոր ձևերի քանակը։
Ենթախնդիրներ
Ենթախնդիր 0 (0 միավոր) Օրինակները։
Ենթախնդիր 1 (7 միավոր)1 ≤ n ≤ 15, տրված բոլոր թվերը միմյանց հավասար են և փոքր կամ հավասար են -ից։
Ենթախնդիր 2 (8 միավոր)1 ≤ n ≤ 5, տրված բոլոր թվերը փոքր կամ հավասար են -ից։
Ենթախնդիր 2 (19 միավոր)1 ≤ n ≤ 9, տրված բոլոր թվերը փոքր կամ հավասար են -ից։
Ենթախնդիր 4 (21 միավոր)1 ≤ n ≤ 15, տրված բոլոր թվերը փոքր կամ հավասար են 2-ից։
Ենթախնդիր 5 (45 միավոր)1 ≤ n ≤ 15, տրված բոլոր թվերը փոքր կամ հավասար են -ից։
Օրինակ
Մուտք
Ելք
4
5 5 5 5
5
8
1 1 2 2 1 1 2 2
89
7
3 2 2 7 5 7 2
11
Բացատրություն
Առաջին օրինակում, թվերը կարելի է բաժանել հետևյալ եղանակներով.
Թվերը բաժանենք 4 խմբի, ամեն խմբում 1 էլեմենտ։ Դա հնարավոր է, քանի որ բոլոր թվերը իրար հավասար են։
Թվերը բաժանենք 2 խմբի հետևյալ եղանակով (1, 2) և (3, 4)։
Թվերը բաժանենք 2 խմբի հետևյալ եղանակով (1, 3) և (2, 4)։
Թվերը բաժանենք 2 խմբի հետևյալ եղանակով (1, 4) և (2, 3)։
Թվերը բաժանենք 1 խմբի, բոլոր թվերը միասին։
Երկրորդ օրինակում հնարավոր բաժանումներից մեկը հետևյալն է. (1, 3, 6, 7) և (2, 4, 5, 8)։ Երկու խմբում էլ թվերի գումարը հավասար է 6-ի։