Rezolvare completă PbInfo #740 Horse

Se consideră o tablă de şah cu n linii şi n coloane, şi n=4k+1. Liniile acestei table sunt numerotate de sus în jos începând cu linia 1, iar coloanele sunt numerotate de la stânga la dreapta începând cu 1. În fiecare dintre câmpurile acestei table se scrie câte un număr natural din mulţimea {1, 2, …, n2} după următoarele reguli:

a) se porneşte din colţul aflat în poziţia stânga sus al tablei şi se avansează utilizând săritura calului
b) se merge orizontal către dreapta şi în continuare, pe chenarul format din primele două linii, primele două coloane, ultimele două linii şi ultimele două coloane, în sensul acelor de ceasornic;
c) se efectuează mai multe tururi ale tablei, până ce se umple întregul chenar, fără să se sară de două ori în aceeaşi căsuţă, fără să se sară în afara acestui chenar şi fără să rămână vreun câmp liber;
d) din poziţia finală în care s-a ajuns, trebuie să fie posibilă săritura în colţul din stânga sus al pătratului rămas neacoperit;
e) se continuă deplasarea în interiorul pătratului rămas neacoperit, folosind regulile a), b), c), d) până ce se ajunge la pătratul interior de latură 1 care va conţine valoarea n2.

Amintim că o săritură a calului constă într-o deplasare de două căsuţe pe orizontală urmată de o deplasare de o căsuţă pe verticală sau într-o deplasare de două căsuţe pe verticală urmată de o deplasare de o căsuţă pe orizontală. Calul din figura următoare poate ajunge printr-o săritură în oricare dintre cele 8 poziţii haşurate:

De exemplu, pentru n=5, după un tur al tablei, se obţine următoarea acoperire parţială:

Iar după al doilea tur, se obţine acoperirea parţială:

Pentru n=9, acoperirea se realizează ca mai jos. Se observă mai întâi umplerea completă, apoi umplerile parțiale.


Cerința

Cunoscând valoarea lui n ce reprezintă dimensiunea tablei şi un număr p, să se determine linia şi coloana căsuţei din tabelă unde este scris numărul p, după regulile de mai sus.

Date de intrare

Fişierul horse.in conţine două numere:

  • n – numărul liniilor şi coloanelor tablei, pe prima linie
  • p – numărul dintr-o căsuţă a tablei, pe a doua linie

Date de ieșire

Fişierul horse.out va conţine două numere: linia şi respectiv coloana căsuţei unde este scris numărul p, cu un spaţiu între ele.

Restricții și precizări

  • 4<n<46340
  • n=4k+1
  • 1≤p≤n2
  • pentru 50% dintre teste n≤1000

Exemplu

horse.in

5
24

horse.out

2 1

Explicație

Pe o tablă 5x5 numărul 24 va ajunge pe linia 2 şi coloana 1.


Exemplu

horse.in

9
36

horse.out

8 9

Explicație

Pe o tablă 9x9 numărul 36 va ajunge pe linia 8 şi coloana 9.


Exemplu

horse.in

41
1000

horse.out

14 7

Explicație

Pe o tablă 41x41 numărul 1000 va ajunge pe linia 14 şi coloana 7.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Horse:

program horses;
const fin='horse.in';
      fout='horse.out';
var l,c,rest,n,p,i,j:longint;
    f,g:text;
procedure horse(n,p:longint;var l,c:longint);
var q:longint;
begin
  if p=sqr(n) then
    begin
      l:=(n+1) div 2;
      c:=l;
      exit;
    end;
  rest:=0;
  while (p>8*n-16) do
    begin
      rest:=rest+2;
      p:=p-8*n+16;
      n:=n-4;
    end;
  if (p<=n div 2) then
    begin
      q:=p;
      c:=2*q-1+rest;
      l:=2-q mod 2+rest;
    end;
  if (p>n div 2) and (p<n) then
    begin
      q:=p-n div 2;
      c:=n-1+q mod 2 + rest;
      l:=2*q-1+rest;
    end;
  if (p>=n) and (p<n + n div 2) then
    begin
      q:=p-n;
      c:=n-2*q+rest;
      l:=n-q mod 2+rest;
    end;
  if (p>=n+n div 2) and (p<2*n-1) then
    begin
      q:=p-n-n div 2;
      l:=n-2*q+rest;
      c:=1+q mod 2+rest;
    end;
  if (p>=2*n-1) and (p<2*n-2+ n div 2) then
    begin
      q:=p-2*n+1;
      c:=2*q+3+rest;
      l:=1+q mod 2+rest;
    end;
  if (p>=2*n-2+ n div 2) and (p<3*n-3) then
    begin
      q:=p-2*n+2-n div 2;
      c:=n-q mod 2 + rest;
      l:=2*q+2+rest;
    end;
  if (p>=3*n-3) and (p<3*n-4+n div 2) then
    begin
      q:=p-3*n+3;
      c:=n-2*q-3+rest;
      l:=n-q mod 2+rest;
    end;
  if (p>=3*n-4+n div 2) and (p<4*n-6) then
    begin
      q:=p-3*n+4-n div 2;
      l:=n-2*q-2+rest;
      c:=1+q mod 2+rest;
    end;
  if (p>=4*n-6) and (p<4*n-6+ n div 2) then
    begin
      q:=p-4*n+6;
      c:=2*q+2+rest;
      l:=1+q mod 2+rest;
    end;
  if (p>=4*n-6+ n div 2) and (p<5*n-8) then
    begin
      q:=p-4*n+6-n div 2;
      c:=n-q mod 2 + rest;
      l:=2*q+4+rest;
    end;
  if (p>=5*n-8) and (p<5*n-9+n div 2) then
    begin
      q:=p-5*n+8;
      c:=n-2*q-2+rest;
      l:=n-q mod 2+rest;
    end;
  if (p>=5*n-9+n div 2) and (p<6*n-11) then
    begin
      q:=p-5*n+9-n div 2;
      l:=n-2*q-1+rest;
      c:=1+q mod 2+rest;
    end;
  if (p>=6*n-11) and (p<6*n-11+ n div 2) then
    begin
      q:=p-6*n+11;
      c:=2*q+2+rest;
      l:=2-q mod 2+rest;
    end;
  if (p>=6*n-11+ n div 2) and (p<7*n-13) then
    begin
      q:=p-6*n+11-n div 2;
      c:=n-q mod 2 + rest;
      l:=2*q+3+rest;
    end;
  if (p>=7*n-13) and (p<7*n-13+n div 2) then
    begin
      q:=p-7*n+13;
      c:=n-2*q-1+rest;
      l:=n-q mod 2+rest;
    end;
  if (p>=7*n-13+n div 2) and (p<8*n-15) then
    begin
      q:=p-7*n+13-n div 2;
      l:=n-2*q-3+rest;
      c:=1+q mod 2+rest;
    end;
end;
begin
  assign(f,fin);
  reset(f);
  readln(f,n);
  readln(f,p);
  close(f);
  assign(g,fout);
  rewrite(g);
  l:=0;c:=0;
  horse(n,p,l,c);
  writeln(g,l,' ',c);
  close(g);
end.

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #740 Horse

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #740 Horse de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!