Malditos unos P84469
Dada una secuencia de naturales x1 … xn entre 0 y 9, escoged como operarlos mediante sumas y productos, poniendo los paréntesis que queráis, de manera que el resultado final sea el máximo posible. Por ejemplo, para la secuencia
| 1 3 2 0 9 1 1 3 1 5 |
el máximo resultado posible es
| (1 + 3) * (2 + 0) * 9 *(1 + 1) * (3 + 1) * 5 = 2880 . |
Fijáos que no está permitido cambiar el orden de los números dados, ni unirlos entre si para formar números de dos o más dígitos.
Entrada
La entrada consiste en diversos casos. Cada caso comienza con n, seguida de n números entre 0 y 9. Asumid 1 ≤ n ≤ 104.
Salida
Para cada caso, escribid el máximo resultado posible módulo 109 + 7.
Puntuación
- Test1: 5 Puntos
Resolver casos donde todas las xi están entre 2 y 9, como los del ejemplo 1.
- Test2: 15 Puntos
Resolver casos donde n ≤ 10 y el resultado sin hacer módulos no sería superior a 109, como los del ejemplo 2.
- Test3: 20 Puntos
Resolver casos donde n ≤ 20 y el resultado sin hacer módulos no sería superior a 1018, como los del ejemplo 3.
- Test4: 60 Puntos
Resolver casos de todo tipo.
Input
6 2 3 4 5 6 7 12 9 9 9 9 9 9 9 9 9 9 9 9
Output
5040 429534507
Input
10 1 3 2 0 9 1 1 3 1 5 9 2 1 1 2 1 1 1 1 3 9 3 1 1 2 1 2 1 1 3 2 0 0
Output
2880 108 216 0
Input
15 2 1 1 1 0 2 1 1 1 0 1 1 2 2 2
Output
648
Input
30 2 1 1 2 1 1 2 2 1 1 2 1 3 2 1 1 2 1 1 1 1 3 2 1 1 2 1 2 1 2
Output
11337408
- Author
- Salvador Roura
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++