Diferente pentru problema/cezar intre reviziile #49 si #24

Diferente intre titluri:

Cezar
cezar

Diferente intre continut:

== include(page="template/taskheader" task_id="cezar") ==
In Roma antica exista {$N$} asezari senatoriale distincte, cate una pentru fiecare dintre cei $N$ senatori ai Republicii. Asezarile senatoriale sunt numerotate de la $1$ la $N$, intre oricare doua asezari existand legaturi directe sau indirecte. O legatura este directa daca ea nu mai trece prin alte asezari senatoriale intermediare. Edilii au pavat unele dintre legaturile directe dintre doua asezari (numind o astfel de legatura pavata "strada"), astfel incat intre oricare doua asezari senatoriale sa existe o singura succesiune de strazi prin care se poate ajunge de la o asezare senatoriala la cealalta.
Toti senatorii trebuie sa participe la sedintele Senatului. In acest scop, ei se deplaseaza cu lectica. Orice senator care se deplaseaza pe o strada plateste $1$ ban pentru ca a fost transportat cu lectica pe acea strada.
Toti senatorii trebuie sa participe la sedintele Senatului. In acest scop, ei se deplaseaza cu lectica. Orice senator care se deplaseaza pe o strada plateste 1 ban pentru ca a fost transportat cu lectica pe acea strada.
La alegerea sa ca prim consul, Cezar a promis ca va dota Roma cu o lectica gratuita care sa circule pe un numar de $K$ strazi ale Romei astfel incat orice senator care va circula pe strazile respective, sa poata folosi lectica gratuita fara a plati. Strazile pe care se deplaseaza lectica gratuita trebuie sa fie legate intre ele (zborul, metroul sau teleportarea nefiind posibile la acea vreme).
In plus, Cezar a promis sa stabileasca sediul salii de sedinte a Senatului intr-una dintre asezarile senatoriale aflate pe traseul lecticii gratuite. Problema este de a alege cele $K$ strazi si amplasarea sediului salii de sedinte a Senatului astfel incat, prin folosirea transportului gratuit, senatorii, in drumul lor spre sala de sedinte, sa faca economii cat mai insemnate. In calculul costului total de transport, pentru toti senatorii, Cezar a considerat ca fiecare senator va calatori exact o data de la asezarea sa pana la sala de sedinte a Senatului.
h2. Restrictii
* {$1 < N &le; 10000$}
* {$0 < K < N$}
* {$1 &le; i, j &le; N, i &ne; j$}
* $1$ < $N$ &le; $10000$
* $0$ < $K$ < $N$
* $1$ &le; $i$ , $j$ &le; $N$ , $i$ &ne; $j$
* Oricare doua perechi de valori de pe liniile $2$, $3$,..., $N$ din fisierul de intrare reprezinta doua strazi distincte.
* Perechile din fisierul de intrare sunt date astfel incat respecta conditiile din problema.
* Pentru $25%$ din teste {$N &le; 30$}, pentru $25%$ din teste {$30 < N &le; 1000$}, pentru $30%$ din teste {$1000 < N &le; 3000$}, pentru $10%$ din teste {$3000 < N &le; 5000$},  pentru $10%$ din teste {$5000 < N &le; 10000$}.
* Perechile din fisierul de intrare sunt date astfel încat respecta conditiile din problema.
* Pentru $25%$ din teste  $N$ &le; $30$, pentru alte $25%$ din teste $30$ < $N$ &le; $1000$, pentru alte $25%$ din teste $1000$ < N &le; $3000$, pentru alte $10%$ din teste $3000$ < $N$ &le; $5000$,  pentru alte $10%$ din teste $5000$ < $N$ &le; $10000$.
h2. Exemplu
table(example). |_. cezar.in |_. cezar.out |
| 13 3
1 2
2 3
2 8
7 8
7 5
5 4
5 6
8 9
8 10
10 11
10 12
10 13
| 11
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
h3. Explicatie
!problema/cezar?poza.jpg 65%!
 
Costul minim se obtine, de exemplu, pentru alegerea celor $3$ strazi intre asezarile $5-7$, $7-8$, $8-10$ si a salii de sedinte a Senatului in asezarea $8$ (dupa cum este evidentiat in desen).
Exista si alte alegeri pentru care se obtine solutia $11$.
...
== include(page="template/taskfooter" task_id="cezar") ==
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

2059