Revizia anterioară Revizia următoare
Soluţii Urmasii lui Moisil 2015
test
Rox
Autor: stud. Liana Ştefania Ţucăr
Descrierea soluţiei (stud. Marta Diana Filimon)
Solutie – 100 p
Pentru a reţine tipul florilor care sunt plantate în celula de pe linia L şi coloana C vom utiliza un tip de date care este reprezentat pe 32 de biţi şi vom utiliza cei mai nesemnificativi (aceştia fiind ultimii) 26 de biţi, astfel: cel de al k-lea bit este 1 dacă floarea care are numele celei de a (k+1)-a literă a alfabetului englez apare pe linia L şi coloana C, unde 0 <= k <= 25.
Pentru o parcelă de coordonate L1, C1, L2, C2 pe care se plantează o floare de tipul T se procedează astfel: vom aplica operaţia xor cu valoarea 1 deplasată la stânga cu k biţi, unde k reprezintă numărul de ordine al literei în alfabet mărit cu 1, în celulele de coordonate (L1, C1), (L2, C2+1), (L2+1, C1), (L2+1, C2+1).
Vom face suma xor pentru elementele aflate în submatricea care are colţurile în celulele (1, 1) şi (L, C) oricare ar fi L şi C cu 1 <= L <= N; 1 <= C <= M. Apoi, pentru a răspunde unei întrebări din cele Q întrebări date, vom determina numărul de biţi de 1 al reprezentării binare a valorii de pe linia şi coloana specificată.
Observăm că nu poate fi reţinută matricea sumelor xor, însă acest lucru nu este necesar deoarece pentru a determina valoarea oricărei celule de pe linia i avem nevoie cel mult de linia i-1. Într-o astfel de abordare, soluţia problemei se modifică asftel:
- Se reţin de la început atât plantările cât şi întrebările.
- Pentru fiecare plantare vom reţine separat prima linie şi ultima linie pe care apare, deoarece în rest aceasta nu modifică suma xor a valorilor din celule; se observă că astfel se dublează numărul de plantări.
- Se sortează crescător dupa linie plantările, iar întrebările se sortează crescător după linie şi, în caz de egalitate, după coloană.
- Pe măsură ce determinăm răspunsurile întrebărilor, le reţinem; la final le sortăm după ordinea apariţiei în fişierul de intrare.
Observăm că pentru a calcula sumele xor de pe o linie nu este necesar să reţinem sumele xor de pe linia precedentă, noile plantări aplicându-se peste cele anterioare. Pentru a răspunde la întrebările de pe o linie i, facem suma xor a valorilor de pe linia respectivă doar în cazul în care avem o întrebare.
