#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
Problema | Sushi | Operații I/O |
![]() sushi.in /sushi.out
|
---|---|---|---|
Limita timp | 0.8 secunde | Limita memorie |
Total: 128 MB
/
Stivă 128 MB
|
Id soluție | #36050837 | Utilizator | |
Fișier | sushi.cpp | Dimensiune | 2.23 KB |
Data încărcării | 02 Aprilie 2022, 13:42 | Scor / rezultat | 100 puncte |
sushi.cpp: In function 'int main()': sushi.cpp:76:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = 0; j < poz[i].size(); j++) ^ sushi.cpp:37:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen("sushi.in", "r", stdin); ^ sushi.cpp:38:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen("sushi.out", "w", stdout); ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
1 | 0 secunde | OK. | 5 | 5 | ||
2 | 0 secunde | OK. | 5 | 5 | ||
3 | 0 secunde | OK. | 5 | 5 | ||
4 | 0 secunde | OK. | 5 | 5 | ||
5 | 0 secunde | OK. | 5 | 5 | ||
6 | 0 secunde | OK. | 5 | 5 | ||
7 | 0.004 secunde | OK. | 5 | 5 | ||
8 | 0.004 secunde | OK. | 5 | 5 | ||
9 | 0.096 secunde | OK. | 5 | 5 | ||
10 | 0.104 secunde | OK. | 5 | 5 | ||
11 | 0.196 secunde | OK. | 5 | 5 | ||
12 | 0.16 secunde | OK. | 5 | 5 | ||
13 | 0.212 secunde | OK. | 5 | 5 | ||
14 | 0.184 secunde | OK. | 5 | 5 | ||
15 | 0.24 secunde | OK. | 5 | 5 | ||
16 | 0.236 secunde | OK. | 5 | 5 | ||
17 | 0.276 secunde | OK. | 5 | 5 | ||
18 | 0.288 secunde | OK. | 5 | 5 | ||
19 | 0.288 secunde | OK. | 5 | 5 | ||
20 | 0.288 secunde | OK. | 5 | 5 | ||
Punctaj total | 100 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Sushi face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.