Lista de probleme 2

Etichete

#2894 Barlog

Este anul 2019, dar Zmeul-Cel-Rău și Făt-Frumos luptă în continuare. Zmeul l-a prins pe Făt-Frumos şi l-a închis în una dintre camerele bârlogului său. Un bârlog de zmeu are forma unui tablou bidimensional, în care camerele sunt plasate sub forma a n linii și m coloane. Vom numerota liniile de la 1 la n, iar coloanele de la 1 la m, astfel că fiecare cameră poate fi identificată prin numărul liniei și al coloanei pe care se află.

Orice cameră are patru pereți și câte o ușă pe fiecare perete prin care poate comunica cu camerele învecinate. Mai exact, camera de pe linia i și coloana j poate comunica cu camerele (i-1,j), (i,j+1), (i+1,j), (i,j-1) (desigur, dacă acestea există). Fiecare cameră are asociat un cod. Ușile din orice cameră se pot deschide cu o cartelă magnetică. Dacă codul camerei este un subșir al cuvântului memorat pe cartela magnetică, atunci ușile din camera respectivă se vor deschide folosind cartela. Ileana Cosânzeana a reușit să-i trimită lui Făt-Frumos o cartelă magnetică.

Scrieți un program care rezolvă următoarele două cerințe:
1. determină numărul de camere în care ar putea ajunge Făt-Frumos folosind cartela primită de la Ileana Cosânzeana;
2. determină numărul minim de camere prin care trece Făt-Frumos pentru a ieși din bârlogul zmeului (adică poate deschide ușa unei camere prin care ajunge în exteriorul bârlogului).

Olimpiada Municipală Iași, clasa a X-a

La un supermarket există două case de marcat la care clienții își pot plăti cumpărăturile. Când intră în magazin, fiecare client primește un număr unic. Când aceștia vor să plătească, se așază la rând la una dintre cele două case. Clienții sunt procesați pe rând, în ordinea venirii lor.
Scrieți un program care procesează cozile de la casele de marcat. Acest program primește N instrucțiuni pe care trebuie să le execute. Aceste instrucțiuni pot fi de următoarele 4 tipuri:

  • 1 – S-a eliberat casa de marcat numărul 1. Trebuie afișat numărul clientului care urmează la rând; dacă nu este nimeni la coadă la casa respectivă, se va afișa -1.
  • 2 – S-a eliberat casa de marcat numărul 2. Trebuie afișat numărul clientului care urmează la rând; dacă nu este nimeni la coadă la casa respectivă, se va afișa -1.
  • 3 x – Clientul cu numărul x se așază la coadă la casa la care așteaptă mai puțini clienți; dacă la ambele case așteaptă același număr de clienți, atunci clientul cu numărul x se va așeza la coadă la casa 1; trebuie afișată coada la care se așază clientul x. Se garantează că acest client nu este deja așezat la vreun la rând.
  • 4 x – Clientul cu numărul x părăsește rândul la care așteaptă (se garantează că era deja la un rând); în acest caz nu trebuie afișat nimic.

Olimpiada Municipală Iași, clasa a X-a