Fişierul intrare/ieşire:cartite.in, cartite.outSursăOJI 2014, clasele 11-12
AutorDoru Popescu AnastasiuAdăugată detudorv96Tudor Varan tudorv96
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cartite

Cârtitele sunt animale de dimensiuni mici care îsi duc traiul pe suprafete de teren deschis, având ca dusman principal vulpea. Lânga o padure se afla o zona agricola în forma dreptunghiulara, împartita în patratele de aceeasi dimensiune. Zona agricola este reprezentata printr-un tablou bidimensional cu M linii si N coloane, având liniile si coloanele numerotate începând cu 1. În aceasta zona agricola traieste o cârtita si K vulpi.
Pentru cârtita cunoastem coordonatele ei (linia si coloana) pe care se gaseste, la fel si pentru vulpi, care stau la pânda pentru a ataca cârtita în momentele ei de neatentie.
Pe suprafata terenului cârtita se poate deplasa din patratelul în care se afla doar într-unul dintre cele 4 patratele vecine pe directiile nord, sud, est sau vest.
Vulpile pot ataca instantaneu pe o raza de actiune de lungime 0, 1 sau 2 pe orizontala si verticala, inclusiv în pozitia unde se gasesc, dupa care tot instantaneu se întorc în pozitiile initiale. În figura de mai jos sunt desenate patratele unde poate ataca o vulpe pozitionata în patratelul cu cifra reprezentând raza de actiune.

Pentru a micsora riscul de deplasare în zona agricola cârtita sapa în pamânt un sistem de G galerii, care leaga între ele patratele din zona agricola. Aceste galerii nu se intersecteaza sub pamânt, ci doar la suprafata, trecerea dintr-o galerie în alta, care se intersecteaza în acelasi patratel facându-se printr-un sistem ce nu îi pune viata în pericol. Galeriile sunt indicate prin coordonatele patratelelor pe care le unesc. Acestea sunt sapate astfel încât, daca pornim dintr-un capat al unei galerii le putem parcurge pe toate. Nu exista doua galerii care sa porneasca din acelasi patratel si sa ajunga tot în acelasi patratel (galeriile sunt distincte).
Cârtita doreste sa se plimbe prin toate galeriile de sub teren trecând o singura data prin fiecare, dar pentru acest lucru trebuie sa ajunga nevatamata mergând la suprafata terenului la un patratel de unde sa intre în sistemul de galerii.

Cerinta

Determinati:
1.cel mai apropiat patratel de pozitia initiala a cârtitei prin care ea poate sa intre în galerie pentru a se plimba, precum si lungimea traseului parcurs la suprafata asftel încât fiecare patratica de pe traseu sa nu fie atacata de nicio vulpe;
2.traseul de plimbare numai prin galerii, specificat prin coordonatele patratelelor care constituie capetelor acestora.

Date de intrare

Fisierul de intrare cartite.in contine pe prima linie un numar natural p, care poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se afla numerele naturale M si N, reprezentând dimensiunile zonei agricole. Pe a treia linie se afla xc yc, coordonatele cârtitei. Pe linia a patra se afla numarul de vulpi K, apoi urmeaza K linii cu câte trei numere naturale reprezentând coordonatele patratelelor unde se gasesc vulpi si raza lor de actiune (0, 1 sau 2). Urmatoarea linie contine numarul de galerii G. Fiecare dintre urmatoarele G linii contine câte 4 numere naturale separate prin câte un spatiu, reprezentând coordonatele capetelor unei galerii.

Date de iesire

Daca valoarea lui p este 1, se va afisa numai rezultatul de la cerinta 1. În acest caz, în fisierul de iesire cartite.out se vor scrie trei numere naturale separate între ele prin câte un spatiu, reprezentând coordonatele patratelului unde va intra cârtita în galerii si lungimea traseului parcurs la suprafata.
Daca valoarea lui p este 2, se va afisa numai rezultatul de la cerinta 2. În acest caz, fisierul de iesire cartite.out va contine coordonatele patratelelor traseului de plimbare prin galerii (coordonatele câte unui patratel pe câte o linie, începând cu prima linie a fisierului de iesire). Patratelul de pornire trebuie sa fie acelasi cu cel în care ajunge cârtita la sfârsitul plimbarii si nu este obligatoriu sa fie acelasi cu cel în care ea intra în galerii de la suprafata terenului.

Restrictii

  • 1 ≤ M,N ≤ 200
  • 1 ≤ G ≤ 105
  • 0 ≤ K ≤ 50
  • Lungimea traseului parcurs la suprafata este egala cu numarul de patratele prin care aceasta trece, dar diferite de cel din care pleaca.
  • Fiecare dintre cerinte reprezinta 50% din punctaj.
  • Cârtita nu poate intra în galerii printr-un patratel din raza de actiune a unei vulpi.
  • Pentru toate testele exista solutie la cerinta a), adica exista un traseu sigur de la cârtita la o intrare într-o galerie.
  • Solutia, nu este unica, însa, orice solutie corecta va obtine punctajul maxim pe test.
  • Initial, cârtita se gaseste pe o pozitie în care nu este atacata de nicio vulpe.

Exemplu

cartite.incartite.out
1
6 4
6 3
3
5 1 0
3 4 1
4 3 0
7
1 1 3 2
1 3 1 4
1 1 3 3
1 4 4 2
4 2 3 3
4 2 1 3
4 2 3 2
4 2 3
2
6 4
6 3
3
5 1 0
3 4 1
4 3 0
7
1 1 3 2
1 3 1 4
1 1 3 3
1 4 4 2
4 2 3 3
4 2 1 3
4 2 3 2
1 1
3 2
4 2
1 3
1 4
4 2
3 3
1 1

Explicatie

Primul exemplu:

Deplasarea cârtiţei pe suprafaţa agricolă se va face pe traseul de lungime 3 ce trece prin pătrăţelele (6,3) (6,2) (5,2) (4,2). Coordonatele pătrăţelului de intrare în galerii sunt (4,2).
Atenţie! Pentru acest test se va afişa doar rezultatul la cerinţa a).

Al doilea exemplu:

Traseul de plimbare prin galerii este urmatorul: (1,1) (3,2) (4,2) (1,3) (1,4) (4,2) (3,3) (1,1), cu observatia ca se putea alege si alt patratel de plecare.
Atentie! Pentru acest test se va afisa doar rezultatul la cerinta b).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content