# PBinfo #3442 – SpiralMatrix – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Parcurgând elementele unei matrice pătratice de dimensiune n în spirală, pornind din colțul din stânga-sus, în sens orar, de la margini către interior, se obține șirul strict crescător format din toate valorile de la 1 la n2, ca în figura de mai jos. Din șirul dat se obțin două subșiruri disjuncte, de lungime egală, cu număr maxim de termeni. Primul subșir este format din numere consecutive din prima jumătate a șirului, și trebuie să conțină în mod obligatoriu valoarea 1, iar al doilea este format din numere consecutive din a doua jumătate a șirului și trebuie să conțină în mod obligatoriu valoarea n2.



 1 
 2 
 3 
 4 
 5 


 16 
 17 
 18 
 19 
 6 


 15 
 24 
 25 
 20 
 7 


 14 
 23 
 22 
 21 
 8 


 13 
 12 
 11 
 10 
 9 


table.spirala{border-collapse:collapse; border:solid 1px gray;}table.spirala td{border:solid 1px gray; padding:3px 6px; text-align:center;}
Cerința
Să se afle poziția în matrice a celui mai mare termen din primul subșir și a celui mai mic termen din al doilea subșir.

Date de intrare
Fișierul de intrare spiralmatrix.in conține pe prima linie numărul n.

Date de ieșire
Fișierul de ieșire spiralmatrix.out va conține:


pe prima linie două numere, separate printr-un spațiu, reprezentând mai întâi linia și apoi coloana pe care se află în matrice cel mai mare termen al primului subșir;
pe a doua linie alte două numere, separate printr-un spațiu, reprezentând mai întâi linia și apoi coloana pe care se află în matrice cel mai mic termen al celui de al doilea subșir.

Restricții și precizări

1 < n < 1.000.000.000;
Pentru teste în valoare de 45 de puncte n este impar;
Pentru teste în valoare de 45 de puncte n < 1000;
Pentru teste în valoare de 75 de puncte n < 1.000.000;
Liniile sunt numerotate de sus în jos începând cu 1, iar coloanele sunt numerotate de la stânga la dreapta începând cu 1;
Punctajul pe un test se obține doar dacă sunt corecte toate cele patru valori.
În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1
spiralmatrix.in

5
spiralmatrix.out

5 2
4 1
Explicație
Primul subșir este format din valorile de la 1 la 12. Valoarea 12 se găsește pe linia 5 și coloana 2. Al doilea subșir este format din valorile de la 14 la 25. Valoarea 14 se găsește pe linia 4 și coloana 1.

Exemplul 2
spiralmatrix.in

4
spiralmatrix.out

4 3
4 2
Explicație
Primul subșir este format din valorile de la 1 la 8. Valoarea 8 se găsește pe linia 4 și coloana 3. Al doilea subșir este format din valorile de la 9 la 16. Valoarea 9 se găsește pe linia 4 și coloana 2.

## Cod sursă C++

```cpp
#include <fstream>
#include <cmath>
using namespace std;
ifstream in("spiralmatrix.in");
ofstream out("spiralmatrix.out");
int l0=1,l1=1,l2=1,c0=1,c1=1,c2=1;
int main(){
    long long n,nc=0;
    int l=1,c=0,dl=0,dc=1;
    in>>n;
    long long p2=n/sqrt(2);
    if(p2*p2==n*n/2)p2--;
    nc=n*n/2-p2*p2;
    if(n%2==0){
        if(p2%2==0){
            dl=1;dc=0;
            l=c=n/2-p2/2+1;c--;
            if(nc<=p2+1){l+=nc-1;}
            else{l+=p2;c+=nc-p2-1;}
        }
        else{l=c=n/2+1+p2/2;
            dl=-1;dc=0;
            if(nc<=p2+1){l-=nc-1;}
            else{   l=n-l+1;
                    c-=nc-p2-1;
                    dl=0;dc=-1;}}}
    else{
        if(p2%2==0){
            dl=-1;dc=0;
            l=c=n/2+1+p2/2;
            if(nc<=p2+1){l+=dl*(nc-1);}
            else{   dl=0;dc=-1;
                    l-=p2;c-=nc-p2-1;}
        }
        else{l=c=n/2-p2/2+1;c--;
            dl=1;dc=0;
            if(nc<=p2+1){l+=nc-1;}
            else{   l+=p2;
                    c+=nc-p2-1;
                    dl=0;dc=1;}}}
    if(n%2==0){l1=l;c1=c;}
    else{l2=l;c2=c;
        if(l2+dl<=(n-p2)/2 || n-(n-p2)/2+1<l2+dl || c2+dc<(n-p2)/2 || n-(n-p2)/2+1<c2+dc){
            if(dl==-1 && dc==0){dl=0;dc=-1;}
            else{if(dl==0 && dc==-1){dl=1;dc=0;}
                 else{ if(dl==1 && dc==0){dl=0;dc=1;}
                       else{if(dl==0 && dc==1){dl=-1;dc=0;}}}}}
         l1=l2+dl;c1=c2+dc;}
    if(l1+dl<=(n-p2)/2 || n-(n-p2)/2+1<l1+dl || c1+dc<(n-p2)/2 || n-(n-p2)/2+1<c1+dc){
        if(dl==-1 && dc==0){dl=0;dc=-1;}
        else{if(dl==0 && dc==-1){dl=1;dc=0;}
             else{ if(dl==1 && dc==0){dl=0;dc=1;}
                   else{if(dl==0 && dc==1){dl=-1;dc=0;}}}}}
    l0=l1+dl;c0=c1+dc;
    out <<  l0 <<  << c0 << endl;
    if(n%2==0)out <<  l1 <<  << c1 << endl;
    else out <<  l2 <<  << c2 << endl;
    return 0;}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3442)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3442/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3442/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)