#3541
Pixeli
RAU-Gigel este pasionat de grafică, așa că se gândește la un joc cu imagini. El creează într-un editor grafic o imagine bitmap binară de dimensiuni N X N
pixeli. O imagine bitmap binară este o matrice de pixeli, fiecare pixel fiind un bit. Să considerăm că valoarea 0 (nesetat) înseamnă alb și valoarea 1 (setat) înseamnă negru (în realitate este exact invers!). Apoi RAU-Gigel împarte imaginea în patru imagini pătrate egale de latură N / 2
pe care le notează de la 1
la 4
(1
este imaginea din colțul dreapta-sus, 2
este cea din colțul dreapta-jos, 3
stânga-jos și 4
stânga-sus). El repetă procedeul pentru fiecare dintre cele 4
imagini obținute, și tot așa, reducând mereu latura la jumătate și notând direcțiile de la 1
la 4
, până când ajunge la imagini de mărimea unui pixel.
Pentru simplitate, să presupunem că N
este o putere a lui 2
, să spunem K
. Deci, după K
împărțiri succesive de imagini, orice pixel poate fi identificat printr-un șir unic format din cifrele 1
, 2
, 3
și 4
, de lungime K
. Inițial, imaginea este complet albă.
Acum începe jocul. RAU-Gigel se gândește la 2
tipuri de operaţii:
Operaţia 1 x
schimbă starea pixelul identificat cu șirul x
, descris ca mai sus. Dacă pixelul x
nu este setat, îl setează. Dacă pixelul x
este deja setat, atunci îl resetează.
Operaţia 2 x
, unde x
are aceeași semnificație ca mai sus, este o interogare: dacă x
este setat, se răspunde cu 0
. Dacă x
nu este setat, se cere determinarea dimensiunii celei mai mari imagini complet albe, dintre cele create de RAU-Gigel, care conține pixelul x
. Dimensiunea este dată de numărul de pixeli conținut.
Dându-se N
cu semnificația de mai sus și M
, reprezentând numărul de operaţii şi cele M
operaţii de tipul 1
și 2
, să se răspundă la operaţiile de tip 2
.
RAU-Coder 2020
Problema | Pixeli | Operații I/O |
pixeli.in /pixeli.out
|
---|---|---|---|
Limita timp | 0.05 secunde | Limita memorie |
Total: 32 MB
/
Stivă 8 MB
|
Id soluție | #23373890 | Utilizator | |
Fișier | pixeli.cpp | Dimensiune | 3.27 KB |
Data încărcării | 26 Iunie 2020, 22:20 | Scor / rezultat | Eroare de compilare |
pixeli.cpp: In function 'int main()': pixeli.cpp:85:9: warning: unused variable 'g' [-Wunused-variable] int g; ^ pixeli.cpp: At global scope: pixeli.cpp:91:12: error: redefinition of 'std::ifstream in' ifstream in("pixeli.in"); ^ pixeli.cpp:4:10: error: 'std::ifstream in' previously declared here ifstream in("pixeli.in"); ^ pixeli.cpp:92:13: error: redefinition of 'std::ofstream out' ofstream out("pixeli.out"); ^ pixeli.cpp:5:10: error: 'std::ofstream out' previously declared here ofstream out("pixeli.out"); ^ pixeli.cpp:93:5: error: redefinition of 'int n' int n,m,ans,found; ^ pixeli.cpp:6:5: error: 'int n' previously declared here int n,m,ans,found; ^ pixeli.cpp:93:7: error: redefinition of 'int m' int n,m,ans,found; ^ pixeli.cpp:6:7: error: 'int m' previously declared here int n,m,ans,found; ^ pixeli.cpp:93:9: error: redefinition of 'int ans' int n,m,ans,found; ^ pixeli.cpp:6:9: error: 'int ans' previously declared here int n,m,ans,found; ^ pixeli.cpp:93:13: error: redefinition of 'int found' int n,m,ans,found; ^ pixeli.cpp:6:13: error: 'int found' previously declared here int n,m,ans,found; ^ pixeli.cpp:95:8: error: redefinition of 'struct trie' struct trie{ ^ pixeli.cpp:8:8: error: previous definition of 'struct trie' struct trie{ ^ pixeli.cpp:103:7: error: redefinition of 'trie* t' trie *t=new trie; ^ pixeli.cpp:16:7: error: 'trie* t' previously declared here trie *t=new trie; ^ pixeli.cpp: In function 'void gasit(char*, trie*)': pixeli.cpp:104:6: error: redefinition of 'void gasit(char*, trie*)' void gasit(char *c,trie *nod){ ^ pixeli.cpp:17:6: error: 'void gasit(char*, trie*)' previously defined here void gasit(char *c,trie *nod){ ^ pixeli.cpp: In function 'void ins(char*, trie*)': pixeli.cpp:111:6: error: redefinition of 'void ins(char*, trie*)' void ins(char *c,trie *nod){ ^ pixeli.cpp:24:6: error: 'void ins(char*, trie*)' previously defined here void ins(char *c,trie *nod){ ^ pixeli.cpp: In function 'bool del(char*, trie*)': pixeli.cpp:122:6: error: redefinition of 'bool del(char*, trie*)' bool del(char *c,trie *nod){ ^ pixeli.cpp:35:6: error: 'bool del(char*, trie*)' previously defined here bool del(char *c,trie *nod){ ^ pixeli.cpp: In function 'void op2(trie*, char*, int)': pixeli.cpp:133:6: error: redefinition of 'void op2(trie*, char*, int)' void op2(trie *nod,char *c,int cnt){ ^ pixeli.cpp:46:6: error: 'void op2(trie*, char*, int)' previously defined here void op2(trie *nod,char *c,int cnt){ ^ pixeli.cpp: In function 'int main()': pixeli.cpp:148:5: error: redefinition of 'int main()' int main() ^ pixeli.cpp:61:5: error: 'int main()' previously defined here int main() ^ pixeli.cpp:172:9: warning: unused variable 'g' [-Wunused-variable] int g; ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Pixeli face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.