#1680
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 | #63505993 | Utilizator | |
| Fișier | sushi.cpp | Dimensiune | 3.08 KB |
| Data încărcării | 06 Martie 2026, 09:30 | Scor/rezultat | Eroare de compilare |
sushi.cpp: In function 'int main()': sushi.cpp:32:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = 0; j < neighbors.size(); ++j) { ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_map:47, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:115, from sushi.cpp:1: /usr/include/c++/4.8/bits/hashtable_policy.h: In instantiation of 'struct std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>': /usr/include/c++/4.8/bits/hashtable_policy.h:1402:10: required from 'struct std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true> >' /usr/include/c++/4.8/bits/hashtable.h:174:11: required from 'class std::_Hashtable<std::pair<int, int>, std::pair<int, int>, std::allocator<std::pair<int, int> >, std::__detail::_Identity, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >' /usr/include/c++/4.8/bits/unordered_set.h:96:18: required from 'class std::unordered_set<std::pair<int, int> >' sushi.cpp:65:39: required from here /usr/include/c++/4.8/bits/hashtable_policy.h:1070:12: error: invalid use of incomplete type 'struct std::hash<std::pair<int, int> >' struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, ^ In file included from /usr/include/c++/4.8/bits/basic_string.h:3033:0, from /usr/include/c++/4.8/string:52, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/istream:38, from /usr/include/c++/4.8/sstream:38, from /usr/include/c++/4.8/complex:45, from /usr/include/c++/4.8/ccomplex:38, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:52, from sushi.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<std::pair<int, int> >' struct hash; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_map:47, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:115, from sushi.cpp:1: /usr/include/c++/4.8/bits/hashtable_policy.h:1070:12: error: invalid use of incomplete type 'struct std::hash<std::pair<int, int> >' struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, ^ In file included from /usr/include/c++/4.8/bits/basic_string.h:3033:0, from /usr/include/c++/4.8/string:52, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/istream:38, from /usr/include/c++/4.8/sstream:38, from /usr/include/c++/4.8/complex:45, from /usr/include/c++/4.8/ccomplex:38, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:52, from sushi.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<std::pair<int, int> >' struct hash; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_map:47, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:115, from sushi.cpp:1: /usr/include/c++/4.8/bits/hashtable_policy.h:1082:53: error: invalid use of incomplete type 'struct std::hash<std::pair<int, int> >' using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; ^ In file included from /usr/include/c++/4.8/bits/basic_string.h:3033:0, from /usr/include/c++/4.8/string:52, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/istream:38, from /usr/include/c++/4.8/sstream:38, from /usr/include/c++/4.8/complex:45, from /usr/include/c++/4.8/ccomplex:38, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:52, from sushi.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<std::pair<int, int> >' struct hash; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_map:47, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:115, from sushi.cpp:1: /usr/include/c++/4.8/bits/hashtable_policy.h:1082:53: error: invalid use of incomplete type 'struct std::hash<std::pair<int, int> >' using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; ^ In file included from /usr/include/c++/4.8/bits/basic_string.h:3033:0, from /usr/include/c++/4.8/string:52, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/istream:38, from /usr/include/c++/4.8/sstream:38, from /usr/include/c++/4.8/complex:45, from /usr/include/c++/4.8/ccomplex:38, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:52, from sushi.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<std::pair<int, int> >' struct hash; ^ sushi.cpp: In constructor 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type, const hasher&, const key_equal&, const allocator_type&) [with _Value = std::pair<int, int>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type = unsigned int; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::hasher = std::hash<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::key_equal = std::equal_to<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::allocator_type = std::allocator<std::pair<int, int> >]': sushi.cpp:65:39: error: invalid use of incomplete type 'std::unordered_set<std::pair<int, int> >::hasher {aka struct std::hash<std::pair<int, int> >}' unordered_set<pair<int, int>> visited_states; ^ In file included from /usr/include/c++/4.8/bits/basic_string.h:3033:0, from /usr/include/c++/4.8/string:52, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/istream:38, from /usr/include/c++/4.8/sstream:38, from /usr/include/c++/4.8/complex:45, from /usr/include/c++/4.8/ccomplex:38, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:52, from sushi.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of 'std::unordered_set<std::pair<int, int> >::hasher {aka struct std::hash<std::pair<int, int> >}' struct hash; ^ sushi.cpp:65:39: note: when instantiating default argument for call to std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type, const hasher&, const key_equal&, const allocator_type&) [with _Value = std::pair<int, int>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type = unsigned int; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::hasher = std::hash<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::key_equal = std::equal_to<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::allocator_type = std::allocator<std::pair<int, int> >] unordered_set<pair<int, int>> visited_states; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_map:47, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:115, from sushi.cpp:1: /usr/include/c++/4.8/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_M_hash_code(const _Key&) const [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code = unsigned int]': /usr/include/c++/4.8/bits/hashtable.h:1023:50: required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::iterator std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::find(const key_type&) [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::iterator = std::__detail::_Node_iterator<std::pair<int, int>, true, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::key_type = std::pair<int, int>]' /usr/include/c++/4.8/bits/unordered_set.h:517:29: required from 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::iterator std::unordered_set<_Value, _Hash, _Pred, _Alloc>::find(const key_type&) [with _Value = std::pair<int, int>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::iterator = std::__detail::_Node_iterator<std::pair<int, int>, true, true>; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::key_type = std::pair<int, int>]' sushi.cpp:69:42: required from here /usr/include/c++/4.8/bits/hashtable_policy.h:1103:22: error: no match for call to '(const std::hash<std::pair<int, int> >) (const std::pair<int, int>&)' { return _M_h1()(__k); } ^ /usr/include/c++/4.8/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_Hash_code_base(const _ExtractKey&, const _H1&, const _H2&, const std::__detail::_Default_ranged_hash&) [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing]': /usr/include/c++/4.8/bits/hashtable_policy.h:1463:65: required from 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::_Hashtable_base(const _ExtractKey&, const _H1&, const _H2&, const _Hash&, const _Equal&) [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, true, true>]' /usr/include/c++/4.8/bits/hashtable.h:828:24: required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable(std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&) [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type = unsigned int; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::allocator_type = std::allocator<std::pair<int, int> >]' /usr/include/c++/4.8/bits/hashtable.h:397:26: required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable(std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type, const _H1&, const key_equal&, const allocator_type&) [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type = unsigned int; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::key_equal = std::equal_to<std::pair<int, int> >; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::allocator_type = std::allocator<std::pair<int, int> >]' /usr/include/c++/4.8/bits/unordered_set.h:136:35: required from 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type, const hasher&, const key_equal&, const allocator_type&) [with _Value = std::pair<int, int>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type = unsigned int; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::hasher = std::hash<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::key_equal = std::equal_to<std::pair<int, int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::allocator_type = std::allocator<std::pair<int, int> >]' sushi.cpp:65:39: required from here /usr/include/c++/4.8/bits/hashtable_policy.h:1099:63: error: invalid use of incomplete type 'struct std::hash<std::pair<int, int> >' : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } ^ In file included from /usr/include/c++/4.8/bits/basic_string.h:3033:0, from /usr/include/c++/4.8/string:52, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/istream:38, from /usr/include/c++/4.8/sstream:38, from /usr/include/c++/4.8/complex:45, from /usr/include/c++/4.8/ccomplex:38, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:52, from sushi.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<std::pair<int, int> >' struct hash; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_map:47, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:115, from sushi.cpp:1: /usr/include/c++/4.8/bits/hashtable_policy.h:1099:63: error: invalid use of incomplete type 'struct std::hash<std::pair<int, int> >' : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } ^ In file included from /usr/include/c++/4.8/bits/basic_string.h:3033:0, from /usr/include/c++/4.8/string:52, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/istream:38, from /usr/include/c++/4.8/sstream:38, from /usr/include/c++/4.8/complex:45, from /usr/include/c++/4.8/ccomplex:38, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:52, from sushi.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<std::pair<int, int> >' struct hash; ^ sushi.cpp: In function 'int main()': sushi.cpp:13: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:14: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); ^
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ă.