Rezolvare PBinfo #3442

Decorative Icon Problema: SpiralMatrix / 3442

Decorative IconAutor: Deivid

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
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.

Andrei Frîntu
Andrei Frîntu

Fondatorul platformei - mentor Academia

LinkedIn Instagram GitHub
© Copyright 2024 - CodulLuiAndrei.ro - Toate drepturile sunt rezervate