Godzina Kodowania to też zadania nietuzinkowe.
To zadanie przygotował Andrzej Dyrek, autor wielu zadań Olimpijskich oraz zadań na zawody CMI. Ciekawe komu uda się rozwiązać i przesłać wynik.
A zadanie o ułamkach łańcuchowych… zaczyna się tak:
Każdy ułamek zwykły p/q (gdzie p i q są dodatnimi liczbami całkowitymi oraz p < q) da się przedstawić jako skończony ułamek okresowy postaci:
Liczby a1, a2, . . . , an są dodatnimi liczbami naturalnymi. Dla przykładu:
Napisz program, który dla danych liczb p oraz q wyliczy liczby a1, a2, . . . , an
Dane wejściowe
Pierwszy wiersz danych wejściowych zawiera dodatnia liczbę naturalna n (1 ≤M ≤ 1000) – ilość ułamków do przetworzenia.
Każdy kolejny k-ty wiersz (k = 1, 2, . . .M) zawiera po dwie liczby naturalne p oraz q
(1 ≤ p < q ≤106) – licznik i mianownik ułamka zwykłego.
Liczby w wierszach oddzielone są pojedynczymi odstępami.
Wynik programu
Program powinien dla każdego ułamka wypisać wiersz tekstu zawierający listę liczb a1, a2, . . . , an
oddzielonych pojedynczymi odstępami (wartość n zależy od konkretnego ułamka).
Przykład
Dla danych wejściowych
4
1 3
2 5
7 11
123 997
prawidłowym wynikiem jest:
3
2 2
1 1 1 3
8 9 2 6
Jeśli myślicie o nagrodach – zapraszamy do wysłania zadania na adres: sis@pti.org.pl