Հավասար բաժանում
Հայկը մասնակցում է ինֆորմատիկայի միջազգային օլիմպիադային և նրան բաժին է ընկել հետևյալ խնդիրը։ Տրված են
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-ի։
Աղբյուրը՝ Հանրապետական 2022
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB