Acest site foloseşte cookies. Navigând în continuare, vă exprimaţi acordul asupra folosirii cookie-urilor.
Detalii evaluare #63395794
Rezumat problemă
#4814
Áles se află într-un castel, reprezentat printr-o matrice A cu N linii și N coloane, fiecare element corespunzând unei camere. Fiecare cameră are asociat câte un număr natural de la 1 la K, care este memorat în elementul corespunzător din matrice. Oricare două camere cu același număr asociat sunt conectate printr-un tunel. De asemenea, fiecare cameră este conectată printr-o ușă cu o cameră vecină, elementele corespunzătoare acestora fiind în matrice pe acceași linie și pe coloane alăturate sau pe aceeași coloană și pe linii alăturate. Scopul lui Áles este să viziteze toate camerele, fiecare cel puțin o dată, astfel încât numerele asociate lor, în ordinea vizitării acestora, să formeze un şir crescător, începând de la 1.
Áles alege la început o cameră care are asociat numărul 1. Din fiecare cameră ce corespunde unui element \(A_{i,j}\) el poate vizita:
- folosind un tunel, orice cameră ce corespunde unui element \(i’,j’\) astfel încât \(A_{i’,j’} = A_{i,j}\).
- folosind o uşă, orice camera vecină cu un număr asociat consecutiv, deci care corespunde unui element \(i’,j’\) astfel încât \( |i’-i|+|j’-j|=1 \) și \(A_{i’,j’}=A_{i,j}+1\).
- folosind un teleportor, în orice cameră cu numărul asociat \(A_{i,j}+1\), la această metodă de deplasare putând să recurgă numai dacă nu poate ajunge la o astfel de cameră utilizând un tunel sau o uşă.
Ați înțeles, Áles doreşte să folosească teleportorul de cât mai puţine ori! El calculează mai întâi numărul minim necesar de teleportări pentru configurația inițială a camerelor, apoi face, pe rând, Q transformări succesive ale configurației, prin schimbarea numărului asociat pentru câte o cameră; după fiecare astfel de transformare, calculează din nou numărul minim necesar de teleportări pentru configurația respectivă.
Pentru configurația inițială, precum și după fiecare dintre cele Q transformări ale acesteia, în ordinea în care sunt realizate, determinați numărul minim de teleportări necesare pentru ca Áles să își îndeplinească scopul.
OJI 2025, clasa a 9-a
Candale Silviu (silviu) Detalii
| Problema | teleportor | Operații I/O |
teleportor.in/teleportor.out
|
|---|---|---|---|
| Limita timp | 0.6 secunde | Limita memorie |
Total: 128 MB
/
Stivă 32 MB
|
| Id soluție | #63395794 | Utilizator |
Lazar Eduard Florin (edy131109)
|
| Fișier | teleportor.cpp | Dimensiune | 5.76 KB |
| Data încărcării | 01 Martie 2026, 18:59 | Scor/rezultat | Eroare de compilare |
Evaluare
Mesaj compilare
In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h: In instantiation of 'struct std::pair<std::tuple<int, int, int>, int>': teleportor.cpp:20:47: required from here /usr/include/c++/4.8/bits/stl_pair.h:101:11: error: 'std::pair<_T1, _T2>::first' has incomplete type _T1 first; /// @c first is a copy of the first object ^ /usr/include/c++/4.8/bits/stl_pair.h:83:11: error: declaration of 'class std::tuple<int, int, int>' class tuple; ^ teleportor.cpp: In function 'int main()': teleportor.cpp:20:70: error: could not convert '{{-1, 0, 2}, 0}' from '<brace-enclosed initializer list>' to 'std::pair<std::tuple<int, int, int>, int>' std::pair<std::tuple<int, int, int>, int> test = { {-1, 0, 2}, 0 }; ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h: In instantiation of 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >': teleportor.cpp:21:176: required from here /usr/include/c++/4.8/bits/stl_pair.h:101:11: error: 'std::pair<_T1, _T2>::first' has incomplete type _T1 first; /// @c first is a copy of the first object ^ /usr/include/c++/4.8/bits/stl_pair.h:83:11: error: declaration of 'class std::tuple<int, int, int>' class tuple; ^ teleportor.cpp:21:176: error: no matching function for call to 'std::pair<std::tuple<int, int, int>, std::vector<room> >::pair(<brace-enclosed initializer list>, std::vector<room>)' std::vector<std::pair<std::tuple<int, int, int>, std::vector<room>>> rooms(k + 1, std::pair<std::tuple<int, int, int>, std::vector<room>>({-1, -1, -1}, std::vector<room>())); ^ teleportor.cpp:21:176: note: candidates are: In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h:206:9: note: template<class ... _Args1, unsigned int ..._Indexes1, class ... _Args2, unsigned int ..._Indexes2> std::pair<_T1, _T2>::pair(std::tuple<_Args1 ...>&, std::tuple<_Args2 ...>&, std::_Index_tuple<_Indexes1 ...>, std::_Index_tuple<_Indexes2 ...>) pair(tuple<_Args1...>&, tuple<_Args2...>&, ^ /usr/include/c++/4.8/bits/stl_pair.h:206:9: note: template argument deduction/substitution failed: teleportor.cpp:21:176: note: 'std::vector<room>' is not derived from 'std::tuple<_Args2 ...>' std::vector<std::pair<std::tuple<int, int, int>, std::vector<room>>> rooms(k + 1, std::pair<std::tuple<int, int, int>, std::vector<room>>({-1, -1, -1}, std::vector<room>())); ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h:155:9: note: template<class ... _Args1, class ... _Args2> std::pair<_T1, _T2>::pair(std::piecewise_construct_t, std::tuple<_Args1 ...>, std::tuple<_Args2 ...>) pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>); ^ /usr/include/c++/4.8/bits/stl_pair.h:155:9: note: template argument deduction/substitution failed: teleportor.cpp:21:176: note: cannot convert '{-1, -1, -1}' (type '<brace-enclosed initializer list>') to type 'std::piecewise_construct_t' std::vector<std::pair<std::tuple<int, int, int>, std::vector<room>>> rooms(k + 1, std::pair<std::tuple<int, int, int>, std::vector<room>>({-1, -1, -1}, std::vector<room>())); ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h:150:12: note: template<class _U1, class _U2, class> constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) constexpr pair(pair<_U1, _U2>&& __p) ^ /usr/include/c++/4.8/bits/stl_pair.h:150:12: note: template argument deduction/substitution failed: teleportor.cpp:21:176: note: candidate expects 1 argument, 2 provided std::vector<std::pair<std::tuple<int, int, int>, std::vector<room>>> rooms(k + 1, std::pair<std::tuple<int, int, int>, std::vector<room>>({-1, -1, -1}, std::vector<room>())); ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h:144:12: note: template<class _U1, class _U2, class> constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) constexpr pair(_U1&& __x, _U2&& __y) ^ /usr/include/c++/4.8/bits/stl_pair.h:144:12: note: template argument deduction/substitution failed: teleportor.cpp:21:176: note: couldn't deduce template parameter '_U1' std::vector<std::pair<std::tuple<int, int, int>, std::vector<room>>> rooms(k + 1, std::pair<std::tuple<int, int, int>, std::vector<room>>({-1, -1, -1}, std::vector<room>())); ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h:138:12: note: template<class _U2, class> constexpr std::pair<_T1, _T2>::pair(const _T1&, _U2&&) constexpr pair(const _T1& __x, _U2&& __y) ^ /usr/include/c++/4.8/bits/stl_pair.h:138:12: note: template argument deduction/substitution failed: teleportor.cpp:21:176: note: cannot convert '{-1, -1, -1}' (type '<brace-enclosed initializer list>') to type 'const std::tuple<int, int, int>&' std::vector<std::pair<std::tuple<int, int, int>, std::vector<room>>> rooms(k + 1, std::pair<std::tuple<int, int, int>, std::vector<room>>({-1, -1, -1}, std::vector<room>())); ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h:133:12: note: template<class _U1, class> constexpr std::pair<_T1, _T2>::pair(_U1&&, const _T2&) constexpr pair(_U1&& __x, const _T2& __y) ^ /usr/include/c++/4.8/bits/stl_pair.h:133:12: note: template argument deduction/substitution failed: teleportor.cpp:21:176: note: couldn't deduce template parameter '_U1' std::vector<std::pair<std::tuple<int, int, int>, std::vector<room>>> rooms(k + 1, std::pair<std::tuple<int, int, int>, std::vector<room>>({-1, -1, -1}, std::vector<room>())); ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h:128:17: note: constexpr std::pair<_T1, _T2>::pair(std::pair<_T1, _T2>&&) [with _T1 = std::tuple<int, int, int>; _T2 = std::vector<room>] constexpr pair(pair&&) = default; ^ /usr/include/c++/4.8/bits/stl_pair.h:128:17: note: candidate expects 1 argument, 2 provided /usr/include/c++/4.8/bits/stl_pair.h:127:17: note: constexpr std::pair<_T1, _T2>::pair(const std::pair<_T1, _T2>&) [with _T1 = std::tuple<int, int, int>; _T2 = std::vector<room>] constexpr pair(const pair&) = default; ^ /usr/include/c++/4.8/bits/stl_pair.h:127:17: note: candidate expects 1 argument, 2 provided /usr/include/c++/4.8/bits/stl_pair.h:124:12: note: template<class _U1, class _U2, class> constexpr std::pair<_T1, _T2>::pair(const std::pair<_U1, _U2>&) constexpr pair(const pair<_U1, _U2>& __p) ^ /usr/include/c++/4.8/bits/stl_pair.h:124:12: note: template argument deduction/substitution failed: teleportor.cpp:21:176: note: candidate expects 1 argument, 2 provided std::vector<std::pair<std::tuple<int, int, int>, std::vector<room>>> rooms(k + 1, std::pair<std::tuple<int, int, int>, std::vector<room>>({-1, -1, -1}, std::vector<room>())); ^ In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0, from /usr/include/c++/4.8/bits/char_traits.h:39, from /usr/include/c++/4.8/ios:40, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/stl_pair.h:112:26: note: constexpr std::pair<_T1, _T2>::pair(const _T1&, const _T2&) [with _T1 = std::tuple<int, int, int>; _T2 = std::vector<room>] _GLIBCXX_CONSTEXPR pair(const _T1& __a, const _T2& __b) ^ /usr/include/c++/4.8/bits/stl_pair.h:112:26: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::tuple<int, int, int>&' /usr/include/c++/4.8/bits/stl_pair.h:108:26: note: constexpr std::pair<_T1, _T2>::pair() [with _T1 = std::tuple<int, int, int>; _T2 = std::vector<room>] _GLIBCXX_CONSTEXPR pair() ^ /usr/include/c++/4.8/bits/stl_pair.h:108:26: note: candidate expects 0 arguments, 2 provided teleportor.cpp:37:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = 0; j < connected_rooms.second.size(); j++) { ^ teleportor.cpp:46:37: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' connected_rooms.first = {j, i2, j2}; ^ teleportor.cpp:55:13: error: 'get' is not a member of 'std' if (std::get<0>(connected_rooms.first) == -1) teleportations++; ^ teleportor.cpp:55:41: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' if (std::get<0>(connected_rooms.first) == -1) teleportations++; ^ teleportor.cpp:76:44: error: 'get' is not a member of 'std' room& tpElement = kRoom.second[std::get<0>(kRoom.first)]; ^ teleportor.cpp:76:62: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' room& tpElement = kRoom.second[std::get<0>(kRoom.first)]; ^ teleportor.cpp:79:59: error: 'get' is not a member of 'std' kRoom.second.erase(kRoom.second.begin() + std::get<0>(kRoom.first)); ^ teleportor.cpp:79:77: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' kRoom.second.erase(kRoom.second.begin() + std::get<0>(kRoom.first)); ^ teleportor.cpp:83:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = 0; j < kRoom.second.size(); j++) { ^ teleportor.cpp:99:27: error: 'get' is not a member of 'std' if (c != k && std::get<0>(kRoom.first) == -1) shouldCheckSelf = true; ^ teleportor.cpp:99:45: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' if (c != k && std::get<0>(kRoom.first) == -1) shouldCheckSelf = true; ^ teleportor.cpp:107:23: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' kRoom.first = { kRoom.second.size() - 1, i2, j2 }; ^ teleportor.cpp:112:21: error: 'get' is not a member of 'std' if (std::get<0>(rooms[initialValue - 1].first) != -1) { ^ teleportor.cpp:112:57: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<std::tuple<int, int, int>, std::vector<room> > > >::value_type' has no member named 'first' if (std::get<0>(rooms[initialValue - 1].first) != -1) { ^ teleportor.cpp:113:25: error: 'get' is not a member of 'std' if (std::get<1>(rooms[initialValue - 1].first) == i1 && std::get<2>(rooms[initialValue - 1].first) == j1) { ^ teleportor.cpp:113:61: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<std::tuple<int, int, int>, std::vector<room> > > >::value_type' has no member named 'first' if (std::get<1>(rooms[initialValue - 1].first) == i1 && std::get<2>(rooms[initialValue - 1].first) == j1) { ^ teleportor.cpp:113:77: error: 'get' is not a member of 'std' if (std::get<1>(rooms[initialValue - 1].first) == i1 && std::get<2>(rooms[initialValue - 1].first) == j1) { ^ teleportor.cpp:113:113: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<std::tuple<int, int, int>, std::vector<room> > > >::value_type' has no member named 'first' if (std::get<1>(rooms[initialValue - 1].first) == i1 && std::get<2>(rooms[initialValue - 1].first) == j1) { ^ teleportor.cpp:114:87: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int)' if (std::find(toCheck.begin(), toCheck.end(), initialValue - 1) == toCheck.end()) { ^ teleportor.cpp:114:87: note: candidate is: In file included from /usr/include/c++/4.8/bits/locale_facets.h:48:0, from /usr/include/c++/4.8/bits/basic_ios.h:37, from /usr/include/c++/4.8/ios:44, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/streambuf_iterator.h:369:5: note: template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&) find(istreambuf_iterator<_CharT> __first, ^ /usr/include/c++/4.8/bits/streambuf_iterator.h:369:5: note: template argument deduction/substitution failed: teleportor.cpp:114:87: note: '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>' if (std::find(toCheck.begin(), toCheck.end(), initialValue - 1) == toCheck.end()) { ^ teleportor.cpp:121:21: error: 'get' is not a member of 'std' if (std::get<0>(rooms[c - 1].first) == -1) { ^ teleportor.cpp:121:46: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<std::tuple<int, int, int>, std::vector<room> > > >::value_type' has no member named 'first' if (std::get<0>(rooms[c - 1].first) == -1) { ^ teleportor.cpp:122:72: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int)' if (std::find(toCheck.begin(), toCheck.end(), c - 1) == toCheck.end()) { ^ teleportor.cpp:122:72: note: candidate is: In file included from /usr/include/c++/4.8/bits/locale_facets.h:48:0, from /usr/include/c++/4.8/bits/basic_ios.h:37, from /usr/include/c++/4.8/ios:44, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from teleportor.cpp:1: /usr/include/c++/4.8/bits/streambuf_iterator.h:369:5: note: template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&) find(istreambuf_iterator<_CharT> __first, ^ /usr/include/c++/4.8/bits/streambuf_iterator.h:369:5: note: template argument deduction/substitution failed: teleportor.cpp:122:72: note: '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>' if (std::find(toCheck.begin(), toCheck.end(), c - 1) == toCheck.end()) { ^ teleportor.cpp:129:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = 0; j < toCheck.size(); j++) { ^ teleportor.cpp:132:33: error: 'get' is not a member of 'std' bool hadInitially = std::get<0>(connected_rooms.first) != -1; ^ teleportor.cpp:132:61: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' bool hadInitially = std::get<0>(connected_rooms.first) != -1; ^ teleportor.cpp:134:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int l = 0; l < connected_rooms.second.size(); l++) { ^ teleportor.cpp:143:41: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' connected_rooms.first = { j, i2, j2 }; ^ teleportor.cpp:152:17: error: 'get' is not a member of 'std' if (std::get<0>(connected_rooms.first) == -1 && hadInitially) teleportations++; ^ teleportor.cpp:152:45: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' if (std::get<0>(connected_rooms.first) == -1 && hadInitially) teleportations++; ^ teleportor.cpp:153:22: error: 'get' is not a member of 'std' else if (std::get<0>(connected_rooms.first) != -1 && !hadInitially) teleportations--; ^ teleportor.cpp:153:50: error: 'struct std::pair<std::tuple<int, int, int>, std::vector<room> >' has no member named 'first' else if (std::get<0>(connected_rooms.first) != -1 && !hadInitially) teleportations--; ^
Cum funcționează evaluarea?
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
- probleme la care rezolvarea presupune scrierea unui program complet
- probleme la care rezolvarea presupune scrierea unei secvențe de program - câteva instrucțiuni, o listă de declarații, una sau mai multe funcții, etc.
Problema teleportor face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
- Programul sursă este compilat folosind compilatorul corespunzător. Dacă în urma compilării se obțin erori sau avertismente, acestea sunt afișate în această pagină.
- Dacă programul a fost compilat, executabilul obținut va fi rulat, furnizându-i-se unul sau mai multe seturi de date de intrare, în concordanță cu restricțiile specifice problemei. Pentru fiecare set de date se obține un anumit punctaj, în raport cu corectitudinea soluției tale.
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ă.