Հավասար բաժանում

Հայկը մասնակցում է ինֆորմատիկայի միջազգային օլիմպիադային և նրան բաժին է ընկել հետևյալ խնդիրը։ Տրված են 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

To check your solution you need to sign in