Fişierul intrare/ieşire:aiacuhexagoane.in, aiacuhexagoane.outSursăGrigore Moisil 2017, 9
AutorVlad MihalyAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aiacuhexagoane

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

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

Date de ieşire

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

Restricţii

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

Exemplu

aiacuhexagoane.inaiacuhexagoane.out
2 3
3
1 5
1 2
3 4
da
nu
da

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?