Enumerarea lui Cantor realizeaza o bijectie de la multimea numerelor naturale N la multimea perechilor de numere naturale NxN, plasand pe rand numerele naturale intr-un tablou infinit in felul urmator:
Bijectia se realizeaza intre orice numar din tabel, evident din N si perechea formata din numerele ce reprezinta linia si coloana pe care acest numar se afla din NxN
In aceasta problema ne intereseaza sa determinam pentru un numar dat k si un dreptunghi definit prin coordonatele coltului stanga-jos si dreapta-sus, ce contine toate numerele aflate in tabel in interiorul acestui dreptunghi inclusiv pe laturi, care dintre acestea este cel mai apropiat de numarul k. Distanta doua numere este egala cu modulul diferentei lor.
De exemplu, dreptunghiul definit de coordonatele (1, 1) si (2,3) contine urmatoarele numere:
7 12 18
4 8 13
Pentru acest dreptunghi si valoarea k = 9 raspunsul corect ar fi 8 fiind cel mai apropiat numar. In cazul in care in dreptunghi sunt incluse doua numere la aceeasi distanta minima de numarul k se cere cel mai mic dintre ele. (de exemplu, pentru dreptunghiul de mai sus si k = 10 raspunsul este tot 8).
Cerinţă
Scrieti un program care gaseste raspunsul pentru mai multe configuratii.
Date de intrare
Fisierul cantor.in contine pe prima linie numarul natural T reprezentand numarul de configuratii ce urmeaza. Pe urmatoarele T linii se gasesc cate 5 numere naturale k, x1, y1, x2, y2 reprezentand numarul k si coordonatele dreptunghiului.
Date de ieşire
Fisierul de iesire cantor.out trebuie sa contina T linii cu cate un singur numar, reprezentand rezultatul pentru fiecare configuratie din fisierul de intrare.
Restricţii
T <= 10000
0 <= x1 <= x2 <= 109
0 <= y1 <= y2 <= 109
0 <= k < 263
Pentru implementare este suficienta folosirea numerelor pe 64 biti
Exemple
cantor.in
cantor.out
2
9 1 1 2 3
10 1 1 2 3
8
8
stud. Paul Diac
Universitarea « Al. I Cuza », Iaşi – Facultatea de informatica