Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2017-03-31 16:50:12.
Revizia anterioară   Revizia următoare  

 

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

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.inaiacuhexagoane.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

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