Subiecte Algoritmică 2015

1. New York

Ionuț s-a mutat în New York, oraș cunoscut pentru dispunerea străzilor în stil Manhattan. Știind că el își are casa localizată la punctul de coordonate X_i, Y_i și că obiectivul lui este de a ajunge la autostradă, care este dreapta de ecuația A*X + B*Y = 1. Ionuț se poate deplasa doar în N, S, E, V. Noi trebuie să îl ajutăm pe Ionuț spunându-i care este distanța minimă de la el la autosradă.

            Fișierul new_york.in conține pe prima linie un număr natural T(<=1000) reprezentând numărul de teste, iar pe următoarele T linii sunt câte 4 numere care reprezintă A,B, X_i și Y_i.

            În fișierul new_york.out vor fi T linii reprezentând răspunsul la fiecare din cele T teste.

            Specificații:

            A, B, X_i, Y_i sunt numere întregi cu semn reprezentate pe 32 de biți.

            A și B nu sunt simultan egale cu 0.

            Se recomandă folosirea a 8 zecimale.

           

            Timp de execuție: 0.1 secunde pe test.

           

            Exemplu:

            new_york.in                            new_york.out

             2                                             5.0000

             1  2 3 4                                   6.0000

            -1 -2 3 4

           

           

2.Arbori echilibrați

Numim un arbore binar echilibrat (sau arbore AVL) dacă subarborii fiecărui nod diferă cu cel mult 1 în înalțime. Scrieți un program care citește din fișierul ”arbore.in” un număr natural n și scrieți în fișierul ”arbore.out” pe o linie numărul de arbori binari echilibrați cu n noduri care au înălțime minimă. Se presupune că n și răspunsul pot fi reprezenta ca numere fără semn pe 64 de biți. Timp de rulare: 1 secundă.

 arbore.in  arbore.out

            5                      6

 

 

https://onedrive.live.com/redir?resid=64a23a21b50d68a9%2112900