ACMP 110: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Ссылка на задачу == | == Ссылка на задачу == | ||
* [http://acmp.ru/?main=task&id_task=110 ACMP #110 — Красивые числа] | * [http://acmp.ru/?main=task&id_task=110 ACMP #110 — Красивые числа] | ||
== Комментарии == | |||
Пусть number — исходное число, digit — требуемая цифра. | |||
Создадим аналог структуры BigDegimal (такая структура должна позволять хранить целую часть, вещественную часть и период). Сохраним такой структуре значение ratio = number / digit. | |||
Теперь number = ratio * digit, поэтому остаётся представить ratio как сумму дробей, содержащих только нули и единицы (далее эти дроби умножаются на digit, что и будет ответом). Очевидно, что если наибольшая цифра ratio равна D<sub>max</sub>, то в ответе будет D<sub>max</sub> дробей; если i-я цифра числа ratio равна D<sub>i</sub>, то первые (D<sub>max</sub> - D<sub>i</sub>) дробей содержат на i-й позиции ноль, остальные D<sub>i</sub> — единицу. | |||
Дроби, входящие в сумму, нужно грамотно нормализовать: | |||
* если целая часть содержит ведущие нули, они убираются; | |||
* если нет периода и дробная часть содержит конечные нули, они убираются; | |||
* если дробная часть или её конец может войти в период, дробная часть пересчитывается; | |||
* если период может быть сокращён, он пересчитывается; | |||
* если период равен 0, он убирается; | |||
* если нет периода и дробная часть равна 0, она убирается. | |||
После этого осталось вывести дроби, выводя digit вместо единиц. | |||
== Похожие задачи == | == Похожие задачи == | ||
Текущая версия от 19:20, 25 мая 2016
Ссылка на задачу
Комментарии
Пусть number — исходное число, digit — требуемая цифра.
Создадим аналог структуры BigDegimal (такая структура должна позволять хранить целую часть, вещественную часть и период). Сохраним такой структуре значение ratio = number / digit.
Теперь number = ratio * digit, поэтому остаётся представить ratio как сумму дробей, содержащих только нули и единицы (далее эти дроби умножаются на digit, что и будет ответом). Очевидно, что если наибольшая цифра ratio равна Dmax, то в ответе будет Dmax дробей; если i-я цифра числа ratio равна Di, то первые (Dmax - Di) дробей содержат на i-й позиции ноль, остальные Di — единицу.
Дроби, входящие в сумму, нужно грамотно нормализовать:
- если целая часть содержит ведущие нули, они убираются;
- если нет периода и дробная часть содержит конечные нули, они убираются;
- если дробная часть или её конец может войти в период, дробная часть пересчитывается;
- если период может быть сокращён, он пересчитывается;
- если период равен 0, он убирается;
- если нет периода и дробная часть равна 0, она убирается.
После этого осталось вывести дроби, выводя digit вместо единиц.