ACMP 110

Материал из Олимпиадное программирование в УлГТУ
Версия от 19:20, 25 мая 2016; Ctrlalt (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Ссылка на задачу

Комментарии

Пусть number — исходное число, digit — требуемая цифра.

Создадим аналог структуры BigDegimal (такая структура должна позволять хранить целую часть, вещественную часть и период). Сохраним такой структуре значение ratio = number / digit.

Теперь number = ratio * digit, поэтому остаётся представить ratio как сумму дробей, содержащих только нули и единицы (далее эти дроби умножаются на digit, что и будет ответом). Очевидно, что если наибольшая цифра ratio равна Dmax, то в ответе будет Dmax дробей; если i-я цифра числа ratio равна Di, то первые (Dmax - Di) дробей содержат на i-й позиции ноль, остальные Di — единицу.

Дроби, входящие в сумму, нужно грамотно нормализовать:

  • если целая часть содержит ведущие нули, они убираются;
  • если нет периода и дробная часть содержит конечные нули, они убираются;
  • если дробная часть или её конец может войти в период, дробная часть пересчитывается;
  • если период может быть сокращён, он пересчитывается;
  • если период равен 0, он убирается;
  • если нет периода и дробная часть равна 0, она убирается.

После этого осталось вывести дроби, выводя digit вместо единиц.

Похожие задачи