Planning P11233


Statement
 

pdf   zip

thehtml

El dia abans del SWERC els equips de la UPC decideixen (potser) deixar una mica l’Age of Empires i fer diverses activitats productives (com ara visitar algun monument, intentar lligar, etc). Poden repetir una activitat durant el dia, però no de forma consecutiva perquè seria molt avorrit.

Sabent exactament el temps que triguen a fer cada activitat, de quantes maneres poden organitzar el dia? Se sap que es lleven a una certa hora x i que han d’estar a l’hotel a una certa hora y per estar “a tope” el dia següent al SWERC. No poden deixar estones lliures entre les activitats, però en qualsevol moment del dia (inclosa l’hora inicial x) poden decidir tornar a l’hotel per jugar a l’Age fins a l’hora y.

Entrada

L’entrada consisteix en diversos casos, només amb nombres naturals. Cada cas comença amb el temps t = y − x en segons, seguit del nombre n d’activitats possibles, seguit dels n ‍temps en segons que es triga a fer cada activitat. Suposeu 1 ≤ t ≤ 1000, 1 ≤ n ≤ 100, i que el temps de cada activitat no és més gran que t.

Sortida

Per a cada cas, escriviu el nombre total de maneres d’organitzar el dia mòdul 108 + 7.

Pista

Una solució acceptable per a aquest problema té cost Θ(n2t).

Public test cases

  • Input

    4
2  2 3

5
2  2 3

6
2  2 3

1000
5  61 735 900 1 1

1000
5  1 1 1 1 1

    Output

    3
5
5
43712202
71503807
    • Information
    Author
    Ivan Geffner
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++