CHIARUONG - Chia ruộng
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 3.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Trong làng Omega có 1 phú ông rất giầu có. Tài sản của ông rất nhiều trâu, bò, ruộng vườn. Một hôm ông gọi 3 người con đã đến tuổi trưởng thành đến ông chia cho một số ruộng để làm ăn. Ông có hàng trăm mẫu ruộng nhưng ông chỉ chọn n thửa ruộng để chia, thửa thứ i có diện tích ai m2. Hỏi rằng phú ông có bao nhiêu cách chia đều n thửa ruộng cho 3 con sao cho các thửa ruộng được chia phải giữ nguyên diện tích.

Dữ liệu

  • Dòng 1: ghi số n là số thửa ruộng của phú ông đem chia (1≤n≤20)
  • Dòng 2: ghi các số ai là diện tích của thửa ruộng thứ i (100≤a[i]≤5000).

Kết quả

  • Dòng thứ nhất ghi số cách chia, nếu không thể chia được thì ghi -1.

Ví dụ

Input

5
100 200 250 50 300

Output

6

Giải thích ví dụ: Có 6 các chia cách tương ứng với quy ước người thứ nhất có tên là “A”, người thứ hai có tên là “B”, người thứ ba có tên là “C” và theo thứ tự của các thửa ruộng được chia.

  • AABBC
  • AACCB
  • BBAAC
  • BBCCA
  • CCAAB
  • CCBBA

Nguồn: DHDBBB'17

Back to Top