ACMP 110
(перенаправлено с «РОИ 2004-2005, заключительный этап, D»)
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Комментарии
Пусть number — исходное число, digit — требуемая цифра.
Создадим аналог структуры BigDegimal (такая структура должна позволять хранить целую часть, вещественную часть и период). Сохраним такой структуре значение ratio = number / digit.
Теперь number = ratio * digit, поэтому остаётся представить ratio как сумму дробей, содержащих только нули и единицы (далее эти дроби умножаются на digit, что и будет ответом). Очевидно, что если наибольшая цифра ratio равна Dmax, то в ответе будет Dmax дробей; если i-я цифра числа ratio равна Di, то первые (Dmax - Di) дробей содержат на i-й позиции ноль, остальные Di — единицу.
Дроби, входящие в сумму, нужно грамотно нормализовать:
- если целая часть содержит ведущие нули, они убираются;
- если нет периода и дробная часть содержит конечные нули, они убираются;
- если дробная часть или её конец может войти в период, дробная часть пересчитывается;
- если период может быть сокращён, он пересчитывается;
- если период равен 0, он убирается;
- если нет периода и дробная часть равна 0, она убирается.
После этого осталось вывести дроби, выводя digit вместо единиц.