Diferente pentru problema/pitici intre reviziile #15 si #5

Diferente intre titluri:

Pitici
pitici

Diferente intre continut:

In varful muntelui Acrom traiesc pe timpul verii $K$ pitici, numerotati de la $1$ la $K$. Pe munte exista $N$ cabane, aflate la altitudini diferite, legate intre ele de $M$ poteci. Cabana piticilor este numerotata cu $1$, iar cabana de la poalele muntelui cu $N$. Fiindca iarna este prea frig, piticii se muta in cabana de la poalele muntelui, unde este mai cald. Piticii sunt disciplinati si coboara de pe munte in ordinea crescatoare a numerelor lor. Pentru a nu fi acuzati de lipsa de personalitate, fiecare pitic alege drumul cel mai scurt pana jos, drum diferit de fiecare dintre drumurile alese de piticii ce au coborat inaintea lui. Un drum al unui pitic este o succesiune de cabane $x{~1~} x{~2~} ... x{~p~}$ cu proprietatea ca $x{~1~}=1$, $x{~p~}=N$ si intre oricare doua cabane consecutive pe drum $x{~i~}$ si $x{~i+1~}$ exista o poteca ce merge in vale (adica altitudinea cabanei $x{~i~}$ este mai mare decat altitudinea cabanei $x{~i+1~}$). Doua drumuri sunt diferite daca exista cel putin o cabana ce apartine unuia dintre drumuri si nu apartine celuilalt. Lungimea unui drum este suma lungimilor potecilor ce leaga cabanele situate pe acest drum.
h2. Cerinta
 
Scrieti un program care sa determine lungimea drumului ales de fiecare pitic, drum ce respecta conditiile din enunt.
 
h2. Date de intrare
Pe prima linie a fisierului de intrare $pitici.in$ sunt scrise trei numere naturale $N M K$ separate prin cate un spatiu cu semnificatia din enunt. Urmatoarele $M$ linii contin cate $3$ numere $a b c$ separate prin cate un spatiu, cu semnificatia ca exista poteca de la cabana $a$ la cabana $b$ de lungime $c$, cabana $a$ avand o altitudine mai mare decat cabana $b$.
...
h2. Date de iesire
Fisierul de iesire $pitici.out$ va contine o singura linie pe care vor fi scrise $K$ numere naturale separate prin cate un spatiu. Al $i$-lea numar reprezinta lungimea drumului ales de piticul $i$.
...
h2. Restrictii
* $3 ≤ N ≤ 1019$
* $3 ≤ M ≤ 200 019$
* $3 ≤ K ≤ 1019$
* $1 ≤ c ≤ 1000$
* se garanteaza corectitudinea datelor de intrare
* intre oricare doua cabane exista cel mult o poteca
* vor exista cel putin $K$ drumuri de la cabana $1$ la cabana $N$
* cabana $1$ are altitudinea cea mai mare, cabana $N$ are altitudinea cea mai mica
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. pitici.in |_. pitici.out |
| 9 11 3
  1 2 1
  1 4 1
  2 3 1
  3 7 4
  7 9 1
  4 6 2
  4 5 1
  5 8 4
  6 8 1
  6 7 2
  8 9 2
| 6 6 7
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
h3. Explicatie
Primul pitic va alege drumul format din cabanele $1 4 6 7 9$, drumul avand lungimea $6$.
Al doilea va alege drumul $1 4 6 8 9$, tot de lungime $6$.
Ultimul pitic va alege drumul $1 2 3 7 9$ de lungime $7$.
...
== include(page="template/taskfooter" task_id="pitici") ==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

1711