Planning (difícil) P65632
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 = y − x 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).
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
- Author
- Ivan Geffner
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++