Diferente pentru problema/lanterna intre reviziile #3 si #6

Nu exista diferente intre titluri.

Diferente intre continut:

==Include(page="template/taskheader" task_id="lanterna")==
Un agent secret are o harta pe care sunt marcate N obiective militare. El se afla, initial, langa obiectivul numerotat cu 1 (baza militara proprie) si trebuie sa ajunga la obiectivul numerotat cu N (baza militara inamica). Pentru aceasta, el va folosi drumurile existente, fiecare drum legand 2 obiective distincte. Fiind o misiune secreta, deplasarea agentului va avea loc noaptea; de aceea, el are nevoie de o lanterna. Pentru aceasta, el are de ales intre K tipuri de lanterne - o lanterna de tipul W (1 <= W <= K) are baterii care permit consumul a W watti; dupa consumul acestor watti, lanterna nu mai lumineaza. Din fericire, unele dintre obiective sunt baze militare prietene, astfel ca, o data ajuns acolo, el isi poate reincarca complet bateriile. Agentul trebuie sa aiba grija ca, inainte de merge pe un drum intre doua obiective, cantitatea de watti pe care o mai poate consuma sa fie mai mare sau egala cu cantitatea de watti pe care o va consuma pe drumul respectiv.
 
Cunoscand drumurile dintre obiective si, pentru fiecare drum, durata necesara parcurgerii drumului si numarul de watti consumati de lanterna, determinati tipul de lanterna cu numarul cel mai mic, astfel incat durata deplasarii sa fie minima (sa presupunem ca acest tip este W ; aceasta inseamna ca daca ar alege o lanterna de un tip mai mic decat W, durata deplasarii ar fi strict mai mare, iar daca ar alege o lanterna de un tip mai mare decat W, durata deplasarii ar fi mai mare sau egala).
Un agent secret are o harta pe care sunt marcate $N$ obiective militare. El se afla, initial, langa obiectivul numerotat cu 1 (baza militara proprie) si trebuie sa ajunga la obiectivul numerotat cu $N$ (baza militara inamica). Pentru aceasta, el va folosi drumurile existente, fiecare drum legand 2 obiective distincte. Fiind o misiune secreta, deplasarea agentului va avea loc noaptea; de aceea, el are nevoie de o lanterna. Pentru aceasta, el are de ales intre $K$ tipuri de lanterne - o lanterna de tipul $W (1 &le; W &le; K)$ are baterii care permit consumul a $W$ watti; dupa consumul acestor watti, lanterna nu mai lumineaza. Din fericire, unele dintre obiective sunt baze militare prietene, astfel ca, o data ajuns acolo, el isi poate reincarca complet bateriile. Agentul trebuie sa aiba grija ca, inainte de merge pe un drum intre doua obiective, cantitatea de watti pe care o mai poate consuma sa fie mai mare sau egala cu cantitatea de watti pe care o va consuma pe drumul respectiv.
Cunoscand drumurile dintre obiective si, pentru fiecare drum, durata necesara parcurgerii drumului si numarul de watti consumati de lanterna, determinati tipul de lanterna cu numarul cel mai mic, astfel incat durata deplasarii sa fie minima (sa presupunem ca acest tip este $W$; aceasta inseamna ca daca ar alege o lanterna de un tip mai mic decat $W$, durata deplasarii ar fi strict mai mare, iar daca ar alege o lanterna de un tip mai mare decat $W$, durata deplasarii ar fi mai mare sau egala).
h2. Date de Intrare
Pe prima linie a fisierului lanterna.in se afla numerele intregi N si K, separate printr-un spatiu. Pe urmatoarea linie se afla N numere intregi din multimea {0,1}. Daca al i-lea numar este 1, aceasta inseamna ca obiectivul cu numarul i este o baza militara prietena (adica agentul isi poate reincarca bateriile lanternei daca ajunge la acest obiectiv); daca numarul este 0, agentul nu isi va putea reincarca bateriile. Pe cea de-a treia linie a fisierului se afla numarul M de drumuri dintre obiective. Fiecare din urmatoarele M linii contine cate 4 numere intregi separate prin spatii: a b T W , avand semnificatia ca exista un drum bidirectional intre obiectivele a si b (a<>b), care poate fi parcurs intr-un timp T si cu un consum de W watti.
Pe prima linie a fisierului $lanterna.in$ se afla numerele intregi $N$ si $K$, separate printr-un spatiu. Pe urmatoarea linie se afla $N$ numere intregi din multimea ${0,1}$. Daca al $i$-lea numar este $1$, aceasta inseamna ca obiectivul cu numarul $i$ este o baza militara prietena (adica agentul isi poate reincarca bateriile lanternei daca ajunge la acest obiectiv); daca numarul este 0, agentul nu isi va putea reincarca bateriile. Pe cea de-a treia linie a fisierului se afla numarul $M$ de drumuri dintre obiective. Fiecare din urmatoarele $M$ linii contine cate 4 numere intregi separate prin spatii: $a b T W$, avand semnificatia ca exista un drum bidirectional intre obiectivele $a$ si $b$ $(a<>b)$, care poate fi parcurs intr-un timp $T$ si cu un consum de $W$ watti.
h2. Date de Iesire
In fisierul lanterna.out veti afisa doua numere intregi, separate printr-un spatiu : Tmin si W. Tmin reprezinta durata minima posibila a deplasarii de la obiectivul 1 la obiectivul N, iar W reprezinta tipul de lanterna cu numarul cel mai mic pentru care se obtine acest timp.
In fisierul $lanterna.out$ veti afisa doua numere intregi, separate printr-un spatiu : $Tmin$ si $W$. Tmin reprezinta durata minima posibila a deplasarii de la obiectivul 1 la obiectivul $N$, iar $W$ reprezinta tipul de lanterna cu numarul cel mai mic pentru care se obtine acest timp.
h2. Restrictii si precizari
. 2 <= N <= 50
 
. 1 <= K <= 1000
 
. 1 <= M <= N*(N-1)/2
 
. Intre doua orase diferite poate exista maxim un drum direct.
* $2 &le; N &le; 50$
* $1 &le; K &le; 1000$
* $1 &le; M &le; N*(N-1)/2$
* Intre doua orase diferite poate exista maxim un drum direct.
* Pentru fiecare drum, durata parcurgerii este un numar intreg intre $1$ si $100$, iar numarul de watti consumati este un numar intreg intre $0$ si $1000$
* Se garanteaza ca exista cel putin un tip de lanterna pentru care deplasarea sa fie posibila.
. Pentru fiecare drum, durata parcurgerii este un numar intreg intre 1 si 100, iar numarul de watti consumati este un numar intreg intre 0 si 1000
 
. Se garanteaza ca exista cel putin un tip de lanterna pentru care deplasarea sa fie posibila.
 
h2. Exemplu:
 
lanterna.in lanterna.out
7 10 27 6
h2. Exemplu
table(example). |_. lanterna.in |_. lanterna.out |
| 7 10
0 0 1 0 0 0 0
 
7
 
1 2 10 3
 
1 4 5 5
 
2 3 10 3
 
4 3 15 1
 
3 6 4 3
 
6 5 2 2
 
5 7 1 0
 
5 7 1 0 | 27 6 |
==Include(page="template/taskfooter" task_id="lanterna")==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
471