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

Astăzi, la finalul orei de informatică, profesorul a dat ca temă pentru acasă o problemă foarte dificilă, aşa că elevii s-au hotărât să copieze unii de la alţii. Vor trebui totuşi să lucreze cât mai deştept pentru a nu fi prinşi că au copiat.

Astăzi, la finalul orei de informatică, profesorul a dat ca temă pentru acasă o problemă foarte dificilă, aşa că elevii s-au hotărât să copieze unii de la alţii. Vor trebui totuşi să lucreze cât mai deştept pentru a nu fi prinşi că au copiat.

Clasa este alcatuită din $N × M$ elevi, aşezaţi în bănci pe $N$ rânduri şi $M$ coloane. Spunem că doi elevi sunt vecini dacă se află în bănci adiacente fie pe rânduri, fie pe coloane. Tema fiecărui copil constă în găsirea unui număr natural. Pentru ca elevii să nu fie prinşi că au copiat, toate temele acestora vor trebui să fie distincte. Mai mult, elevii sunt foarte leneşi, aşa că îşi vor modifica tema foarte puţin faţă de tema vecinilor. Mai exact, tema oricarui elev diferă prin exact un bit în scrierea în baza $2$ faţă de tema oricărui vecin al său. De exemplu $3$ şi $2$ diferă prin exact un bit, pe când $2$ şi $4$ diferă prin doi biţi.

h2. Restricţii

* $1 ≤ N, M ≤ 2000$

* $1 ≤ N, M ≤ 2000$ Restricţii

* În plus:

table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| 1 | 7 | N=1 |
| 2 | 9 | N şi M sunt puteri de 2 |
| 3 | 14 | N este o putere de 2 |
| 4 | 70 | Nicio restricţie suplimentara |

table(restrictii). |_. # |_. %{font-family: Verdana, sans-serif;} Punctaj% |_. %{font-family: Verdana, sans-serif;} Restricţii % |
| $1$ | $7$ | $N=1$ |
| $2$ | $9$ | $N şi M sunt puteri de 2$ |
| $3$ | $14$ | $N este o putere de 2$ |
| $4$ | $70$ | $Nicio restricţie suplimentara$ |
h3. Punctare
 
Această problemă acceptă şi soluţii parţiale, astfel se va acorda punctaj parţial pentru fiecare test, în
funcţie de cât de aproape de răspunsul optim este soluţia dată folosind următoarea formulă:
 
<tex> S \cdot \max (\left{1 - \sqrt{\dfrac{\frac{G}{O} - 1}{3}}}, \right{0}) </tex>
 
Unde:
 
* $S$ este punctajul testului,
* $G$ este răspunsul dat,
* $O$ este răspunsul optim.
 
*Atenţie!* O soluţie care nu respectă toate cerinţele problemei pentru un anumit test (toate numerele să fie distincte şi oricare două numere adiacente să difere printr-un singur bit) va fi punctata cu 0 pe acel test
 

h2. Exemplu
table(example). |_. xcopy.in |_. xcopy.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3
| 5 4 6
  1 0 2
  9 8 10

|

h3. Explicaţie

h3. Explicaţie
 
În această secţiune, indicele poziţionat in dreapta-jos a numărului reprezintă baza în care este scris. Spre exemplu, opt poate fi scris drept 8{~10~} = 1000 {~2~}
 
Unul dintre răspunsurile optime pentru copii sunt date în urmatorul tabel:
 
table(expli1). | 0101{~2~} = 5{~10~} | 0100{~2~} = 4{~10~} | 0110{~2~} = 6{~10~} |
| 0001{~2~} = 1{~10~} | 0000{~2~} = 0{~10~} | 0010{~2~} = 2{~10~} |
| 1001{~2~} = 9{~10~} | 1000{~2~} = 8{~10~} | 1010{~2~} = 10{~10~} |
 
Putem observa că între oricare două bănci adiacente numerele elevilor din acele bănci diferă cu exact un bit. Valoarea maximă a soluţiei este 10 si este răspunsul optim. Este evident că există şi alte răspunsuri optime – spre exemplu, soluţia propusa dar oglindită vertical sau orizontal.
 
Una dintre soluţiile parţiale posibile în care maximul este 15 este:
 
table(expli2). | 0110{~2~} | 0111{~2~} | 0101{~2~} |
| 1110{~2~} | 1111{~2~} | 1101{~2~} |
| 1010{~2~} | 1011{~2~} | 1001{~2~} |
 
Această soluţie ar fi punctată, conform formulei de punctare, cu $59, 1%$ din punctajul testului.
 

...

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