Farmer John tiene $N$ vacas, $2 \le N \le 20$; la vaca $i$ produce $M(i)$ unidades de leche al día ($1 \le M(i) \le 100,000,000$). Para agilizar el ordeño diario instala una máquina nueva en el granero. ¡Pero es demasiado sensible y solo funciona si las vacas de izquierda y derecha producen exactamente el mismo total!
Un subconjunto es «balanceado» si puede dividirse en dos grupos de igual producción. Solo uno balanceado hace funcionar la máquina, y FJ quiere contar estos subconjuntos de sus $N$ vacas. Calcula el número.
Entrada
- Línea 1: entero $N$.
- Líneas 2..1+$N$: la línea $i+1$ contiene $M(i)$.
Salida
- Línea 1: número de subconjuntos balanceados.
Ejemplos
Entrada 1
4 1 2 3 4
Salida 1
3
Nota
Cuatro vacas producen 1, 2, 3 y 4 unidades.
Tres subconjuntos balanceados: $\{1,2,3\}$ se divide en $\{1,2\}$ y $\{3\}$; $\{1,3,4\}$ en $\{1,3\}$ y $\{4\}$; $\{1,2,3,4\}$ en $\{1,4\}$ y $\{2,3\}$.
Autor del problema: Neal Wu, 2012