Misir Kəsrləri
Misir Orta Krallığı dövründə misirlilər kəsrləri yazmaq üçün yeni bir üsul inkişaf etdirdilər. Tam ədədin hiyeroglifinə müəyyən bir simvol əlavə etmək həmin ədədin qarşılığını təmsil etmək kimi başa düşülürdü. Bu, 1 / n (bir vahid kəsr adlanır) formasında hər hansı bir kəsri yazmağı asanlaşdırdı — sadəcə n üçün hiyeroglifə qarşılıq simvolunu əlavə edin.
m / n formasında, burada m > 1 olan bir kəsri təmsil etmək üçün birbaşa yol yox idi. Bunun əvəzinə, belə bir kəsr vahid kəsrlərin cəmi kimi yazılırdı. Məsələn, 3 / 4 kəsri belə yazıla bilərdi:
Qeyd edək ki, bir neçə cəm eyni nəticəni verə bilər; məsələn, həmçinin belə yazıla bilər:
Sizin işiniz kəsrini götürmək və onu "acgöz" axtarış yolu ilə vahid kəsrlərin cəmi kimi yazmaqdır. Acgöz axtarışda siz orijinal kəsrinizdən qalanı sıfıra qədər ən böyük mümkün vahid kəsri davamlı olaraq çıxırsınız. Məsələn, kəsrini nəzərdən keçirin. Acgöz axtarış üç addımda cəmini tapardı, belə ki:
Qeyd edək ki, hər addımda orijinal kəsrimizdən qalanı ən böyük mümkün vahid kəsri çıxırdıq.
Həllərimizin çox böyük olmamasını təmin etmək üçün bir əlavə məhdudiyyət əlavə edilməlidir: Hər dəfə bir vahid kəsr çıxardığımızda, məxrəci 1,000,000-dən kiçik olan bir kəsr qalmalıdır. Məsələn, kəsrini nəzərdən keçirin. Çıxaracağımız ilk iki vahid kəsr və olardı, bizi ilə tərk edərdi. Bu nöqtədə çıxara biləcəyimiz ən böyük vahid kəsr olardı, bizi
təəssüf ki, bu bizi məxrəci 1,000,000-dən böyük olan bir kəsrlə tərk edir, buna görə də bu vahid kəsri cəmimizdə istifadə edə bilmərik. Növbəti ən böyük vahid kəsrə keçirik, , bu bizi
ilə tərk edir. Son cavab məxrəci 1,000,000-dən kiçik olan bir kəsrə endirildiyi üçün bu vahid kəsrdən istifadə edə bilərik, bizi son cavabla tərk edir.
Bu halda yalnız bir kəsri keçmək məcburiyyətində qaldıq. Lakin, ümumiyyətlə, işləyəcək birini tapmaq üçün bir çox kəsri keçmək məcburiyyətində qala bilərsiniz. Axtarış edərkən, böyük məxrəcləri olan bir çox kəsr üzərində hesablamalar aparmalı olacaqsınız; bunu səmərəli şəkildə etdiyinizə əmin olun, əks halda proqramınızın icrası çox uzun çəkə bilər.
Həmçinin, işlədiyiniz böyük ədədləri saxlamaq üçün kifayət qədər böyük bir məlumat növündən istifadə etdiyinizə əmin olun. Məxrəcləri 1,000,000 ilə məhdudlaşdırmış olsaq da, məxrəcləri 10^12-ə qədər olan aralıq dəyərləri hesablamaq məcburiyyətində qala bilərsiniz. Belə dəyərləri saxlamaq üçün 64-bitlik tam ədəd tələb olunacaq (Java-da long, C/C++-da long long).
Nəhayət, qeyd etmək lazımdır ki, acgöz alqoritm təbiətinə görə həmişə məxrəcləri 1,000,000-dən kiçik olan kəsrlərdən ibarət bir cavab tapacaq, çünki ən azından hər hansı bir kəsr öz məxrəci ilə vahid kəsrlərin cəmi kimi təmsil edilə bilər. Məsələn:
Giriş
Giriş bir sıra kəsrlərdən ibarət olacaq; hər sətirdə bir kəsr. Hər sətirdə yalnız iki tam ədəd M və N olacaq, burada 1 < M < N < 100, kəsrini təmsil edir. M və N-in 1-dən böyük ümumi böləni olmayacaq. Girişin sonu iki sıfırla göstəriləcək: 0 0.
Çıxış
Hər bir giriş kəsri üçün siz bir sətir çıxış etməlisiniz ki, burada D[1] ≤ D[2] ≤ D[3] ≤ … belə ki:
Bu, məxrəcin 1,000,000 məhdudiyyətini tətbiq edərkən acgöz axtarışdan istifadə edərək əldə edilən ilk cəm olmalıdır. Hər bir ədəd bir boşluqla ayrılmalıdır, heç bir qabaqcıl və ya son boşluq olmamalıdır.