Runda 24 (Hard) - Rower

20.06.2011 - Damian Rusak
TrudnośćTrudność

Zadanie tygodnia

runda 24; kategoria Hard

Limit czasowy: 1s; Limit pamięciowy: 32MB


Rower

Adam kupił właśnie nowy turborower. Taki rower jest wyposażony w dwa przyciski na kierownicy, oba wpływające na prędkość roweru. Rower rozpoczyna prędkość z pewną stałą fabrycznie dobraną prędkością - wynosi ona $ x $ jednostek. Adam bardzo chciałby rozpędzić się do prędkości wynoszącej dokładnie $ y $ jednostek. 

Naciśnięcie pierwszego przycisku sprawia, że prędkość roweru rośnie $ a $ razy, zaś po wciśnięciu drugiego przycisku prędkość zwiększa się o $ b $ jednostek. Adam zastanawia się, ile co najmniej razy musi naciskać na oba przyciski aby prędkość zmieniła się z $ x $ na $ y $?

Dla przykładu jeśli $ x = 5, y = 23, a = 3, b = 1 $ to kombinacja naciśnięć $ bbabb $ i $ bbbbbbbbbbbbbbbbbb $, $ babbbbb $, $ abbbbbbbb $ są akceptowalne, zaś najkrótsza jest ta pierwsza. (oznaczamy przez $ a $ naciśnięcie pierwszego przycisku, a przez $ b $ drugiego).

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $ t $ - liczbę zestawów testowych. ($ 1 \leq t \leq 10 $) Każdy zestaw testowy składa się z czterech liczb całkowitych $ x $,$ y $,$ a $,$ b $. ($  0\leq x,y \leq 10^{18}, 1 \leq a,b \leq 10^{18} $). 

Wyjście:

Dla każdego zestawu testowego należy wypisać najmniejszą liczbę naciśnięć przycisków potrzebną do zmiany prędkości z $ x $ na $ y $. Jeśli jest to niemożliwe należy wypisać -1.

Przykład:

Wejście:

3
3 14 2 3
3 200 11 1
5 23 3 1

Wyjście:

-1
18
5

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com