Malditos unos P84469


Statement
 

pdf   zip

thehtml

Dada una secuencia de naturales x1xn 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.

Public test cases
  • 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
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++