!problema/aiacuhexagoane?hexagoane1.png!
O parte a planului este preluată şi se formează un grid hexagonal. Grid-ul hexagonal va avea $N$ linii. Liniile impare conţin câte $M$ hexagoane fiecare, iar liniile pare conţin câte $M-1$ hexagoane fiecare. Hexagoanele din grid se numerotează ca în figura alăturată. Fiind date $Q$ perechi de hexagoane $(h1, h2)$, se cere să se determine dacă furnica, pornind din $h1$, poate ajunge în $h2$, eventual trecând prin alte hexagoane intermediare pentru a forma un drum.
!problema/aiacuhexagoane?hexagoane2.png!
h2. Date de intrare
Fişierul de intrare $aiacuhexagoane.in$ ...
Fişierul de intrare $aiacuhexagoane.in$ conţine pe prima linie două numere naturale $N$ şi $M$, reprezentând numărul de linii, respectiv numărul de hexagoane aflate pe prima linie. Următoarea linie conţine un număr natural $Q$, reprezentând numărul de întrebări, iar fiecare din următoarele $Q$ linii conţine câte două numere separate prin spaţiu, reprezentând valorile $h1$ şi $h2$ din enunţ.
h2. Date de ieşire
În fişierul de ieşire $aiacuhexagoane.out$ ...
În fişierul de ieşire $aiacuhexagoane.out$ conţine $Q$ linii, corespunzătoare celor $Q$ perechi de hexagoane. Pentru fiecare pereche se va afişa $da$, în cazul în care există drum între hexagoanele perechii respective, sau $nu$, în caz contrar.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 10^9^; 2 ≤ M ≤ 10^9^; 1 ≤ Q ≤ 10^5^$.
* Pentru teste in valoare de 20 de puncte $N, M ≤ 15$.
* Pentru teste in valoare de 65 de puncte $N, M ≤ 800$.
* Problema va fi evaluată pe teste în valoare de 90 de puncte.
* Exemplele vor reprezenta teste în valoare de 10 ("puncte din oficiu") şi vor fi cu feedback.
* Cele $Q$ perechi de hexagoane vor fi unice. Atenţie: perechea de hexagoane $h1$ şi $h2$ este diferită de $h2$ şi $h1$.
* $h1 ≠ h2$
h2. Exemplu
table(example). |_. aiacuhexagoane.in |_. aiacuhexagoane.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="aiacuhexagoane") ==
Cerinţă
O parte a planului este preluată şi se formează un grid hexagonal. Grid-ul hexagonal va avea N linii. Liniile impare conţin câte M hexagoane fiecare, iar liniile pare conţin câte M-1 hexagoane fiecare. Hexagoanele din grid se numerotează ca în figura alăturată. Fiind date Q perechi de hexagoane (h1, h2), se cere să se determine dacă furnica, pornind din h1, poate ajunge în h2, eventual trecând prin alte hexagoane intermediare pentru a forma un drum.
Date de intrare
Fişierul aiacuhexagoane.in conţine pe prima linie două numere naturale N şi M, reprezentând numărul de linii, respectiv numărul de hexagoane aflate pe prima linie. Următoarea linie conţine un număr natural Q, reprezentând numărul de întrebări, iar fiecare din următoarele Q linii conţine câte două numere separate prin spaţiu, reprezentând valorile h1 si h2 din enunţ.
Date de ieşire
Fişierul aiacuhexagoane.out conţine Q linii, corespunzătoare celor Q perechi de hexagoane. Pentru fiecare pereche se va afişa da, în cazul în care există drum între hexagoanele perechii respective, sau nu, în caz contrar.
Restricţii şi precizări
1 ≤ N ≤ 109; 2 ≤ M ≤ 109; 1 ≤ Q ≤ 105.
Pentru teste in valoare de 20 de puncte N, M ≤ 15.
Pentru teste in valoare de 65 de puncte N, M ≤ 800.
Problema va fi evaluată pe teste în valoare de 90 de puncte.
Se vor acorda 10 puncte din oficiu.
Cele Q perechi de hexagoane vor fi unice. Atenţie: perechea de hexagoane h1 si h2 este diferită de h2 si h1 .
Exemplu
aiacuhexagoane.in
aiacuhexagoane.out
Explicaţii
2 3
| 2 3
3
1 5
1 2
3 4
da
| da
nu
da
|
h3. Explicaţie
Între hexagonul 1 şi hexagonul 5 există un drum pe latura hexagonului 2.
Între hexagonul 1 şi hexagonul 2 nu există drum, hexagonul 2 fiind izolat de toate celelalte.
Între hexagonul 3 şi hexagonul 4 există un drum pe latura hexagonului 2.
!problema/aiacuhexagoane?hexagoane3.png!
Timp maxim de execuţie/test: 1 sec
Memorie totală: 16 MB din care stiva 16 MB
Dimensiunea maximă a sursei: 10 kB
== include(page="template/taskfooter" task_id="aiacuhexagoane") ==
