Se consideră un tablou cu N
linii şi N
coloane (numerotate de la 1
la N
) care conţine valoarea 1
în fiecare dintre cele NxN
celule. Valorile din tablou pot fi modificate prin aplicarea a două operații codificate astfel:
L nr
, prin care se schimbă simultan toate semnele numerelor din linia cu numărulnr
.C nr
, prin care se schimbă simultan toate semnele numerelor din coloana cu numărulnr
.
Cerințe
1) Dându-se o succesiune de K
operații (L nr
sau C nr
) asupra liniilor/coloanelor tabloului inițial (în care toate celulele conțin valoarea 1
) să se determine numărul valorilor pozitive din tablou la finalul executării celor K
operații.
2) Să se determine numărul minim de operații L nr
sau C nr
, care, aplicate tabloului inițial, îl modifică astfel încât tabloul obținut să conțină exact Z
valori negative.
Date de intrare
Fișierul de intrare tablou.in
conține pe prima linie numărul p=1
sau p=2
, reprezentând numărul cerinței ce trebuie rezolvată.
- Dacă
p=1
atunci linia a doua a fișierului de intrare conține numereleN
șiK
, separate printr-un spațiu, iar următoareleK
linii conțin fiecare câte o literă mare (L
sauC
) și un numărnr
, separate printr-un spațiu, reprezentând codificarea uneia dintre cele două operații (L nr
sauC nr
). - Dacă
p=2
atunci linia a doua a fișierului de intrare conține numereleN
șiZ
, separate printr-un spațiu.
Date de ieșire
- Dacă
p=1
, atunci fișierul de ieșiretablou.out
conține pe prima linie un număr natural, reprezentând numărul valorilor pozitive din tabloul obținut la finalul executării celorK
operații asupra tabloului inițial (răspunsul la cerința 1). - Dacă
p=2
, atunci fișierul de ieșiretablou.out
conține pe prima linie un număr natural reprezentând numărul minim de operațiiL nr
sauC nr
, care, aplicate tabloului inițial, îl modifică astfel încât tabloul obținut să conțină exactZ
valori negative (răspunsul la cerința 2). Dacă prin aplicarea de operațiiL nr
sauC nr
tabloului inițial nu se poate obține un tablou cuZ
valori negative, atunci, fișierul va conține pe prima linie valoarea0
(zero).
Restricții și precizări
N
,K
,Z
șinr
sunt numere naturale3 ≤ N ≤ 20000
;1 ≤ K ≤ 43000
;1 ≤ Z ≤ N*N
;1 ≤ nr ≤ N
- Prin schimbare de semn, valoarea
-1
se transformă în1
și valoarea1
se transformă în-1
- În concurs s-au acordat 10 puncte din oficiu și câte 45 puncte pentru rezolvarea corectă a fiecărei cerințe. Pe site se acordă 10 puncte pentru rezolvarea corectă a exemplelor.
Exemplul 1
tablou.in
1 4 4 L 1 L 3 C 1 L 1
tablou.out
10
Explicație
N=4
. La finalul aplicării succesiunii de K=4
operații, tablou modificat are conținutul:
-1 1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1
Astfel, tabloul conține 10
valori pozitive.
Exemplul 2
tablou.in
2 3 5
tablou.out
3
Explicație
Sunt necesare minimum 3
operații, de exemplu: L 3
, L 1
, C 1
Exemplul 3
tablou.in
2 4 7
tablou.out
0
Explicație
Nu există nicio succesiune de operații pentru care să se obțină Z=7
valori negative.
Autor prof. Carmen Mincă
Colegiul Național de Informatică Tudor Vianu – București
Presupunem că s-a aplicat de xi ori operația L i și deyk ori operația C k.
Valoarea memorată în celula situată în liniai și coloanak își va schimba semnul dexi+yk ori.
Astfel, ea va fi negativă dacă suma xi+yk este impară.
Deducem că numărul de valori negative din tabloul modificat va depinde de paritățile numerelor xi și yk. Dacă șirul valorilorx1,x2,x3,..,xN conține x valori impare iar șirul valorilor y1,y2,y3,..,yN conține y valori impare atunci tabloul modificat va conține x*(N-y)+y*(N-x) valori negative.
Astfel răspunsul la cerința 1) este valoarea expresiei N2 – x*(N-y) + y*(N-x)
Pentru cerința 2), vom folosi relația x*(N-y)+y*(N-x)=Z.
Căutăm prima valoare a lui x din mulțimea {0,1,2,…,N} pentru care există un y din {0,1,2,..,N} și cu proprietatea că y= . și N≠2*x Dacă există aceste valori x și y, atunci numărul minim de operații este M=x+y
#include <fstream> #include <cmath> #include <bitset> using namespace std; ifstream fin("tablou.in"); ofstream fout("tablou.out"); bitset <20005> L,C; char x; int i,y,n,v,k,l,c,s,p; void solve1() { for(i=1;i<=k;++i) { fin>>x>>y; if(x=='L') L[y]=L[y]^1; else C[y]=C[y]^1; } l=L.count(); c=C.count(); fout<<n*n-l*(n-c)-c*(n-l); } void solve2() { if(k>n*n) {fout<<0; return;} for(s=k/n;s<=n;++s) if((n*s-k)%2==0) {p=(n*s-k)/2; y=sqrt(s*s-4*p); if(y*y==s*s-4*p){fout<<s;return;} } fout<<0; } int main() { fin>>v>>n>>k; if(v==1) solve1(); else solve2(); fin.close();fout.close(); return 0; }
#include <fstream> using namespace std; #define Nmax 20005 ifstream fin("tablou.in"); ofstream fout("tablou.out"); int N,Z,K,M,P; char linie[Nmax]; char coloana[Nmax]; void cerinta1() { fin>>N>>K; char LC; int nr_val_pozitive,nr_val_negative,nr; int i, linimpar=0, colimpar=0; for(i=1; i<=K; i++) { fin>>LC>>nr; if(LC=='L') linie[nr]=(linie[nr]+1)%2; else coloana[nr]=(coloana[nr]+1)%2; } for(i=1; i<=N; i++) { linimpar+=linie[i]; colimpar+=coloana[i]; } nr_val_negative=linimpar*(N-colimpar)+(N-linimpar)*colimpar; nr_val_pozitive=N*N - nr_val_negative; fout<<nr_val_pozitive<<endl; } void cerinta2() { fin>>N>>Z; int M,linimpar, colimpar,ok=0, i; if(Z>N*N)ok=0; else if(Z==N*N) { linimpar=N; colimpar=0; ok=1; } else if(2*Z==N*N) { ok=1; linimpar=N/2; colimpar=0; } else for(linimpar=0; (linimpar<=N) && (ok==0); linimpar++) { if(N-2*linimpar!=0 && (Z-N*linimpar)%(N-2*linimpar)==0) { colimpar=(Z-N*linimpar)/(N-2*linimpar); if(colimpar>=0 && colimpar<=N) { ok=1; break; } } } if(ok==0)fout<<0<<endl; else fout<<linimpar+colimpar<<endl; } int main() { fin>>P; if(P==1) cerinta1(); else cerinta2(); return 0; }