Planning (difícil) P65632


Statement
 

pdf   zip

thehtml

L’enunciat d’aquest problema és semblant a l’anterior (Planning). Les úniques diferències es troben en el format de l’entrada, en que ara la n pot estar entre 1 i 1000, i en que la solució esperada és més eficient.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb les dues hores x i y, seguides del nombre n d’activitats possibles, seguit dels n temps que es triga a fer cada activitat. Suposeu que les hores estan entre 00:00:00 i 23:59:59, que el temps t = yx compleix 1 ≤ t ≤ 1000, 1 ≤ n ≤ 1000, que el temps de cada activitat no és més gran que t, i que tant les hores com els temps segueixen estrictament el bonic format dels exemples.

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 Θ(nt).

Public test cases
  • Input

    12:00:00  12:00:04
    2  0m 2s  0m 3s
    
    12:00:00  12:00:05
    2  0m 2s  0m 3s
    
    12:00:00  12:00:06
    2  0m 2s  0m 3s
    
    04:55:59  05:12:39
    5  1m 1s  12m 15s  15m 0s  0m 1s  0m 1s
    
    00:00:00  00:16:40
    5  0m 1s  0m 1s  0m 1s  0m 1s  0m 1s
    

    Output

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