#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 | #35396850 | Utilizator | |
Fișier | sushi.cpp | Dimensiune | 2.25 KB |
Data încărcării | 08 Martie 2022, 10:50 | Scor / rezultat | 100 puncte |
sushi.cpp: In function 'void precalc()': sushi.cpp:30:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i=0; i<euler.size(); i++) ^ sushi.cpp: In function 'int main()': sushi.cpp:64:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i=2; i<=euler.size(); i++) ^ sushi.cpp:77:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i = 1; (1 << i)<=euler.size(); i++) ^ sushi.cpp:79:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j = 0; j+(1 << i)-1<euler.size(); j++) ^ sushi.cpp:86:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<pz[i].size(); j++) ^ sushi.cpp:88:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if(j!=adj[i].size()-1) ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
1 | 0.004 secunde | OK. | 5 | 5 | ||
2 | 0.004 secunde | OK. | 5 | 5 | ||
3 | 0.004 secunde | OK. | 5 | 5 | ||
4 | 0.004 secunde | OK. | 5 | 5 | ||
5 | 0.004 secunde | OK. | 5 | 5 | ||
6 | 0.004 secunde | OK. | 5 | 5 | ||
7 | 0.008 secunde | OK. | 5 | 5 | ||
8 | 0.004 secunde | OK. | 5 | 5 | ||
9 | 0.108 secunde | OK. | 5 | 5 | ||
10 | 0.112 secunde | OK. | 5 | 5 | ||
11 | 0.18 secunde | OK. | 5 | 5 | ||
12 | 0.156 secunde | OK. | 5 | 5 | ||
13 | 0.212 secunde | OK. | 5 | 5 | ||
14 | 0.176 secunde | OK. | 5 | 5 | ||
15 | 0.236 secunde | OK. | 5 | 5 | ||
16 | 0.244 secunde | OK. | 5 | 5 | ||
17 | 0.292 secunde | OK. | 5 | 5 | ||
18 | 0.276 secunde | OK. | 5 | 5 | ||
19 | 0.272 secunde | OK. | 5 | 5 | ||
20 | 0.292 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ă.