ACMP 110: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=110 ACMP #110 — Красивые числа] Category: Сборник зада…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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 вместо единиц. | |||
== Похожие задачи == | |||
* [[РОИ 2004-2005, заключительный этап, D]] | |||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Математика]] | [[Category: Задачи: Математика]] | ||
[[Category: Задачи: Сложный вывод]] | [[Category: Задачи: Сложный вывод]] | ||
Текущая версия от 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 вместо единиц.