== include(page="template/taskheader" task_id="aiacuhexagoane") ==

Poveste şi cerinţă...

Un plan se poate pava folosind hexagoane regulate de aceeaşi dimensiune. O furnică poate trece dintr-un hexagon în altul numai dacă cele două hexagoane sunt unite printr-o latură a unui hexagon vecin comun, ca în figură (ex: din hexagonul 1 poate ajunge în hexagonul 5, deoarece ele sunt legate printr-o latură a hexagonului 2, vecin cu hexagoanele 1 şi 5).
 
!problema/aiacuhexagoane?hexagoane1.png!
 
 

h2. Date de intrare

...
== 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
3
1 5
1 2
3 4
da
nu
da
Î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.
 
 
 
 
 
 
 
 
 
 
Timp maxim de execuţie/test: 1 sec
Memorie totală: 16 MB din care stiva 16 MB
Dimensiunea maximă a sursei: 10 kB