Diferențe pentru problema/superstition între reviziile #4 si #45

superstition

Superstition

h2. Date de intrare

Fișierul de intrare $superstition.in$ ...

Fișierul de intrare $superstition.in$ conține patru numere întregi [$N$], [$M$], $D$ și [$K$]. De pe următoarele $М$ linii se citesc câte trei numere întregi $x[~i~]$, $y[~i~]$ și $t[~i~]$ reprezentând strada bidirecțională dintre magazinele x[~i~] și y[~i~] traversată în timpul t[~i~].

h2. Date de ieșire

În fișierul de ieșire $superstition.out$ ...

Fișierul de ieșire $superstition.out$ va conține numărul de rute diferite valide determinat. De vreme ce numărul poate fi foarte mare, ți se cere să afișezi restul la împărțirea cu $1 000 000 007$ al numărului determinat

h2. Restricții
* $... ≤ ... ≤ ...$

h2. Restricții

h2. Exemplu

* $2 ≤ N ≤ 80$
* $2 ≤ M ≤ 3160$
* $2 ≤ D ≤ K ≤ 10[^9^]$
* $1 ≤ t[~i~] ≤ 10$
* $1 ≤ i ≤ M$

table(example).

|_. superstition.in |_. superstition.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|

|_. Subtask |_. Punctaj |_. N |_. M |_. D |_. K |_. Alte restricții |
| 1
| 5
| ≤ 5
| ≤ 10
| ≤ 12
| ≤ 12
| Nu există alte restricții
|
| 2
| 30
| ≤ 80
| ≤ 3160
| ≤ 10[^4^]
| ≤ 10[^4^]
| Nu există alte restricții
|
| 3
| 10
| ≤ 20
| ≤ 190
| ≤ 10[^9^]
| ≤ 10[^9^]
| D = K și ∑[^M^][~i = 1~] t[~i~]≤ 200
|
| 4
| 20
| ≤ 20
| ≤ 190
| ≤ 10[^9^]
| ≤ 10[^9^]
| ∑[^M^][~i = 1~] t[~i~]≤ 200
|
| 5
| 15
| ≤ 30
| ≤ 435
| ≤ 10[^9^]
| ≤ 10[^9^]
| D = K
|
| 6
| 20
| ≤ 30
| ≤ 435
| ≤ 10[^9^]
| ≤ 10[^9^]
| Nu există alte restricții
|
 
Programul tău va obține punctajul pe un subtask dacă toate testele din acel subtask vor fi trecute cu succes.

h3. Explicație
...

h2. Exemplu
 
table(example).
|_. superstition.in |_. superstition.out |_. Explicații |
| 3 3 2 2
1 2 1
2 3 2
3 1 1
| 8
| Aici D = K = 2 deci soluțiile sunt doar rute de durată 2.
Acestea sunt:
1 – 2 – 1    2  – 1  – 2    3 – 1 – 3
1 – 3 – 1    2  – 3         3 – 2
2 – 1 – 3    3  – 1  – 2
Observați  că străzile și  magazinele  se  pot repeta mai mult de o dată.
|
| 5 7 5 10
1 3 8
2 5 7
3 4 3
1 4 2
2 3 1
1 5 4
4 5 4
| 58
| Pentru D < K soluțiile sunt doar rute de durată 5 sau 10
|
| 5 9 2 20
1 2 1
2 3 2
3 1 1
3 4 1
4 5 2
5 3 1
1 5 1
2 4 1
2 5 1
| 989802661
| Aici răspunsul este foarte mare așa că s-a afișat doar  restul  la  împărțirea  cu 1,000,000,007 a
numărului determinat.
|
| 5 7 5000000 5000000
1 3 8
2 5 7
3 4 3
1 4 2
2 3 1
1 5 4
4 5 4
| 598634781
| Aici răspunsul este foarte mare așa că s-a afișat doar  restul  la  împărțirea  cu 1,000,000,007 a
numărului determinat.
|

== include(page="template/taskfooter" task_id="superstition") ==