Diferente pentru problema/pinex intre reviziile #15 si #34

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="pinex") ==

A gamă foarte largă de probleme în cadrul concursurilor de informatică şi nu numai se rezolvă folosind principiul includerii şi excluderii. Deşi 'teoria':http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle poate părea greu de înţeles, mă voi strădui să ofer o explicaţie cât mai clară pentru cei interesaţi.

O gamă foarte largă de probleme în cadrul concursurilor de informatică, şi nu numai, se rezolvă folosind _principiul includerii şi excluderii_. Teoria poate părea greu de înţeles, aşa că vom încerca să oferim o explicaţie cât mai clară pentru cei interesaţi.

Principiul enunţă faptul că fiind date $N$ multimi finite $A{~1~},A{~2~},A{~3~}...A{~n~}$, relaţia de mai jos este adevărată.

Principiul enunţă faptul că fiind date $n$ mulţimi finite $A{~1~},A{~2~},A{~3~}...A{~n~}$, relaţia de mai jos este adevărată...

<tex> \displaystyle | \bigcup_{i=1}^{n} A_{i} | =  \sum_{i=1}^{n} | A_{i} | - \sum_{i,j:1 \le i < j \le n} |A_{i} \cap A_{j} | + \sum_{i,j,k:1 \le i < j < k \le n} |A_{i} \cap A_{j} \cap A_{k}| - \ldots + (-1)^{n-1} |A_{1} \cap \ldots \cap A_{n}| </tex>
!>problema/pinex?Inclusion-exclusion.png 50%!

Pentru demonstraţie, vom pleca de la cazul banal când avem doar două mulţimi, fie acestea $A$ şi $B$. Dacă sunt disjuncte, este clar că reuniunea lor se calculează după relaţia <tex>|A \cup B|=|A|+|B|</tex>. Ne rămâne de rezolvat cazul când $A$ şi $B$ au cel puţin un element în comun. Relaţia anterioară numără elementele comune din cadrul reuniunii de două ori(o dată pentru $A$ şi o dată pentru $B$), de aici apare nevoia să scădem numărul acestora din rezultat. Acest lucru este uşor de făcut, dat fiind faptul că pentru $A$ şi $B$, numărul de elemente comune celor doua mulţimi este <tex>|A \cap B|</tex>. Rezultă <tex>|A \cup B|=|A|+|B|-|A \cap B|</tex>.

Pentru demonstraţie, vom pleca de la cazul banal când avem doar două mulţimi; fie acestea $A$ şi $B$. Dacă sunt disjuncte, este clar că reuniunea lor se calculează după relaţia <tex>|A \cup B|=|A|+|B|</tex>. Rămâne de rezolvat cazul când $A$ şi $B$ au cel puţin un element în comun. Relaţia anterioară numără elementele comune din cadrul reuniunii de două ori (o dată pentru $A$ şi o dată pentru $B$), de unde apare nevoia să scădem numărul acestora din rezultat. Acest lucru este uşor de făcut, dat fiind faptul că pentru $A$ şi $B$, numărul de elemente comune celor doua mulţimi este <tex>|A \cap B|</tex>. Rezultă <tex>|A \cup B|=|A|+|B|-|A \cap B|</tex>.

În diagrama din dreapta este reprezentat cazul cu trei muţimi $A$, $B$ şi $C$. Relaţia de mai sus se extinde la <tex> |A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|B \cap C|-|C \cap A|+|A \cap B \cap C| </tex>.

Pentru cazul general, având $N$ mulţimi $A{~1~},A{~2~},A{~3~}...A{~n~}$, vom presupune că există un element $x$ din
<tex> \displaystyle \bigcup_{i=1}^{n} A_{i} </tex> comun pentru exact $k$ multimi, fie acestea $A{~i1~},A{~i2~},A{~i3~}...A{~ik~}$. Vom considera cardinalele mulţimilor doar faţă de acest număr $x$ (cu alte cuvinte, ignormăm celelalte elemente). Dacă vom face intersecţia a mai mult de $k$ mulţimi, sau a unor mulţimi cu indicele de ordine diferit de $i1,i2...ik$, această intersecţie va fi evident vidă. Numărul de intersecţii a două mulţimi din cele $k$ este $C(k,2)$, numărul de intersecţii a trei mulţimi este $C(k,3)$, etc. Cum am spus ca vom urmări doar elementul $x$, avem relaţia <tex> \displaystyle \bigcup_{i=1}^{k} A_{i}=C(n,1)-C(n,2)+C(n,3)+...+(-1)^{k-1} C(n,n)=1</tex> Rezultă relaţia de demonstrat este adevărată.

Pentru cazul general, având $n$ mulţimi $A{~1~},A{~2~},A{~3~}...A{~n~}$, vom presupune că există un element $x$ din
<tex> \displaystyle \bigcup_{i=1}^{n} A_{i} </tex> comun pentru exact $k$ multimi. Fie acestea $A{~i{~1~}~}$, $A{~i{~2~}~}$, $A{~i{~3~}~}$ ... $A{~i{~k~}~}$. Vom considera cardinalele mulţimilor doar faţă de acest număr $x$ (cu alte cuvinte, ignorăm celelalte elemente). Dacă vom face intersecţia a mai mult de $k$ mulţimi, sau a unor mulţimi cu indicele de ordine diferit de $i{~1~}$, $i{~2~}$ ... $i{~k~}$, această intersecţie va fi evident vidă. Numărul de intersecţii a două mulţimi din cele $k$ este <tex> \dbinom{k}{2} </tex>, numărul de intersecţii a trei mulţimi este <tex> \dbinom{k}{3} </tex>, etc. Cum urmărim doar elementul $x$, avem relaţia <tex> \displaystyle |\bigcup_{j=1}^{k} A_{i_{j}}|=\binom{k}{1}-\binom{k}{2}+\binom{k}{3}-...+(-1)^{k-1} \binom{k}{k}=1</tex>. Rezultă că relaţia de demonstrat este adevărată.

Pentru o demonstratie mai riguroasă puteţi citi de pe 'wikipedia':http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle sau de pe 'cut-the-knot':http://www.cut-the-knot.org/arithmetic/combinatorics/InclusionExclusion.shtml.

h3. Aplicaţie

h3. Aplicaţie la teoria prezentă mai sus

Răspundeţi la $M$ întrebări de tipul: „ dându-se două numere naturale $A$ şi $B$, să se determine numărul de numere naturale mai mici sau egale cu $A$ şi prime cu {$B$} ”. Două numere naturale $x$, $y$ sunt prime între ele dacă ${'cmmdc':problema/euclid2}(x, y) = 1$.

Răspundeţi la $M$ întrebări de tipul: „dându-se două numere naturale $A$ şi $B$, să se determine numărul de numere mai mici ca $A$ şi prime cu $B$ ”. Două numere naturale $(x,y)$ sunt prime între daca $cmmdc(x,y)=1$.

h3. Notaţii

h3. Care-i legătura?
 
*Marius* Zici ce reprezintă mulţimea Ai şi ce reprezintă astfel mulţimea reuniuii lor.

În loc să calculăm în mod direct numărul de numere mai mici ca $A$ şi prime cu $B$, va fi mai uşor să calculăm numărul de numere mai mici ca $A$ şi **neprime** cu $B$, după care să scădem acest rezultat din $A$. Astfel, vom lua în considerare divizorii primi ai lui $B$; fie aceştia $d{~1~}$, $d{~2~}$ ... $d{~k~}$. Este evident că orice număr natural $x$ pentru care $cmmdc(x, B) &ne; 1$ va fi divizibil cu unul din numerele $d{~1~}$, $d{~2~}$ ... $d{~k~}$. De aici rezultă că vom avea $k$ mulţimi formate din numerele naturale mai mici ca $A$ şi prime cu câte unul din divizorii primi ai lui $B$. Valoarea căutată este reprezentată de cardinalul reuniunii lor. Calcularea acestui cardinal implică principiul includerii şi exlcuderii.

h2. Date de intrare

Fişierul de intrare $pinex.in$ va conţine pe prima linie numărul $M$, reprezentând numărul de query-uri. Următoarele $M$ linii vor conţine câte două numere $A$ si $B$, cu semnificaţia din enunţ.

Fişierul de intrare $pinex.in$ va conţine pe prima linie numărul $M$, reprezentând numărul de întrebări. Următoarele $M$ linii vor conţine câte două numere $A$ şi $B$ cu semnificaţia din enunţ.

h2. Date de ieşire

h2. Restricţii

* $1 &le; M &le; 500$
* $1 &le; A &le; 10^18^$
* $1 &le; B &le; 10^12^$
* Pentru $30%$ din teste $M &le; 100, A,B &le; 1 000$
* Pentru $70%$ din teste $A,B &le; 10^9^$

* $1 &le; M &le; 500$.
* $1 &le; A &le; 10^18^$.
* $1 &le; B &le; 10^12^$.
* Pentru $30%$ din teste $M &le; 100$ şi $A, B &le; 1 000$.
* Pentru $70%$ din teste $A, B &le; 10^9^$.

h2. Exemplu

h2. Indicaţii de rezolvare

*Marius* Aici zici pe larg despre soluţie şi dai un exemplu aî să ai 3 mulţimi, faci trimitere la diagramă şi analizezi cum ajungi la rezultat. După care intră textul cu modalităţi de implementare. ;) Bagă Winie!

Demonstraţii mai riguroase a acestui principiu puteţi citi pe 'wikipedia':http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle sau pe 'cut-the-knot':http://www.cut-the-knot.org/arithmetic/combinatorics/InclusionExclusion.shtml.
 
În rezolvarea aplicaţiei, vom calcula numărul de numere mai mici ca $A$ neprime cu $B$. Fie $d{~1~}$, $d{~2~}$ ... $d{~k~}$ divizorii primi ai lui $B$. Fiecare astfel de divizor va determina o mulţime de numere <tex> A_{i} = \{ x \mid x \vdots d_{i}, x \le A \} </tex>. Astfel, soluţia va fi <tex> A - | A_{1} \cup A_{2} \cup A_{3} \ldots \cup A_{k} | </tex>. Ştiind cardinalul fiecărei configuraţii de intersecţie între cele $k$ mulţimi, vom putea folosi principiul includerii şi excluderii pentru calcularea numărului căutat.
 
Să exemplificăm pentru $A = 50$ şi $B = 30$. Divizorii primi ai lui $B$ sunt $2$, $3$ şi $5$. Rezultă mulţimile <tex> A_{1}=\{2,4,6...50\}, A_{2}=\{3,6,9...48\} </tex> şi <tex> A_{3}=\{5,10,15...50\} </tex>. Tabelul de mai jos ilustrează toate cele $7$ mulţimi care vor apărea în operaţiile efectuate de noi, precum şi elementele conţinute de acestea.
 
Numărul de numere mai mici ca $A$ şi divizibile cu $x$ va fi $[A/x]$ (parte întreagă din $A$ împărţit la $x$). De asemenea, dacă avem două mulţimi $A{~i~}$ şi $A{~j~}$, $i, j &le; k$, atunci <tex> |A_{i} \cap A_{j}| = [A / (D_{i} * D_{j})] </tex>. Acestă relaţie se extinde natural la $n$ mulţimi.
 
Astfel, pentru exemplul $A = 50$ şi $B = 30$, avem relaţia...
 
<tex> |A_{1} \cup A_{2} \cup A_{3}|=|A_{1}|+|A_{2}|+|A_{3}|-|A_{1} \cap A_{2}|-|A_{2} \cap A_{3}|-|A_{3} \cap A_{1}|+|A_{1} \cap A_{2} \cap A_{3}| = </tex>
<tex> = [50/2] + [50/3] + [50/5]  - [50/6] - [50/15] - [50/10] + [50/30] = </tex>
<tex> = 25 + 16 + 10 - 8 - 3 - 5 + 1 = 36 </tex>
 
Soluţia în acest caz va fi <tex> 50 - 36 = 14 </tex>, cele $14$ numere fiind <tex> \{ 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49 \} </tex>
 
table{width: 900px; text-align: center}. | | <tex> A </tex> | <tex> B </tex> | <tex> C </tex>| <tex> A \cap B </tex> | <tex> A \cap C </tex> | <tex> B \cap C </tex> | <tex> A \cap B \cap C </tex> |
| <tex> 1 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 2 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 3 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 4 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 5 </tex> | 0 | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 |
| <tex> 6 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 7 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 8 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 9 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 10 </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 |
| <tex> 11 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 12 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 13 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 14 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 15 </tex> | 0 | <tex> \star </tex> | <tex> \star </tex> | 0 | 0 | <tex> \star </tex> | 0 |
| <tex> 16 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 17 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 18 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 19 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 20 </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 |
| <tex> 21 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 22 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 23 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 24 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 25 </tex> | 0 | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 |
| <tex> 26 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 27 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 28 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 29 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 30 </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> |
| <tex> 31 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 32 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 33 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 34 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 35 </tex> | 0 | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 |
| <tex> 36 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 37 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 38 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 39 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 40 </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 |
| <tex> 41 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 42 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 43 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 44 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 45 </tex> | 0 | <tex> \star </tex> | <tex> \star </tex> | 0 | 0 | <tex> \star </tex> | 0 |
| <tex> 46 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 47 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 48 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 49 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 50 </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 |
 
h3. Detalii de implementare
 
'Soluţia de $30$ puncte':job_detail/372817?action=view-source presupune parcurgerea numerelor mai mici ca $A$ la fiecare întrebare, verificându-se primalitatea lor cu $B$.
 
Pentru '$70$ puncte':job_detail/372842?action=view-source trebuie aplicat principiul includerii şi excluderii descris mai sus.
 
Optimizarea ce permite obţinerea punctajului maxim presupune precalcularea tuturor numerelor prime mai mici ca $10^6^$. Astfel, atunci când determinăm divizorii primi ai lui $B$ vom itera doar prin numere prime. Complexitatea acestei 'soluţii':job_detail/379646?action=view-source este <tex> O(M*\sqrt{B}*2^X*X) </tex>, unde prin $X$ ne referim la numărul divizorilor primi ai lui $B$.

h2. Aplicaţii

'Reuniune':problema/reuniune
'Suman':problema/suman
'Mins':problema/mins
'Pairs':problema/pairs
"Coin Changing Again":http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2226, uva
"Prime Frog":http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2291, uva
'Jap':problema/jap
'Secventa farey':problema/farey
'Cowfood':problema/cowfood
'Rifleman':http://acm.sgu.ru/problem.php?contest=0&problem=370 sgu
"Sweets":http://www.oi.edu.pl/ceoi2004/problems/swe.pdf, CEOI 2004

* 'Frac':problema/frac
* 'Reuniune':problema/reuniune
* 'Suman':problema/suman
* 'Mins':problema/mins
* 'Pairs':problema/pairs
* 'Jap':problema/jap
* 'Gol3d':problema/gol3d
* 'Secventa farey':problema/farey
* 'Cowfood':problema/cowfood
* 'Borg':http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=741, _ONI 2006_
* 'Coin Changing Again':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2226, _UVA_
* 'Prime Frog':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2291, _UVA_
* 'Rifleman':http://acm.sgu.ru/problem.php?contest=0&problem=370 _SGU_
* 'Sweets':http://www.oi.edu.pl/ceoi2004/problems/swe.pdf, _CEOI, 2004_

== include(page="template/taskfooter" task_id="pinex") ==

infoarena informatica de performanta

Diferente pentru problema/pinex intre reviziile #15 si #34

Nu exista diferente intre titluri.

Diferente intre continut:

Nu exista diferente intre securitate.

Diferente intre topic forum: