Rezumat problemă

Blind

#5004

Fie o matrice de dimensiuni 𝑁 × 𝑀 care conține numai valorile 0 și 1. Căsuțele marcate cu 0 sunt inaccesibile, în timp ce căsuțele marcate cu 1 sunt accesibile.

Gimi se va afla inițial într-o căsuță marcată cu 1 din această matrice, poziția ei nefiind însă cunoscută nouă. Lui Gimi îi putem da instrucțiuni de tipul: deplasează-te în căsuța (𝑥𝑑 , 𝑦𝑑). Regulile sunt următoarele:

• Gimi se poate deplasa numai în căsuțe marcate cu 1.
• Gimi se poate deplasa numai în căsuțe vecine cu cea în care se află. Căsuțele vecine cu (𝑥, 𝑦) sunt (cât timp sunt în matrice): (𝑥 − 1, 𝑦), (𝑥, 𝑦 + 1), (𝑥 + 1, 𝑦) și (𝑥, 𝑦 − 1).

Dacă Gimi poate respecta toate regulile, atunci acesta se va deplasa în căsuța (𝑥𝑑 , 𝑦𝑑). Altfel, va rămâne pe loc.

Scrieți un program care, cunoscând 𝑁 și 𝑀, respectiv matricea, determină:

Cerința 1. O serie de instrucțiuni pe care, dacă Gimi o urmărește, indiferent de poziția lui inițială, ne va garanta faptul că va trece prin căsuța (𝑥𝑡 , 𝑦𝑡) (marcată cu 1).
Cerința 2. O serie de instrucțiuni pe care, dacă Gimi o urmărește, indiferent de poziția lui inițială, ne va garanta faptul că va trece prin toate celelalte căsuțe marcate cu 1.
Cerința 3. Cel mai mic număr 𝑃 astfel încât, primind o serie de 𝑄 instrucțiuni pe care, dacă Gimi o urmărește, indiferent de poziția lui de start, ne va garanta faptul că va trece prin toate celelalte căsuțe marcate cu 1, fără să fie necesară executarea instrucțiunilor de la 𝑃 + 1 la 𝑄.

ONI 2026, clasa a 10-a

Fișiere Candale Silviu (silviu) Ioan-Cristian Pop concurs

Clasa 10 Structuri de date liniare Coada

Rezolvă

Detalii

Problema	Blind	Operații I/O	blind.in/blind.out
Limita timp	1 secunde	Limita memorie	Total: 128 MB / Stivă 8 MB
Id soluție	#64177833	Utilizator	Andrei Visalon (Prekzursil)
Fișier	blind.cpp	Dimensiune	4.58 KB
Data încărcării	21 Aprilie 2026, 18:54	Scor/rezultat	100 puncte

Evaluare

Mesaj compilare

blind.cpp: In function ‘void solve3()’:
blind.cpp:69:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   69 |         auto [x, y] = pos[i];
      |              ^
blind.cpp:80:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   80 |         auto [x, y] = v[i];
      |              ^
blind.cpp: In function ‘void solve()’:
blind.cpp:163:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  163 |         for (auto [x, y] : moves) {
      |                   ^
blind.cpp:168:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  168 |         auto [x, y] = pos[1];
      |              ^
blind.cpp:176:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  176 |         for (auto [x, y] : moves) {
      |                   ^
blind.cpp: In function ‘int main()’:
blind.cpp:194:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  194 |     freopen("blind.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
blind.cpp:195:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  195 |     freopen("blind.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Rezultat evaluare

Cum funcționează evaluarea?