Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
963. Унарная система счисления
Динамическое программирование и запоминающие функцииПредрешение
Олимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 4J) |
| 09/07/2008 | Лето 2008 - 4 (J) |
| 05/09/2013 | Занятие 1 для продолжающих (C) |
| 04/07/2018 | Лето 2018 - 5 (E) |
| 06/07/2020 | Летние сборы - 4 (F) |
| 08/07/2020 | Лето 2020 - 4 (E) |
| 12/07/2021 | Лето 2021-7 (E) |
| 07/04/2022 | «Базовая олимпиадная подготовка» (second level) - Одномерная динамика (проводит novink) (G) |
| 06/07/2022 | Лето 2022-5 (E) |
| 10/07/2023 | Лето 2023-7 простые (F) |
| 08/07/2024 | Лето 2024-7 простые (F) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В унарной системе счисления натуральные числа записываются как соответствующее количество "палочек". Например, число 3 записывается как |||, а число 7 – как |||||||. Понятно, что с большими числами работать в унарной системе счисления неудобно. К счастью, есть арифметические операции + (сложение) и `times` (умножение). Пользуясь этими операциями, можно весьма компактно записывать унарные числа. Например, число 53 можно записать как |||||`times`|||||`times`||+|||, то есть 5*5*2+3, затратив всего лишь 21 "палочку". Откуда 21? – спросите вы – всего 15! Верно, 5+5+2+3=15, но вы не учли, что знаки умножения и сложения состоят из двух "палочек" каждый, вот и недостающие 6 "палочек". Углублённые исследования показали, что число 53 в унарной системе счисления никаким способом нельзя записать, использовав менее, чем 21 "палочку". Учтите, что использование скобок в записи унарных чисел категорически не допускается!
Напишите программу, которая находит минимальное количество "палочек", достаточное для записи унарного числа `N`.
Ввод
Входной файл может содержать несколько тестов (точнее, несколько тысяч). Каждый тест состоит из одного натурального числа `N` (`N\ ≤\ 5000`).
Вывод
Для каждого теста из входного файла запишите в выходной файл (в отдельной строке) найденное минимальное количество "палочек".
Пример ввода
35 37 53
Пример вывода
14 17 21
