Pagini recente » Diferente pentru problema/zeap intre reviziile 3 si 2 | Diferente pentru problema/magic intre reviziile 22 si 18 | Diferente pentru problema/turnuri5 intre reviziile 7 si 8 | Diferente pentru problema/bmat intre reviziile 3 si 4 | Diferente pentru problema/aiacuhexagoane intre reviziile 1 si 2
Nu exista diferente intre titluri.
Diferente intre continut:
== 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
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.