Diferente pentru problema/drumuri3 intre reviziile #3 si #18

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="drumuri3") ==
Bercea tocmai şi-a procurat (prin mijloace îndoielnice) o nouă limuzină. Acum, pentru a arăta tuturor noua sa achiziţie, el s-a hotărât să facă o plimbare prin oraş, oraşul fiind de fapt un graf cu $N$ noduri şi $M$ muchii. Un drum se defineşte ca fiind o secvenţă de noduri $a{~1~}$, $a{~2~}$, ..., $a{~k~}$ astfel încât să existe muchia ({$a{~i~}$}, $a{~i+1~}$), oricare ar fi $1$ ≤ $i$ ≤ $k-1$. Astfel orice nod poate fi folosit de oricâte ori într-un drum, la fel şi orice muchie. Lungimea unui drum este numărul de noduri care fac parte din drumul respectiv.
Totuşi Bercea nu doreşte să facă drumuri mai lungi de $K$ noduri, deoarece atunci ar putea ieşi din sfera sa de influenţă din oraş. Aşadar, fiind date două noduri $i$ si $ji$, aflaţi numărul de drumuri care încep în nodul $i$, se termină in nodul $ji$, iar lungimea fiecărui drum este ≤ $K$.
 
Bercea tocmai şi-a procurat (prin mijloace îndoielnice) $Q$ limuzine. Acum, pentru a arăta tuturor noile sale achiziţii, el s-a hotărât să facă mai multe plimbări prin oraş, oraşul fiind de fapt un graf *neorientat* cu $N$ noduri şi $M$ muchii. Un drum se defineşte ca fiind o secvenţă de noduri $a{~1~}$, $a{~2~}$, ..., $a{~k~}$ astfel încât să existe muchia ({$a{~i~}$}, $a{~i+1~}$), oricare ar fi $1$ ≤ $i$ ≤ $k-1$. Astfel orice nod poate fi folosit de oricâte ori într-un drum, la fel şi orice muchie. Lungimea unui drum este numărul de noduri care fac parte din drumul respectiv.
Totuşi Bercea nu doreşte să facă drumuri mai lungi de $K$ noduri, deoarece atunci ar putea ieşi din sfera sa de influenţă din oraş. Aşadar, fiind date $Q$ perechi de noduri $i$ si $ji$, aflaţi numărul de drumuri care încep în nodul $i$, se termină in nodul $ji$, iar lungimea fiecărui drum este ≤ $K$.
Deoarece numărul de drumuri poate fi foarte mare şi Bercea nu ştie să numere decât până la câte milioane de € are, afişaţi răspunsul modulo $10 007$.
h2. Date de intrare
Fişierul de intrare $drumuri3.in$ ...
Fişierul de intrare $drumuri3.in$ va conţine pe prima linie numerele naturale $N$, $M$, $K$ şi $Q$ cu semnificaţia de mai sus. Următoarele $M$ linii vor conţine câte două numere naturale reprezentând două noduri între care există o muchie. Următoarele $Q$ linii vor conţine câte două numere naturale $i$ şi $ji$ reprezentând perechile de oraşe între care Bercea doreşte să se plimbe.
h2. Date de ieşire
În fişierul de ieşire $drumuri3.out$ ...
În fişierul de ieşire $drumuri3.out$ se vor afişa $Q$ linii cu numerele dorite modulo $10 007$.
h2. Restricţii
h2. Restricţii şi precizări
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100$
* $1 ≤ K ≤ 5 000$
* $1 ≤ Q ≤ 2 500$
* Graful este conex (există cel puţin un drum între oricare două perechi de noduri).
* O muchie nu va apărea în fişierul de intrare de mai multe ori.
* Nu va exista în fişierul de intrare o muchie de la un nod la el însuşi.
* $i$ ≠ $ji$
h2. Exemplu
table(example). |_. drumuri3.in |_. drumuri3.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 6 15 4 2
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 2
1 6
| 26
26
|
h3. Explicaţie
 
...
 
== include(page="template/taskfooter" task_id="drumuri3") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
5300