Fişierul intrare/ieşire:pandele.in, pandele.outSursăOJI 2015 clasa a 10-a
AutorAdriana SimulescuAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Pandele (clasa a 10-a)

Aceasta este o versiunea modificată a problemei originale panda. Pluralul substantivului panda nu este pandele.

O rezervaţie de urşi panda, privită de sus, are formă dreptunghiulară şi este compusă din n rânduri identice, iar pe fiecare rând sunt m ţarcuri identice cu baza pătrată. Ţarcurile sunt îngrădite şi sunt prevăzute cu uşi către toate cele 4 ţarcuri vecine. Uşile sunt prevăzute cu câte un cod de acces, ca atare acestea se închid şi se deschid automat. Prin acest sistem, unele ţarcuri sunt accesibile ursuleţilor, iar altele le sunt interzise acestora. În T ţarcuri se găseşte mâncare pentru ursuleţi.

Ursuleţii din rezervaţie poartă câte un microcip care le deschide automat uşile ţarcurilor unde pot intra şi închide automat uşile ţarcurilor interzise. Un ţarc este accesibil ursuleţului dacă ultimele S cifre ale reprezentărilor binare ale codului ţarcului şi ale codului k de pe microcip sunt complementare. (Exemplu: pentru S=8, 11101011 şi 00010100 sunt complementare).

Într-un ţarc este un ursuleţ căruia i s-a făcut foame. Ursuleţul se deplasează doar paralel cu laturile dreptunghiului. Trecerea dintr-un ţarc în altul vecin cu el se face într-o secundă.

Cerinţă

Cunoscând n şi m dimensiunile rezervaţiei, codurile de acces de la fiecare dintre cele n*m ţarcuri, coordonatele celor T ţarcuri cu mâncare, coordonatele ţarcului L şi C unde se află iniţial ursuleţul, codul k al microcipului său şi numărul S, determinaţi:

Un drum pe care ursuleţul în poate parcurge într-un timp cât mai scurt de la ţarcul în care se află iniţial la unul dintre ţarcurile cu mâncare.

Date de intrare

Fişierul de intrare pandele.in conţine:

  • pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p este irelevant;
  • pe a doua linie trei numere naturale n, m şi T separate prin câte un spaţiu, cu semnificaţiile din enunţ;
  • pe linia a treia patru numere naturale nenule L, C, k şi S, separate prin câte un spaţiu, cu semnificaţiile din enunţ;
  • pe următoarele T linii câte două numere naturale reprezentând coordonatele ţarcurilor cu mâncare;
  • pe următoarele n linii câte m numere naturale, separate prin câte un spaţiu, reprezentând codurile de acces la uşile din cele n*m ţarcuri ale rezervaţiei.

Date de ieşire

Fişierul de ieşire pandele.out va conţine perechi de numere naturale (Li şi Ci), fiecare pe câte o linie, reprezentând o succesiune de coordonate ale căsuţelor prin care ursuleţul trebuie să treacă pentru a ajunge din căsuţa iniţială la o căsuţă cu mâncare într-un timp cât mai scurt.

Restricţii

  • 2 ≤ n,m ≤ 500
  • 1 ≤ S ≤ 8
  • 1 ≤ T < n*m
  • 0 ≤ k, valorile codurilor ≤ 9.999
  • Pentru toate testele problemei există soluţie, adică ursuleţul poate ajunge la cel puţin unul dintre ţarcurile cu mâncare.
  • Mâncarea se poate găsi şi în zone inaccesibile.
  • Pentru 24% dintre teste, se garantează m ≤ 50 şi n ≤ 50.
  • Pentru 20% dintre teste, se garantează S=1.

Exemplu

pandele.inpandele.outExplicaţie
2
5 6 4
3 5 1 1
1 2
5 1
2 1
4 3
15 1278 3 1278 1278 1
16 17 18 19 254 20
21 25 26 254 254 254
27 28 29 3 2 254
2 254 4 254 254 254
3 5
4 5
5 5
5 4
5 3
5 2
5 1
Dacă notăm cu 1 ţarcurile accesibile şi cu 0 cele inaccesibile, obţinem următoarea matrice:
0 0 0 1 1 0
0 0 1 0 1 1
0 0 1 1 1 1
0 1 0 0 1 1
1 1 1 1 1 1
Ursuleţul se află în ţarcul de coordonate (3,5) şi poate ajunge la un singur ţarc cu mâncare, după 6 secunde.
Acest ţarc este cel de la coordonatele (5,1); drumul parcurs este (3,5)→(4,5)→(5,5)→(5,4)→(5,3)→(5,2)→(5,1).
Trebuie sa te autentifici pentru a trimite solutii. Click aici