Balances equilibrades V45017


Statement
 

pdf   zip

thehtml

Donats n pesos, hem de col·locar-los en una balança, un rere l’altre, de manera que en cap moment el plat de la dreta tingui més pes que el de l’esquerra. Us demanem que calculeu el nombre de maneres que hi ha de fer-ho.

Per exemple, si n=3 i els pesos són {1,2,4}, algunes solucions possibles són:

(1e,2e,4e),(2e,1e,4e), (2e,4e,1d), (2e,1d,4e), (4e,1d,2d), ⋯

on 1e significa que posem el pes 1 al plat de l’esquerra, mentre que 2d significa que posem el pes 2 al plat de la dreta. Recordem, com es veu a l’exemple, que l’ordre en el que posem els pesos importa i que, per tant, (2e,4e,1d) i (2e,1d,4e) són dues solucions diferents.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de pesos n seguit dels n diferents pesos, tots entre 1 i 106. Podeu assumir que 1 ≤ n ≤ 8.

Sortida

Per cada cas, escriviu el nombre de maneres correctes de col·locar els pesos a la balança. Aquest nombre mai serà més gran que 107.

Public test cases
  • Input

    1   20
    3   1 2 4
    3   6 10 4
    8   1 2 3 4 5 6 7 8
    

    Output

    1
    15
    17
    2130717
    
  • Information
    Author
    Albert Oliveras
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++