(toc){width: 25em}*{text-align:center} *Conţinut:*
* 'Problema 1':probleme-de-taietura#problema-1
* 'Problema 2':probleme-de-taietura#problema-2

* 'Problema 3':probleme-de-taietura#problema-3

* 'Problema 3 [["10519 !! Really Strange !!":http://online-judge.uva.es/p/v105/10519.html]]':probleme-de-taietura#problema-3

* 'Problema 4':probleme-de-taietura#problema-4
* 'Problema 5':probleme-de-taietura#problema-5
* 'Problema 6':probleme-de-taietura#problema-6

* 'Problema 7':probleme-de-taietura#problema-7
* 'Problema 8':probleme-de-taietura#problema-8
* 'Problema 9':probleme-de-taietura#problema-9
* 'Problema 10':probleme-de-taietura#problema-10
* 'Problema 11':probleme-de-taietura#problema-11
* 'Problema 12':probleme-de-taietura#problema-12

* 'Problema 7 Bursele Agora 2001':probleme-de-taietura#problema-7
* 'Problema 8 ["10623 Thinking Backward":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1564]':probleme-de-taietura#problema-8
* 'Problema 9 ["Internet Problem Solving Contest 2000":http://plg1.cs.uwaterloo.ca/~acm00/ipsc/]':probleme-de-taietura#problema-9
* 'Problema 10 ["527 The partition of a cake":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=468]':probleme-de-taietura#problema-10
* 'Problema 11 ["10178 Count the faces":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1119]':probleme-de-taietura#problema-11
* 'Problema 12 Algoritmus, Cercuri':probleme-de-taietura#problema-12

* 'Bibliografie':probleme-de-taietura#bibliografie

p=. !probleme-de-taietura?poza-5.bmp!

h2(#problema-3). Problema 3:

h2(#problema-3). Problema 3 [["10519 !! Really Strange !!":http://online-judge.uva.es/p/v105/10519.html]]:

Se dau $n$ cercuri care se intersectează oricare două în două puncte şi nu există trei care se intersectează într-un punct, se cere să se determine numărul de zone în care este împarţit planul de aceste $n$ cercuri. ( $n <= 10^100$ )

[["10519 !! Really Strange !!":http://online-judge.uva.es/p/v105/10519.html]]

h3. Rezolvare:

În această problemă urmăm raţionamentul de până acum. Este evident că trebuie ca fiecare plan să se intersecteze cu fiecare, că oricare trei plane trebuie să nu se intersecteze într-o dreaptă, oricare trei plane nu trebuie să fie paralele cu o dreaptă şi oricare patru plane nu trebuie să se intersecteze într-un punct. Notăm $p(n)$ numărul maxim de zone în care $n$ plane împart spatiul. Când adaugăm un nou plan acesta va fi intersectat de celelalte plane în $n$ drepte, drepte care după restrictiile care le-am pus nu vor fi două paralele sau trei care să se intersecteze într-un punct. Acest plan va fi împărţit în $d(n)$  regiuni de aceste drepte din cauza restricţiilor impuse. Fiecare regiune din plan taie o zonă din spaţiu în două noi zone, de aici tragem concluzia că $p(n + 1) = d(n) + p(n)$ . Astfel avem $p(n) =  n(n-1)/2 + 1 + (n-1)(n-2)/2 + 1 + ...+2 * 1 / 2 + 1 + p(1) = ( n^2^ – n + (n-1)^2^ – (n-1)+... + 2^2^ – 2  +  1 – 1 + (n – 1) )/2+ 2 = ( n(n+1)(2n + 1)/6 – n(n+1)/2 + (n-1))/2 + 2  = (n^3^/3 + n^2^/2 + n/6 – n^2^/2 – n/2 )/2 + n + 1 = n^3^/ 6 + 5n/6 + 1$ . Am folosit identităţile $1 + 2 + … + n = n(n+1)/2 şi 1 + 2^2^ + 3^2^ + … + n^2^ = n(n+1)(2n+1)/6$ care se pot demonstra uşor prin inducţie.
Menţionăm că dacă vrem să împărţim un cub, un cilindru o sfera etc în număr maxim de regiuni folosind $n$ plane, formula se păstrează.

h2(#problema-7). Problema 7:

h2(#problema-7). Problema 7 Bursele Agora 2001:

Dându-se un număr natural $N$ , să se determine numărul maxim de zone în care pot împărţi spaţiul $N$ sfere.

[Bursele Agora 2001[3]]

h3. Rezolvare:
Pornim la fel ca la problema anterioară, oricare două sfere se vor intersecta şi nu vor exista trei sfere care să se intersecteze în acelaşi punct. Vom nota cu $s(n)$ numărul maxim de regiuni în care poate fi împărţit spaţiul cu $n$ sfere. Să vedem ce se întâmplă când adăugăm o sferă. Această sferă va fi intersectată de toate celelalte $n$ sfere în $n$ cercuri, pentru ca numărul de regiuni noi să fie maxim aceste cercuri vor împărţi sfera într-un număr maxim de regiuni, acest număr este $c(n)$ aşa cum am discutat la problema 2. Obţinem astfel $s(n + 1) = c(n) + s(n) = c(n) + c(n-1) + ... + c(1) = n(n-1) + 2 + (n-1)(n-2) + 2 + ... + 2 = 1 + 2^2 + .. + n^2 – 1 – 2 – 3 - .... – n + 2n => s(n) = n(n^2 – 3n + 8) / 3$

h2(#problema-8). Problema 8:

h2(#problema-8). Problema 8 ["10623 Thinking Backward":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1564]:

Se dă un număr $N$ care este numărul maxim în care poate fi împărţit planul de $m$ elipse, $n$ cercuri şi $p$ triunghiuri. Se cere ştiind $N$ să se determine toate valorile posibile pentru $m$ , $n$ şi $p$ . ( $N$ întreg făra semn reprezentabil pe 32 de biţi, $0<=m<100$ , $0<=n<20000$ şi $0<=p<100$ )

[["10623 Thinking Backward":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1564]]

h3. Rezolvare:

Problemele anterioare au fost cam matematice şi ele sunt numite de obicei de olimpici peiorativ ca “probleme de formulă”, majoritatea olimpicilor la informatică participă aici pentru că matematica nu le place aşa tare şi deci nici apariţia unor probleme ca cele de mai sus care sunt mai mult de mate decât de info nu îi prea încântă. Cum poate fi rezolvată o problemă de formulă fără să avem intuiţia matematică sau cunoţinţele matematice necesare? Păi câteodată elevii apelează la următorul truc: află primele câteva valori de mâna sau cu ajutorul unor algoritmi brute force şi apoi speră ca formula să fie de o anumită formă, de exemplu ar putea fi un polinom de un grad mic. Atunci avem ca $f(N) = An^3 + Bn^2 + Cn + D$ . Afland primele câteva valori vom ştii valorile $f(1), f(2), f(3), f(4)$ . Dând lui $n$ pe rand valorile 1, 2, 3 şi 4 putem face un sistem cu necunoscutele A, B, C şi D. Sau putem încerca să vedem cum se comportă şirul de numere, are o creştere polinomială sau exponenţială, apar valorile lui în triunghiul lui Pascal. Iar dacă rezolvăm problemele de acasă putem căuta valorile din şirul de soluţii pe internet pe pagina Eciclopedia Online a şirurilor de întregi [7] care este o resursă foarte utilă în cazul problemelor de acest gen .

h2(#problema-9). Problema 9:

h2(#problema-9). Problema 9 ["Internet Problem Solving Contest 2000":http://plg1.cs.uwaterloo.ca/~acm00/ipsc/]:

Se dau $N$ drepte în plan, fiecare dreaptă este dată prin două puncte prin care trece. Se cere să se determine pentru această configuraţie în câte zone este împărţit planul. ( $n <= 1000$ )

[["Internet Problem Solving Contest 2000":http://plg1.cs.uwaterloo.ca/~acm00/ipsc/]]

h3. Rezolvare:
În sfârşit o problemă în care avem nevoie să folosim calculatorul şi talentul nostru de programatori . Vom folosi aceeaşi idee ce a apărut şi în celelalte probleme, adică numărăm pe rând în câte zone este împărţit planul de primele o dreaptă, doua drepte respectiv $n$ drepte. Deci vom adăuga în ordine dreptele la configuraţia noastră. Când adăugăm o dreaptă ea va fi intersectată de dreptele deja adăugate în $k$ puncte nu neapărat distincte, pe noi ne intereseaza punctele distincte, ca să facem acest lucru putem sorta punctele în $O(k log k)$ sau să folosim o tabelă de dispersie şi astfel să aflăm în $O(k)$ numărul de puncte distincte, daca acest număr e egal cu $L$ atunci la numărul curent de zone vom adăuga $L$ . Astfel algoritmul are complexitatea $O(n^2 log n)$ , sau dacă folosim tabele de dispersie $O(n^2)$ .

h2(#problema-10). Problema 10:

h2(#problema-10). Problema 10 ["527 The partition of a cake":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=468]:

p=. !probleme-de-taietura?poza-10.bmp!
Avem un tort în formă de pătrat de dimensiune $1000 x 1000$ . Folosim un cuţit pentru a tăoa tortul. Întrebarea este după o serie de tăieturi, în căte bucăţi am patriţionat tortul. Restricţii: Numărul de tăieturi nu va fi mai mare de $8$ . După tăieturi, lungimea oricărei laturi a partiţiei nu va fi mai mică decât unu. Coordonatele vârfurilor tortului vor fi $(0,0)(0,1000)(1000,1000) (1000,0)$ . Tăieturile se vor intersecta în două puncte cu marginile tortului. Următoarea imagine e un tort tăiat în zece bucăţi.

[["527 The partition of a cake":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=468]]

h3. Rezolvarea:
Este analoaga cu cea a problemei anterioare, datele sunt foarte mici în problema aceasta, probabil că autorii au vrut să facă problema accesibilă şi altor idei care folosesc împărţiri efective în poligoane a pătratului.

h2(#problema-11). Problema 11:

h2(#problema-11). Problema 11 ["10178 Count the faces":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1119]:

p=. !probleme-de-taietura?poza-12.bmp!
Se dă un graf planar prin noduri şi muchii, un graf este planar dacă există o modalitate de a îl desena în plan făra ca muchiile să se intersecteze decăt la capete. Se cere să se determine în căte regiuni împarte planul graful dat la intrare. Mai jos avem un exemplu de graf în care feţele sunt numerotate.

[["10178 Count the faces":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1119]]

h3. Rezolvare:
Este interesant faptul că în această problemă nu ne este dată configuraţia în plan a grafului ci doar structura lui. Un graf il putem reprezenta în mai multe moduri în plan, astfel suntem duşi înspre ideea că există ceva formulă care rezolvă problema. O formulă întradevăr există şi se numeşte formula lui Euler pentru grafurile planare. Formula arată aşa $f - m + n  = 2$ , unde prin $f$ am notat numărul de feţe, $m$ numărul de muchii şi $n$ numărul de vârfuri, dacă graful nostru e conex (formula include faţa exterioară). Această formulă poate fi demonstrată în foarte multe moduri. Dacă vreţi să vedeţi 19 metode de demonstrare puteţi să vizitaţi adresa [8]. O demonstraţie simplă ar fi prin inducţie pornind de la un arbore şi adăugând pe rând câte o muchie. La început avem o singură faţă, cea infinită, $1 – (n – 1) + n = 2$ se verifică. Fiecare muchie adăugată împarte o faţă în două deci dacă aveam inainte $f – m + n = 2$ acum vom avea $f1 – m1 + n = 2$ unde $f1 = f + 1$ şi $m1 = m + 1$ . Deci am demonstrate formula şi putem foarte uşor să rezolvăm problema, mai trebuie numai să avem grijă ca pentru fiecare componentă conexă număram faţa infinită.
Această formulă este adevarată şi în spaţiu pentru poliedre.

h2(#problema-12). Problema 12:

h2(#problema-12). Problema 12 Algoritmus, Cercuri:

p=. !probleme-de-taietura?poza-13.bmp!

165 115 65
CERCURI.OUT
$11$

[Algoritmus, Cercuri]

h3. Rezolvare: