Soluții trimise

Rezumat problemă

#1680 Sushi

După o zi productivă de făcut curățenie, Henry și Hetty au ieșit în oraș la un restaurant de sushi. În acest restaurant există N mese unite între ele prin N-1 benzi rulante cu dublu sens, astfel încât oricare două mese sunt conectate direct sau indirect prin benzi rulante. Pentru fiecare masă i, 1 ≤ i ≤ N, cunoaștem atât numărul K[i] de mese cu care este conectată direct, cât și lista ordonată de mese vecine acesteia: V[i,1], V[i,2]V[i,K[i]].

Benzile rulante au rolul de a transporta preparatele la clienți. Acestea urmează un traseu unic, definit după următoarea regulă: pentru orice masă i, un preparat aflat la masa i care tocmai a venit dinspre masa V[i,j], va pleca de la masa i spre masa:

  • V[i,j+1], dacă 1 ≤ j < K[i]
  • V[i,1], dacă j = K[i].

În plus, dacă un preparat nou este trimis de la masa 1 spre masa V[1,1], știm că acesta va ajunge la masa i pentru prima oară venind dinspre masa V[i,1], pentru orice i, 1 ≤ i ≤ N.

Henry și Hetty au intrat în restaurant la momentul de timp 0. Ei știu că pe parcursul vizitei lor pe benzile rulante vor fi așezate M preparate. Pentru fiecare din cele M preparate ei cunosc tripletul (x, y, t), semnificând faptul că la momentul de timp t preparatul va fi așezat pe bandă în dreptul mesei x pentru a pleca spre spre masa V[x,y]. Ei mai știu și că timpul necesar unui preparat de a parcurge distanța dintre două mese vecine este de o unitate. Cei doi se vor așeza la o masă și vor lua de pe bandă toate preparatele care trec prin dreptul mesei respective. Henry și Hetty se întreabă: pentru fiecare masă i, care este timpul minim după care culeg toate cele M preparate ce vor fi puse pe bandă?

ONI 2016, clasele XI-XII

ID   Utilizator Problema Data încărcării Stare
Fazacaș Mihai Tudor (FazacasMihai) Sushi 08 Martie 2024, 10:49 Evaluare finalizată E.C
Ghica Tudor (Gtudor) Sushi 15 Februarie 2024, 23:21 Evaluare finalizată 100
Ghica Tudor (Gtudor) Sushi 15 Februarie 2024, 23:12 Evaluare finalizată 60
Ghica Tudor (Gtudor) Sushi 15 Februarie 2024, 23:10 Evaluare finalizată 35
Ghica Tudor (Gtudor) Sushi 15 Februarie 2024, 22:41 Evaluare finalizată 35
Ghica Tudor (Gtudor) Sushi 15 Februarie 2024, 22:31 Evaluare finalizată 5
POPESCU ANDREI (andreip99) Sushi 24 Ianuarie 2024, 15:50 Evaluare finalizată 100
Bostina George Eduard (eduard02) Sushi 08 Noiembrie 2023, 20:39 Evaluare finalizată 0
Prof C.N. "Spiru Haret" (flaviusboian) Sushi 03 Septembrie 2023, 00:00 Evaluare finalizată 100
Adrian Statescu (thinkphp) Sushi 03 Iulie 2023, 13:37 Evaluare finalizată 100
Adrian Statescu (thinkphp) Sushi 03 Iulie 2023, 13:35 Evaluare finalizată 100
Boaca Andrei (andreivkrekvei) Sushi 15 Iunie 2023, 09:30 Evaluare finalizată 100
Moldovan Robert (use KN) (moldovan_robert_lol) Sushi 22 Mai 2023, 17:25 Evaluare finalizată 100
Iosif Andrei Stefan (Iosif_Andrei_Stefan) Sushi 30 Martie 2023, 00:44 Evaluare finalizată 100
Popescu Sebastian (USER1234567) Sushi 30 Martie 2023, 00:44 Evaluare finalizată 100
Popescu Sebastian (USER1234567) Sushi 30 Martie 2023, 00:37 Evaluare finalizată 0
ROTARIU EMANUEL (Emmy) Sushi 29 Martie 2023, 19:37 Evaluare finalizată 100
ROTARIU EMANUEL (Emmy) Sushi 29 Martie 2023, 19:36 Evaluare finalizată 40
ROTARIU EMANUEL (Emmy) Sushi 29 Martie 2023, 19:24 Evaluare finalizată 10
ROTARIU EMANUEL (Emmy) Sushi 29 Martie 2023, 19:22 Evaluare finalizată E.C
ROTARIU EMANUEL (Emmy) Sushi 29 Martie 2023, 19:21 Evaluare finalizată 10
ROTARIU EMANUEL (Emmy) Sushi 29 Martie 2023, 19:20 Evaluare finalizată 10
Pirvulescu Serban (Zexsoft) Sushi 28 Martie 2023, 17:23 Evaluare finalizată 0
Duguleanu Ana-Valeria (anavaleria) Sushi 28 Martie 2023, 13:43 Evaluare finalizată 100
Iordachioaiei Alex (AlexInfo3) Sushi 23 Martie 2023, 15:37 Evaluare finalizată 40
Iordachioaiei Alex (AlexInfo3) Sushi 23 Martie 2023, 14:53 Evaluare finalizată E.C
Gheorghies Alexandru (andu2006) Sushi 23 Martie 2023, 11:14 Evaluare finalizată 100
Gheorghies Alexandru (andu2006) Sushi 23 Martie 2023, 11:14 Evaluare finalizată 100
Gheorghies Alexandru (andu2006) Sushi 23 Martie 2023, 10:56 Evaluare finalizată 0
Dumitru Alexandru (DumitruDaniel) Sushi 22 Martie 2023, 12:04 Evaluare finalizată 100
Dumitru Alexandru (DumitruDaniel) Sushi 21 Martie 2023, 16:28 Evaluare finalizată 40
Eugen Mariel (Ionut_2004_2) Sushi 13 Martie 2023, 21:29 Evaluare finalizată 100
Munteanu Gheorghe (9amurgoci) Sushi 28 Februarie 2023, 09:01 Evaluare finalizată 100
Munteanu Gheorghe (9amurgoci) Sushi 28 Februarie 2023, 08:59 Evaluare finalizată 0
Cotiga David (davidcotiga) Sushi 18 Februarie 2023, 12:28 Evaluare finalizată 100
Coman Isabela (isabela_c) Sushi 05 Februarie 2023, 22:03 Evaluare finalizată 100
Toncea Andrei (andrei170) Sushi 07 Ianuarie 2023, 00:17 Evaluare finalizată 100
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Sushi 02 Ianuarie 2023, 19:25 Evaluare finalizată 100
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Sushi 02 Ianuarie 2023, 19:24 Evaluare finalizată 50
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Sushi 02 Ianuarie 2023, 19:24 Evaluare finalizată 100
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Sushi 02 Ianuarie 2023, 19:14 Evaluare finalizată 60
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Sushi 02 Ianuarie 2023, 19:14 Evaluare finalizată 40
NU INTRA PE ARTICOLELE MELE ❌ DOLTEANU GABRIEL (arcker) Sushi 01 Ianuarie 2023, 17:19 Evaluare finalizată 100
Alexutan Cristian (cristi_a) Sushi 29 Decembrie 2022, 11:12 Evaluare finalizată 100
Alexutan Cristian (cristi_a) Sushi 29 Decembrie 2022, 11:12 Evaluare finalizată 0
Doru Floare (Doruletz) Sushi 31 Octombrie 2022, 08:55 Evaluare finalizată 100
Suspicious Soup (0p) Sushi 31 Octombrie 2022, 08:54 Evaluare finalizată 100
Suspicious Soup (0p) Sushi 31 Octombrie 2022, 08:48 Evaluare finalizată 50
Suspicious Soup (0p) Sushi 31 Octombrie 2022, 08:47 Evaluare finalizată 0
Suspicious Soup (0p) Sushi 31 Octombrie 2022, 08:16 Evaluare finalizată 10