Fişierul intrare/ieşire:panda.in, panda.outSursăOJI 2015 clasa a 10-a
AutorAdriana SimulescuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Panda (clasa a 10-a)

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:

a) Numărul X de ţarcuri care îndeplinesc proprietatea că ultimele S cifre din reprezentarea binară a codului lor sunt complementare cu ultimele S cifre din reprezentarea binară a codului k purtat de ursuleţ, cu excepţia ţarcului în care se află acesta iniţial.
b) Numărul minim de secunde Smin în care poate ajunge la un ţarc cu mâncare precum şi numărul de ţarcuri cu mâncare nt la care poate ajunge în acest timp minim.

Date de intrare

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

  • pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2;
  • 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

Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerinţă.

În acest caz, în fişierul de ieşire panda.out se va scrie un singur număr natural X, reprezentând numărul total de ţarcuri pe care le poate accesa ursuleţul, cu excepţia ţarcului în care se află acesta iniţial.

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerinţă.

În acest caz, fişierul de ieşire panda.out va conţine numerele naturale naturale Smin şi nt, în această ordine, separate printr-un spaţiu.

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 rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.
  • Pentru 24% dintre teste, se garantează m ≤ 50 şi n ≤ 50.
  • Pentru 20% dintre teste, se garantează S=1.
  • Neimplementat pe varena: Pentru determinarea corectă a numărului Smin se acordă 75% din punctajul testului, iar pentru determinarea corectă a numărului nt se acordă 25% din punctajul testului.

Exemplu

panda.inpanda.outExplicaţie
1
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
19
k=1 şi deoarece S=1 trebuie ca doar ultima cifră binară a lui k să fie diferită de ultima cifră binară a codului din ţarc.
Atenţie! Pentru acest test se rezolvă doar cerinţa a).
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
6 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).
Atenţie! Pentru acest test se rezolvă doar cerinţa b).
Trebuie sa te autentifici pentru a trimite solutii. Click aici