Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTWPZ085 - PTwPZ Przekładnie

Przekładnie

Treść

Podlaska Agencja Kosmiczna, pomimo braku medialnego nagłośnienia, jest przez fachowców typowana na przyszłego globalnego lidera podboju kosmosu. Dzieje się tak ze względu na ogromną ilość przełomowych rozwiązań stosowanych w projektach Agencji. Inżynierowie skupiają się tu przede wszystkim na ekonomii wytwarzanych podzespołów tak, by koszty przedsięwzięć kosmicznych nie były barierą w przeprowadzaniu ich na szeroką skalę.

Jednym z takich rozwiązań jest układ napędowy statku kosmicznego. Składa się on z jednego prostego silnika oraz wielu przekładni przekazujących jego moc do wszystkich odbiorników. Każda z przekładni działa w układzie 1:a (zwiększenie prędkości obrotowej a razy) lub a:1 (zmniejszenie prędkości obrotowej a razy). Przy połączeniu przekładni w łańcuch można uzyskać prawie dowolne przełożenie całkowite takiego układu.

Właśnie dowiedziałeś się, że Twoje podanie o przyjęcie na staż do PAK zostało zaakceptowane. Niestety nie od razu będziesz mógł zająć się badaniem prędkości nadświetlnych i innymi interesującymi zagadnieniami. Na początek postawiono przed Tobą zadanie zrobienia porządków po poprzedniku. Poprzednik ów zajmował się łączeniem przekładni w łańcuchy. Niestety nie pozostawił po sobie żadnej dokumentacji i nie wiadomo teraz jakie jest całkowite przełożenie łańcucha. Na szczęście zachowały się parametry i kolejność ułożenia pojedynczych przekładni. Napisz program, który na podstawie tych danych obliczy przełożenie całego układu.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera liczbę całkowitą n (1<=n<=106) przekładni w łańcuchu. W kolejnych n wierszach podane są opisy poszczególnych przekładni. Pojedynczy opis składa się z dwóch liczb całkowitych ai i bi (1<=ai,bi<=106) definiujących przełożenie ai:bi, przy czym zawsze jedna z tych liczb jest równa 1.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest para liczb całkowitych a i b, oddzielonych pojedynczą spacją, oznaczających przełożenie całego łańcucha przekładni. Ze względu na to, iż taka sama wartość przełożenia może być podana na wiele sposobów, np. 1:2 i 2:4, jako wynik należy wypisać tę parę, dla której wartość a jest najmniejsza z możliwych. Dane wejściowe są tak dobrane, że wartości a i b nie przekraczają 109.

Przykład

dane wejściowe:
3
3
4 1
1 6
3 1
3
1 27
3 1
9 1
4
1 500000
1 300000
1000000 1
200000 1

wynik:
2 1
1 1
4 3


Dodane przez:Michael Suchacz
Data dodania:2009-07-24
Limit czasu wykonania programu:0.283s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Pochodzenie:Podlaski Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.