
Subiecte Algoritmică 2015
Publicat Sâm, 04/04/2015 - 16:33
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