X Olimpiada Informatyczna 2002/2003
|
Zadanie: kaf
|
Autor: Rafał Rusin
|
Zawody II stopnia, dzień drugi |
Plik źródłowy: | kaf.xxx (xxx=pas,c,cpp) |
Alternatywne formaty: PostScript | PDF
Majster Bajtazar wraz ze swym pomocnikiem Bajtolinim układają kafelki w łazience państwa Bajtockich. Elementem dekoracyjnym w łazience ma być poziomy pas złożony z rozmaitych wzorzystych kafli, szerokości n kafli i wysokości jednego kafla. Pani Bajtocka powiedziała Bajtoliniemu, że kafelki tworzące poziomy pas muszą być ułożone tak, żeby tworzyły wzór powtarzający się co k kafli. Ledwo pani Bajtocka wyszła, przyszedł pan Bajtocki i powiedział Bajtoliniemu, że kafelki tworzące poziomy pas muszą być ułożone tak, żeby tworzyły wzór powtarzający się co l kafli. Biedny Bajtolini przyszedł do Bajtazara po radę:
- Mistrzu Bajtazarze, to jak mam w końcu ułożyć kafelki? Czy wzór ma się powtarzać co k, czy co l kafli?
- Nasz klient, nasz pan! Musisz ułożyć kafelki tak, żeby wzór powtarzał się zarówno co k jak i co l kafli. Ponadto musisz użyć jak największej liczby różnych kafli, tak aby wzór nie był zbyt monotonny. A teraz już nie filozofuj, tylko do roboty!
Bajtolini zgłupiał do reszty. Pomóż mu!
Napisz program, który:
Na standardowym wejściu znajdują się trzy liczby całkowite n, k i l, odpowiednio, w pierwszym, drugim i trzecim wierszu. Liczby te spełniają zależności 1 <= n <= 10500, 1 <= k, l <= n. Uwaga: liczby k i l nie muszą być dzielnikami n.
Twój program powinien wypisać na standardowe wyjście (w pierwszym i jedynym wierszu) jedną liczbę całkowitą - maksymalną liczbę różnych kafli jakich należy użyć do udekorowania łazienki pasem długości n tak, żeby wzór powtarzał się zarówno co k, jak i l kafli.
Dla danych wejściowych:
10 5 7
poprawnym wynikiem jest:
2