Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Фермер Джон придумал игру для своих коров.

Она играется на решётке R*C (2 <= R <= 15, 2 <= C <= 15), где каждый квадрат раскрашем красным либо синим цветом. Коровы начинают в левом верхнем углу и двигаются в правый нижний последовательными прыжками. Прыжок является корректным если и только если:

1) Вы прыгаете на квадрат другого цвета

2) Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы сейчас стоите

3) Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором Вы сейчас стоите

Пожалуйста, помогите коровам вычислить количество возможных различных последовательностей корректных прыжков из левого верхнего квадрата в правый нижний.

Формат входных данных

Первая строка содержит два целых числа R и C. Каждая из следующих R строк содержит ровно C символов. Каждый символ или R или B (обозначающих соответтсвенно красный или синий квадрат)

Формат выходных данных

Выведите количество различных способов пропрыгать из левого верхнего угла в правый нижний.

Динамическое программирование: один параметр

—Войти и решать

COW#90402

Беси стоит перед огромным камнем в середине своего любимого поля. На камне - шифровка на древнем языке, алфавит которого состоит только из трёх букв C, O, W. Беси интересно, сколько раз встретилось слово COW в тексте.

Бесси не возражает если другие букв встречаются между C O W. Также Беси считает разными слова, в которых отличается хоть одна буква. Например COW встречается только один раз в слове CWOW, два раза в слове CCOW, и 8 раз в слове CCOOWW.

По заданному тексту шифровки помогите Беси посчитать сколько раз появится слово COW.

Формат входных данных

Первая строка ввода содержит одно целое число N <= 10^5. Вторая строка содержит строку из N символов, каждый их которых либо C, либо O, либо W.

Формат выходных данных

Выведите количество раз, которое COW появляется как подпоследовательность, необязательно непрерывная, во входной строке.

Заметим, что ответ может быть очень большим, поэтому нужно из пользовать 64-битную целую величину (long long в С++ или long в Java).

Динамическое программирование: один параметр

✓ 1✗ 1—Войти и решать

Secret Cow Code#90401

Коровы экспериментируют с секретными кодами, и они изобрели метод для создания строки с бесконечной длиной которая может быть использована для кодирования.

Пусть дана строка \(s\), назовём \(F(s)\) строку \(s\) за которой идёт строка \(s\) "циклически сдвинутая" на один символ вправо (последний символ становится новым первым символом). По заданной строке \(s\), коровы строят свою строку бесконечной длины повторя применение \(F\); каждый шаг удваивает длину текущей строки.

Вам дана начальная строка и индекс \(N\), помогите коровам вычислить символ на позиции \(N\), в этой бесконечной строке.

ФОРМАТ ВВОДА (файл cowcode.in):

Ввод состоит из одной строки, содержащий строку, за которой следует число \(N\). Строка содержит не более 30 больших латинских букв, \(N \leq 10^{18}\).

Заметим, что \(N\) может не поместиться в 32-битное целое, поэтому нужно использовать 64-битное целое (например long long для С/С++).

ФОРМАТ ВЫВОДА (файл cowcode.out):

Выведите \(N\)-ый символ в бесконечной строке построенной по данной. Первый символ имеет \(N=1\).

Динамическое программирование: один параметр

—Войти и решать

Fruit Feast#90346

Беси забралась на кухню Фермера Джона и обнаружила там кучу лимонов и апельсинов там (неограниченное количество и того и другого) и хочет съесть как можно больше .

Максимум сытости Беси равен \(T\) (\(1 \le T \le 5,000,000\)). Поедание апельсина увеличивает её сытость на \(A\), а поедание лимона увеличивает её сытость на \(B\) (\(1 \le A, B \le T\)). Дополнительно, если она хочет, Беси может попить воды не более одного раза, что мгновенно уменьшит её сытость вдвое (с округлением вниз).

Помогите определить Беси максимальную сытость, которую она сможет достичь.

ФОРМАТ ВВОДА(файл feast.in):

Первая и единственная строка содержит три целых числа \(T\), \(A\), and \(B\).

Формат выходных данных:

Одно целое число, представляющее максимальную сытость, которую может достичь Беси.

Динамическое программирование: один параметр

—Войти и решать

Fruit Feast#90339

Помогите определить Беси максимальную сытость, которую она сможет достичь.

ФОРМАТ ВВОДА(файл feast.in):

Первая и единственная строка содержит три целых числа \(T\), \(A\), and \(B\).

Формат выходных данных:

Одно целое число, представляющее максимальную сытость, которую может достичь Беси.

Динамическое программирование: один параметр

—Войти и решать

Pareidolia#90227

Парейдолия – это явление, при котором ваши глаза склонны видеть в изображениях знакомые узоры, которых на самом деле не существует — например, видение лица в облаке. Поскольку фермер Джон постоянно находится рядом с коровами, он часто видит коровьи узоры в повседневных предметах. Например, если он смотрит на строку "bqessiyexbesszieb", глаза фермера Джона игнорируют некоторые буквы и все, что он видит, это «bessiexbessieb» — строка, содержащая два последовательных подстроки, равные "bessie".

Дана строка длиной не более \(2\cdot 10^5\), состоящая только из символов a-z, где каждый символ имеет связанную стоимость удаления, вычислите максимальную количество непрерывных подстрок, равных "bessie", которые вы можете сформировать, удалив ноль или более символов из него, и минимальную общую стоимость символов, которую вам нужно удалить, чтобы сделать это.

ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):

Первая строка содержит строку. Вторая строка содержит стоимость удаления связанную с каждым символом (целое число в диапазоне \([1,1000]\)).

ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):

Максимальное количество вхождений и минимальная стоимость создания этого числа вхождений.

Динамическое программирование: один параметр

—Войти и решать

Balancing a Tree#90178

Фермер Джон изучает эволюцию пород коров. Результат - корневое дерево с \(N\) (\(2\le N\le 10^5\)) вершинами, помеченными \(1\ldots N\), каждая вершина соответствует одной породе коров. Для каждого \(i\in [2,N]\), родитель вершины \(i\) есть вершина \(p_i\) (\(1\le p_i<i\)), это означает, что порода \(i\) эволюционировала из породы \(p_i\). Вершина \(j\) называется предком вершины \(i\), если \(j=p_i\) или \(j\) предок вершины \(p_i\).

Каждая вершина \(i\) в этом дереве ассоциируется с породой, имеющей целое число пятен \(s_i\). Дисбалансом такого дерева называется максимум \(|s_i-s_j|\) по всем парам \((i,j)\) таким, что \(j\) есть предок \(i\).

Фермер Джон не знает точное значение \(s_i\) для каждой породы, но он знает нижнюю и верхнюю границу этих величин. Ваша задача - назначить значения \(s_i \in [l_i,r_i]\) (\(0\le l_i\le r_i\le 10^9\)) каждой вершине так, чтобы минимизировать дисбаланс этого дерева.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(T\) (\(1\le T\le 10\)), количество независимых подтестов в тесте. и целое число \(B\in \{0,1\}\).

Каждый подтест начинается со строки, содержащей \(N\), за которым следуют \(N-1\) целых чисел \(p_2,p_3,\ldots,p_N\).

Каждая из последующих \(N\) строк содержит целые числа \(l_i\) и \(r_i\).

Гарантируется, что сумма \(N\) по всем подтестам не превысит \(10^5\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого подтеста выведите одну или две строки в зависимости от значения \(B\).

Первая строка должна содержать минимальный дисбаланс.

Если \(B=1,\) выведите дополнительную строку с разделёнными одиночными пробелами целыми числами \(s_1,s_2,\ldots, s_N\) содержащими назначения количеств пятен для достижения вышеуказанного дисбаланса. Любое правильное назначение будет принято.

Деревья Динамическое программирование: один параметр реализация

—Войти и решать

Walking Home#90122

Корова Беси идёт с любимого пастбища в амбар.

Пастбище и амбар расположены на решётке \(N \times N\) (\(2 \leq N \leq 50\)), причём пастбище находится в левом верхнем углу, а амбар - в правом нижнем. Беси хочет попасть в амбар как можно быстрее, поэтому она ходит только вниз и вправо. В некоторых ячейках находятся стоги сена, которые Беси должна обходить.

Беси чувствует себя уставшей, поэтому она хочет изменить направление движения не более \(K\) раз (\(1 \leq K \leq 3\)).

Сколько различных путей имеется у Беси из пастбища в амбар? Два пути считаются различными, если Беси идёт через некоторую ячейку в одном пути и не идёт через неё в другом.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Ввод для каждого теста содержит \(T\) подтестов, каждый из которых описывает различную ферму и для каждого из которых нужно выдать правильный ответ, чтобы получить полный балл за тест. Первая строка ввода содержит \(T\) (\(1 \leq T \leq 50\)). Далее описывается каждый из под-тестов.

Каждый из под-тестов начинается со строки, содержащей \(N\) и \(K\).

Каждая из последующих \(N\) строк содержит строку из \(N\) символов. Каждый символ либо \(\texttt{.}\) если ячейка пуста, или \(\texttt{H}\) если в ячейке стог сена. Гарантируется, что левый верхний и правый нижний углы фермы не содержат стоги сена.

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(T\) строк, \(i\)-ая тсрока содержит количество различных путей, которыми может пройти Беси для \(i\)-го подтеста.

Динамическое программирование: один параметр

—Войти и решать

Snakes#90077

У Беси есть сеть ловить змеек, распределённых в \(N\) групп на линии \((1 \leq N \leq 400)\). Беси должна поймать каждую змейку в каждой группе. Каждый раз, когда Беси ловит группу она может переложить змеек в клетку и начать пустой сеткой ловить следующую группу.

Сеть размером \(s\) означает, что Беси может поймать любую группу, которая содержит \(g\) змеек, где \(g \leq s\). Однако каждый раз, когда Беси ловит группу змеек размером \(g\) сетью размером \(s\), она тратит впустую \(s - g\) пространства. Беси может начинать с сети любого размера и Беси может изменять размер своей сети \(K\) раз \((1 \leq K < N)\).

Выведите минимальное количество потерянного пространства, которого может добиться Беси после вылавливания всех групп змеек.

ФОРМАТ ВВОДА (файл snakes.in):

Первая строка содержит \(N\) и \(K\). Вторая строка содержит \(N\) целых чисел \(a_1,\dots,a_N\), где \(a_i\) (\(0 \leq a_i \leq 10^6\)) количество змеек в \(i\)-ой группе.

ФОРМАТ ВЫВОДА (файл snakes.out):

Выведите одно целое число - минимальное количество потерянного пространства после того как Беси выловит всех змеек.

Динамическое программирование: один параметр Динамическое программирование: последовательности

—Войти и решать

Taming the Herd#90005

Однажды утром Фермер Джон проснулся от звуков дробления древесины. Это коровы ломали амбар.

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако с логом некоторые проблемы.

ФД хочет определить, сколько слово зафиксировано. Однако он подозревает, что коровы подделали его лог и всё в чём он уверен, что он начало лог в день слома. Помогите ему определить, для каждого количества сломов какое минимальное количество записей должно быть подделано.

ФОРМАТ ВВОДА (файл taming.in):

Первая строка ввода содержит одно целое число \(N\) (\(1 \leq N \leq 100\)), обозначающее количество дней, с дня когда ФД начал логгирование.

Вторая строка содержит \(N\) целых чисел, разделённых одиночными пробелами. \(i\)-ое число это неотрицательное целое \(a_i\) (не более 100), указывающее что в день \(i\) на счётчике было \(a_i\) если коровы не подделали эту запись в логе.

ФОРМАТ ВЫВОДА (файл taming.out):

Вывод состоит из \(N\) целых чисел, по одному в строке. \(i\)-ое целое число должно содержать минимум из всех возможных последовательностей с \(i\) сломами количества записей, которые несостоятельны в этой последовательности.

Динамическое программирование: один параметр Жадный алгоритм Разбор случаев

—Войти и решать

Problem_648#89972

ЃҐбЁ ЁЈа Ґв ў ЁЈаг.

€Ја зЁ Ґвбп б Ї®б«Ґ¤®ў вҐ«м®бвЁ Ё§ \(N\) Ї®«®¦ЁвҐ«мле жҐ«ле зЁбҐ« (\(2 \leq N \leq 262,144\)), Є ¦¤®Ґ ў ¤Ё Ї §®Ґ \(0 \ldots 40\). ‡ ®¤Ё е®¤ ЃҐбЁ ¬®¦Ґв ‚§пвм ¤ў б®бҐ¤Ёе а ўле зЁб« Ё § ¬ҐЁвм Ёе зЁб«® 1 Ў®«миҐ ( ЇаЁ¬Ґа, ® ¬®¦Ґв § ¬ҐЁвм ¤ўҐ б®бҐ¤ЁҐ 7 ®¤г 8). –Ґ«м ЁЈал - ¬ ЄбЁ¬Ё§Ёа®ў вм § зҐЁҐ б ¬®Ј® Ў®«ми®Ј® зЁб« , Є®в®а®Ґ ® ¬®¦Ґв Ї®«гзЁвм. Џ®¬®ЈЁвҐ Ґ©.

”ЋђЊЂ’ ‚‚Ћ„Ђ (д ©« 262144.in):

ЏҐаў п бва®Є ўў®¤ б®¤Ґа¦Ёв \(N\), б«Ґ¤гойЁҐ \(N\) бва®Є § ¤ ов Ї®б«Ґ¤®ў вҐ«м®бвм Ё§ \(N\) зЁбҐ«, б Є®в®але зЁ Ґвбп ЁЈа .

”ЋђЊЂ’ ‚›‚Ћ„Ђ (д ©« 262144.out):

‚лўҐ¤ЁвҐ ЁЎ®«миҐҐ зЁб«®, Є®в®а®Ґ ЃҐбЁ ¬®¦Ґв бЈҐҐаЁа®ў вм

Џђ€Њ…ђ ‚‚Ћ„Ђ:

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

‚ ЇаЁ¬ҐаҐ ЃҐбЁ б з « б«Ёў Ґв ўв®аго Ё ваҐвмо 1 Ё Ї®«гз Ґв Ї®б«Ґ¤®ў вҐ«м®бвм 1 2 2 , § вҐ¬ б«Ёў Ґв ¤ўҐ ¤ў®©ЄЁ ў 3. ‡ ¬ҐвЁ¬, зв® Ґ ®ЇвЁ¬ «м® б«Ёў вм ЇҐаўлҐ ¤ўҐ Ґ¤ЁЁжл.

Ђўв®а: Mark Chen Bessie likes downloading games to play on her cell phone, even though she does find the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing. The game starts with a sequence of \(N\) positive integers (\(2 \leq N \leq 262,144\)), each in the range \(0 \ldots 40\). In one move, Bessie can take two adjacent numbers with equal values and replace them a single number of value one greater (e.g., she might replace two adjacent 7s with an 8). The goal is to maximize the value of the largest number she can create. Please help Bessie score as highly as possible!

Формат входных данных:

The first line of input contains \(N\), and the next \(N\) lines give the sequence of \(N\) numbers at the start of the game.

Формат выходных данных:

Please output the largest integer Bessie can generate.

Динамическое программирование: один параметр

—Войти и решать

262144#89969

Бесси любит скачивать игры для своего мобильного телефона, хотя ей и кажется, что маленький сенсорный экран довольно неудобен в использовании из-за её больших копыт.

Её особенно заинтересовала игра, в которую она сейчас играет. Игра начинается с последовательности из N положительных целых чисел (2 ≤ N ≤ 262144), каждое из которых находится в диапазоне от 1 до 40. За один ход Бесси может взять два соседних числа с одинаковыми значениями и заменить их на одно число на единицу больше (например, она может заменить две соседние семёрки на восьмёрку). Цель состоит в том, чтобы максимизировать значение наибольшего числа в последовательности в конце игры. Пожалуйста, помогите Бесси набрать как можно больше очков.

Входные данные

Первая строка ввода содержит N, а следующие N строк дают последовательность из N чисел в начале игры.

Выходные данные

Пожалуйста, выведите наибольшее целое число, которое может сгенерировать Бесси.

Примечание
В приведенном здесь примере Бесси сначала объединяет вторую и третью единицы, чтобы получить последовательность 1 2 2, а затем объединяет двойки в тройку. Обратите внимание, что объединение первых двух единиц не является оптимальным.

Динамическое программирование: один параметр

✓ 1✗ 0—Войти и решать

The Cow Run#89893

Фермер Джон забыл заделать дыру в изгороди на своей ферме и его N (1 <= N <= 1,000) коров сбежали и бедокурят. Каждая минута, когда корова находится вне изгороди, она "бедокурит" на 1 доллар. ФД должен посетить каждую корову, чтобы "усмирить" ее и прекратить долларовые потери от нее.
К счастью, коровы находятся вдоль одной прямой на различных растояниях от фермы. ФД знает расстояние P_i (-500,000 <= P_i <= 500,000, P_i != 0) каждой коровы i относительно ворот (позиция 0), из которых он стартует.
ФД двигается на 1 единицу расстояния за минуту и "усмиряет" корову мгновенно. Определите порядок, в котором ФД дожен посещать коров, так чтобы минимизировать свои долларовые потери.
PROBLEM NAME: cowrun
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..N+1: Строка i+1 содержит целое число P_i.
Формат выходных данных
* Строка 1: Минимальная общая стоимость долларовых потерь
Примечание
Оптимальный порядок посещения --2, 3, 7, -12. ФД прибудет в позицию -2 на 2-ой минуте и получит ущерб в два доллара от этой коровы.
Потом он проследует в позицию 3 (расстояние 5), итого ущерб = 2+5=7 долларов от второй коровы.
Затем он потратит 4 минут чтобы добраться до коровы в позиции 7, с общей стоимостью потерь от этой коровы 7+4 = 11 долларов.
Наконец, он потратит 19 минут чтобы перейти в точку -12, и стоимость потерь от этой коровы будет 11 + 19 = 30 долларов.
Общие потери от всех коров будут 2 + 7 + 11 + 30 = 50 долларов.

Динамическое программирование: два параметра Динамическое программирование: один параметр

✓ 1✗ 0—Войти и решать

Bookshelf (Silver)#89858

Когда Фермер Джон не доит коров, собирает сено, выстраивает коров или строит изгороди, он сидит и читает хорошую книгу. С годами он собрал коллекцию из N книг (1 <= N <= 2,000), и хочет построить для них новое множество книжных полок.
Каждая книга I имеет ширину W(i) и высоту H(i). Книги необходимо ставить на полки в определенном порядке; например, первая полка должна содержать книги с номерами от 1 до k для некоторого k. Вторая полка должна содержать книгу k+1 и т.д. Каждая полка имеет общую ширину не более L (1 <= L <=1,000,000,000). Высота полки равна высоте самой высокой книги на этой полке, а высота множества книжных полок равна сумме высот на всех полках, поскольку полки ставятся одна поверх другой.
Помогите ФД вычислить минимально возможную высоту всего множества книжных полок.
PROBLEM NAME: bookshelf
Формат входных данных
* Строка 1: два разделенных пробелом целых числа: N и L.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа : H(i) W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
Формат выходных данных
* Строка 1: Минимально возможная высота множества полок.
Примечание
Всего 3 полки. Первая содержит книгу 1 (высота 5, ширина 7), вторая содержит книги 2..4 (высота 13, ширина 9), третья содержит книгу 5 (высота 3, ширина 8).

Динамическое программирование: один параметр

—Войти и решать

Bookshelf#89856

Когда Фермер Джон не доит коров, собирает сено, выстраивает коров или строит изгороди, он сидит и читает хорошую книгу. С годами он собрал коллекцию из N книг (1 <= N <= 100,000), и хочет построить для них новое множество книжных полок.
Каждая книга I имеет ширину W(i) и высоту H(i). Книги необходимо ставить на полки в определенном порядке; например, первая полка должна содержать книги с номерами от 1 до k для некоторого k. Вторая полка должна содержать книгу k+1 и т.д. Каждая полка имеет общую ширину не более L (1 <= L <=1,000,000,000). Высота полки равна высоте самой высокой книги на этой полке, а высота множества книжных полок равна сумме высот на всех полках, поскольку полки ставятся одна поверх другой.
Помогите ФД вычислить минимально возможную высоту всего множества книжных полок.
PROBLEM NAME: bookshelf
Формат входных данных
* Строка 1: два разделенных пробелом целых числа: N и L.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа : H(i) W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
Формат выходных данных
* Строка 1: Минимально возможная высота множества полок.
Примечание
Всего 3 полки. Первая содержит книгу 1 (высота 5, ширина 7), вторая содержит книги 2..4 (высота 13, ширина 9), третья содержит книгу 5 (высота 3, ширина 8).

Динамическое программирование: один параметр

—Войти и решать

Длина НВП - 1 (24-25)#89299

В текстовом файле записана последовательность, состоящая из n натуральных чисел. Петя собирает самую большую возрастающую подпоследовательность чисел, при этом ему нужно, чтобы все числа в этой подпоследовательности давали одинаковый остаток при делении на 4.

Пример: в последовательности 5 8 13 9 17 12 21 25 можно выбрать:

5 9 17 21 25 или 5 13 17 21 25 (остаток 1 при делении на 4, длина 5)
8 12 (остаток 0 при делении на 4, длина 2)

Максимальная длина = 5.

Напишите программу, которая находит эту максимальную длину.

Формат входных данных

В первой строке число n (1 ≤ n ≤ 20000)
Во второй строке n чисел через пробел

Формат выходных данных

Длина самой большой такой подпоследовательности

Динамическое программирование: один параметр

✓ 0✗ 1—Войти и решать

Кролик и морковки#82076

Кролик Роджер находится в начале числовой прямой (позиция 0) и хочет добраться до позиции N, где лежит гигантская морковка.

Кролик умеет делать только два вида прыжков:
- Короткий прыжок: +1 позиция (тратит 1 единицу энергии)
- Длинный прыжок: +2 позиции (тратит 1 единицу энергии)

Сколько РАЗЛИЧНЫХ способов есть у Роджера добраться до морковки?

Два способа считаются различными, если последовательность прыжков отличается.

ВХОДНЫЕ ДАННЫЕ:
Одно число N (0 ≤ N ≤ 45) - позиция морковки.

ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество различных способов добраться до морковки.

Динамическое программирование: один параметр

✓ 2✗ 4—Войти и решать

Ледяная горка#81116

В Простоквашино построили ледяную горку. Она состоит из N ступенек. На каждой ступеньке написано число — сколько секунд нужно отдохнуть, если встать на неё. Дядя Фёдор стартует перед первой ступенькой и может прыгать на 1 или 2 ступеньки вперёд. Ему нужно добраться до вершины (встать на последнюю ступеньку), потратив минимум времени на отдых.

Входные данные: В первой строке число N (1 ≤ N ≤ 10). Во второй строке N целых чисел от 0 до 100 — время отдыха на каждой ступеньке.

Выходные данные: Минимальное суммарное время отдыха.

Динамическое программирование: один параметр

✓ 163✗ 393800средняяВойти и решать

Подарки под ёлкой#81115

Под ёлкой лежит N подарков в ряд. Известна радость, которую принесёт каждый подарок. По традиции Простоквашино, нельзя брать два соседних подарка — это невежливо. Дядя Фёдор хочет выбрать подарки так, чтобы суммарная радость была максимальной.

Входные данные: В первой строке число N (1 ≤ N ≤ 10). Во второй строке N целых чисел от 1 до 1000 — радость от каждого подарка.

Выходные данные: Максимальная суммарная радость.

Динамическое программирование: один параметр

✓ 195✗ 117600лёгкаяВойти и решать

Летокоины#60945

В деревне Летовецк, где живут мудрые старцы и их ученики, существует древний банк, который хранит богатства в виде ле́токоинов — особых монет, обладающих магической силой. Однако банк установил строгие правила: чтобы снять деньги, нужно использовать только определённые суммы за одну операцию:

за одну операцию можно снять только 1 ле́токоин,
за одну операцию можно снять сумму 6^x, где x - любое натуральное число (можно снять сумму равную 6, 36, 216, и т.д.),
за одну операцию можно снять сумму 9^x, где x - любое натуральное число (можно снять сумму равную 9, 81, 729, ...).

Старец Летовец спросил своих учеников: за какое минимальное количество операций вы сможете снять ровно N ле́токоинов?

Примечание: невозможно повторно вносить снятые деньги в банк!

Формат входных данных
На вход подается целое число N (\(1<=N<=100000\)).

Формат выходных данных
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 летокоинов за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16

Динамическое программирование: один параметр

✓ 7✗ 1401 100средняяВойти и решать