Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | veri.in, veri.out | Sursă | OJI 2023, clasele 11-12 |
| Autor | Vlad Adrian Ulmeanu | Adăugată de |  Ivan Andrei •IvanAndrei |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Veri
Se dă un graf orientat cu n noduri şi m muchii. Fiecare muchie are costul 1 (poate fi parcursă într-un minut). Doi "prieteni" (veri) pornesc din nodul S. Unul dintre ei vrea să ajungă în nodul A, iar celălalt vrea să ajungă în nodul B.
Cei doi prieteni se vor plimba împreună până când ciclează, adică până când vor ajunge în acelaşi nod a doua oară, notat cu Z. După ciclare, ei îşi pot continua drumurile separat. Totuşi, dacă vor, pot să meargă amândoi în
continuare pe acelaşi drum: doar dispare obligaţia de a merge împreună.
Fiecare dintre ei trebuie să-şi termine drumul doar după ciclare, adică după ce nu mai sunt obligaţi să meargă împreună. Totuşi, este în regulă dacă drumul unuia se termină exact în nodul în care au ciclat (adică ciclează în A sau B).
Care este numărul minim de minute necesar, astfel încât să fie posibil ca amândoi să ajungă la destinaţiile lor, în timpul alocat, în A, respectiv B?
Cu alte cuvinte, dacă cei doi veri ciclează pentru prima oară după exact t minute, apoi îşi continuă drumurile pentru alte tA, respectiv tB minute, vrem să aflăm valoarea minimă a lui max(t + tA, t + tB).
Există două tipuri de cerinţe, reprezentate printr-un număr c:
- Dacă c = 1, trebuie calculată valoarea minimă a lui max(t + tA, t + tB).
Date de intrare
Fişierul de intrare veri.in ...
Date de ieşire
În fişierul de ieşire veri.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| veri.in | veri.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
