|
||||||||||||||||
ultima problemă
grupă: mică
sursă: OMI 2016 ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
|
Micul robotel Herbert s-a saturat sa tot alerge dupa butonase albe in griduri dreptunghiulare asa ca s-a hotarat sa accepte un nou tip de sarcina. El a fost asezat intr-o zona "triunghiulara" de dimensiune n (zona este formata din n linii astfel: pe prima linie se afla o locatie, pe a doua linie se gasesc 2 locatii...etc pe linia n se gasesc n locatii), ca in figura:
Fiecare locatie din zona este identificata prin doua coordonate numere naturale (prima coordonata reprezinta linia, iar a doua diagonala la care se afla locatia respectiva). Atunci cand Herbert se afla la coordonatele (x,y) el se poate deplasa doar in una din cele 6 locatii vecine: (x-1,y-1), (x-1,y), (x,y+1), (x+1,y+1), (x+1,y), (x,y-1). Sarcina robotelului este sa plece dintr-o locatie initiala (xs,ys) si sa ajunga la o locatie finala (xf,yf) trecand prin toate locatiile triunghiului o singura data (inclusiv prin cea initiala si cea finala va trece o singura data). Locatia initiala si cea finala nu coincid niciodata. Insa Herbert e un robotel care se plictiseste repede. Asadar, pentru ca el sa nu poata fugi din zona triunghiulara, nu va avea niciodata locatiile de inceput si de sfarsit fixate pe laturi. O locatie (x,y) se afla pe laturi daca: y = 1 sau x = y sau x = n. Fiind si idealist, va refuza din start acele sarcini care i se par redundante. Nu va accepta ca numarul liniei pe care se afla locatia finala sa fie mai mica decat numarul liniei pe care se afla locatia initiala (adica xf < xs) pentru ca parcurgand drumul invers, intr-o astfel de configuratie, poate sa reduca problema la cazul xs < xf. Asadar xs va fi mereu strict mai mic decat xf. Cerinta Sa se determine pentru robotel un drum care trece prin toate locatiile triunghiului exact o data. Drumul trebuie sa inceapa in (xs,ys) si sa se termine in (xf,yf). Date de intrare Fisierul de intrare herbert.in are urmatoarea structura: Date de iesire Fisierul de iesire herbert.out va contine n(n + 1)/2 linii care
descriu drumul gasit astfel: Restrictii
Exemplu
Iolanda Popa propunător: Prof. Emanuela Cerchez emanuela.cerchez@gmail.com Probleme recomandate
|
|||||||||||||||
surse trimise | ajutor |