Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | aiacuhexagoane.in, aiacuhexagoane.out | Sursă | Grigore Moisil 2017, 9 |
| Autor | Vlad Mihaly | Adăugată de |  Grigore Moisil •grigore.moisil |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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).
Date de intrare
Fişierul de intrare aiacuhexagoane.in ...
Date de ieşire
În fişierul de ieşire aiacuhexagoane.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| aiacuhexagoane.in | aiacuhexagoane.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
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
