# Problem

In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there were $n$ cities connected by unidirectional roads, with possibly more than one road connecting a city to another one, or even to itself. As a homework assignment for your geography class, you need to calculate the number of paths of length exactly two that were between each pair of cities. However, you’ve been too busy celebrating the Spanish victory in the World Cup, so now you are copying the answers from your friend. You would like to make sure his answers are correct before handing in your homework.

# Input

The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer $n$ $(1 \leqslant n \leqslant 1000)$. The following $n$ lines contain $n$ elements each, with element $j$ of line $i$ being the number of roads from city $i$ to city $j$ (a number between $0$ and $10$, inclusive). After that, there will be $n$ lines. Each will contain $n$ elements, with element $j$ of line $i$ being the answer from your friend for the number of length-$2$ paths from city $i$ to city $j$; it will be an integer between $0$ and $100000$ inclusive.

The test cases will finish with a line containing only the number zero (also preceded by a blank line).

Note: Large input file; use fast I/O routines.

# Output

For each case, your program should output a line. The content of this line should be «YES» if your classmate’s solution to the assignment is right, and «NO» otherwise.

# Tests

 № Input Output 1 3 2 0 1 1 0 3 1 1 0 5 1 2 5 3 1 3 0 43 2 0 1 1 0 3 1 1 0 5 1 2 5 3 2 3 0 40 YES NO 2 5 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 54 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1435 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 4 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1430 YES NO 3 1 2 21 2 40 NO YES 4 9 1 5 7 9 10 6 3 3 6 10 2 0 5 10 4 3 3 5 7 10 4 1 4 0 4 4 2 5 4 0 1 7 0 5 3 2 7 0 6 1 7 5 2 2 2 7 4 0 1 1 8 6 6 3 0 4 9 2 1 8 0 3 7 8 7 7 3 5 0 10 8 2 1 0 5 8 8 8 3 3 1 287 178 173 129 293 196 195 180 134 182 123 203 174 287 214 150 143 144 202 143 163 158 261 150 126 128 148 125 78 153 108 182 137 82 89 109 156 141 157 108 183 149 120 120 105 166 145 166 147 192 199 157 161 147 207 159 98 105 176 141 159 149 81 243 232 270 182 300 197 184 192 201 213 152 128 61 176 142 160 147 1000 YES

# Solution

The problem statement says that element $j$ of line $i$ of the matrix corresponds to the number of unidirectional roads from city $i$ to city $j$. Thus, we have an adjacency matrix of a directed unweighted graph. We need to find the number of paths of fixed length $k = 2$ for each pair of cities and compare them to our friend’s answer from the output. Adjacency matrix $g_{n \times n}$ of a directed unweighted graph contains the number of routes of length $k = 1$  between each pair of vertices. The solution is iterative: adjacency matrix $g$ corresponds to paths of length $k = 1$. Let $g = d_k$. For $k + 1$ we have: $d_{k+1}[i][j] = \sum\limits_{p=1}^n d_k[i][p] \cdot g[p][j]$, i.e. the product of matrices $d_k$ and $g$. Conclusion: to count the routes of fixed length we have to raise the adjacence matrix to the correspondent power.

Testcases are processed one at a time and after each the answer is given. Firstly, two 2D arrays of size $n \times n$ are initialized and entered: one for storing the matrix with the amounts of paths and the other with our friend’s answers. There is a warning about a big input file in the problem statement. Thus we use C style for I/O operations. Secondly, the first matrix is squared and the results are compared to the friend’s answers one by one. Once an error is detected the loop ends and the answer «NO» is displayed. Otherwise the loop reaches its end and «YES» is displayed. It is necessary that both arrays are deleted before processing the next testcase to prevent memory leaks.

# Задача

Вы – профессионал своего дела и планируете ограбить ряд домов вдоль улицы. В каждом доме спрятана определенная сумма денег. Единственное, что мешает Вам грабить – так это то, что соседние дома связаны системой безопасности: будет передан сигнал в полицию, если два соседние дома будут ограблены в один и тот же вечер.

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

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

Первая строка содержит количество домов $n (1 \leqslant n \leqslant 106)$. Вторая строка содержит n целых неотрицательных чисел $a_1, a_2, …, a_n$, где $a_i$ — количество денег, которое может быть вынесено из iго дома.

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

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

# Тесты

 № Входные данные Выходные данные 1 5 6 1 2 10 4 16 2 10 4 1 29 0 14 8 31 12 7 5 85 3 2 1 3 3

# Решение

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

Решение задачи динамическим программированием должно содержать следующее:
Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям, либо к задаче, решаемой элементарно.
Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии. В противном случае вы можете попытаться узнать какой-то известный числовой ряд, вычислив первые несколько значений вручную.

Для решения данной задачи будет использовать метод последовательного вычисления (далее МПВ).
МПВ подходит, только если функция ссылается исключительно на элементы перед ней — это его основной минус.
Суть метода в следующем: необходимо создать массив на N элементов и последовательно заполнять его значениями. Таким образом вычисляется, в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения.

Зная, что такое динамическое программирование и МПВ — можно описать алгоритм решения.
Пусть $a_i$ — количество денег в $i$-ом доме и houseRobbery(i) — максимальное количество денег, которое удалось унести грабителю.

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

Далее в цикле рассматривается $i$-й дом и определять для него $houseRobbery(i)$, где houseRobbery(i) — максимальное из houseRobbery(i - 1) и houseRobbery(i - 2) + initialHouses[i], так как нужно учитывать houseRobbery(i - 1), если $i$-й дом не был ограблен, а houseRobbery(i - 2) + initialHouses[i], если $i$-й дом — ограблен.

И так как используется МПВ, то последний элемент в заведенном массиве и будет решением этой задачи.

# Условие

На доске записано число $1$. Каждую секунду Петя может провести над числом одну из двух операций: либо прибавить к числу $1$, либо произвольным образом переставить цифры числа (но так, чтобы на первом месте оказался не ноль). После этого Петя вытирает с доски старое число и записывает вместо него получившееся.

Задание
Напишите программу, которая для заданного натурального числа определяет, за какое наименьшее число операций Петя может, начав с единицы, дойти до этого числа.

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

Первая строка входного файла содержит число $T (1 \leqslant T < 10^4),$ которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих $T$ строках задано по одному натуральному числу $N_i$,$2\leqslant N_i < 10^9$, $1 \leqslant i \leqslant T$. Известно, что среди чисел $N_i, 1 \leqslant i \leqslant T$, нет одинаковых.

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

Выходной файл должен содержать $T$ чисел по одному в строке — в $i$-й строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число $N_i$.

# Тесты

 № Ввод Вывод 1 3 3 955 21 1 48 12 2 4 137 318 3028 300 39 40 71 50

# Решение

Количество цифр в числе никогда не уменьшается, а может увеличиться только при добавлении к числу, состоящее только из девяток и единицы. Поэтому, для достижения числа $N$ сначала нужно дойти до числа $10$, потом до чисел $99$ и $100$ и так далее, пока количество цифр в числе не будет таким, какое требуется.
Наименьшее количество операций, необходимое для того, чтобы перейти от числа $10^{n-1}$ до заданного $n$ -значного числа $N$ можно посчитать следующим образом:
1. Если число $N$ содержит хотя бы одну цифру, отличную от нуля, кроме первой, то количество операций можно посчитать по формуле summa(N) + nonzero(N) edinica(N) - 1, где summa(N) — сумма цифр числа, nonzero(N) — количество цифр, отличных от нуля, на всех позициях числа $N$, кроме последней, edinica(N) — число, которое равно единице, если хотя бы на одной позиции числа $N$, кроме последней, есть единица, или равна нулю, если единиц на этих позициях нет.
2. Если все цифры числа $N$, кроме первой, нулевые, а первая цифра больше единицы, то количество операций можно посчитать по формуле summa(N-1)+nonzero(N-1) edinica(N-1).

Доказательство формул

Для дальнейшего удобства обозначим перестановку цифр числа через $\Rightarrow$.
Число $N$ -заданное число, число $n$ -количество цифр числа $N$. Если $n=1$, $N=7$, то для того, чтобы дойти от единицы до заданного числа, потребуется $N-1$ операций. В нашем случае $6$ операций
($1+1=2, 2+1=3, 6+1=7$)
Если $n\geq2$, то для этого достаточно привести пример цепочки, подсчитывающая количество операций, которая число $10^{n-1}$ превращает в $N$. Но вместо прямого порядка действий будем делать обратный эквивалентный. $N \Rightarrow 10^{n-1}$. За одну операцию мы можем или уменьшить число на единицу, или переставить в нем цифры так, чтобы на первом месте оказался не нуль. Могут возникнуть следующие случаи:
1. Если $N=10^{n-1}$, то количество операций равно summa(N) + nonzero(N) - edinica(N) - 1 $=$ $0$.
Например, возьмем число $1000$. Сумма цифр $= 1$, количество ненулевых цифр $= 1$, количество единиц $= 1$, соответственно значение $= 1+1-1-1 =0$.

2. Если $N!=10^{n-1}$ и первая цифра числа $N$ равна единице, то проводим следующие операции:
Сначала отнимаем от числа $N$ столько единиц, чтобы последняя цифра стала нулем, далее переставим местами последнюю цифру с какой-нибудь другой, отличной от нуля, кроме первой, и опять отнимем количество единиц, чтобы последняя цифра стала нулевой. Повторять будем до тех пор, пока все цифры, кроме первой, не станут нулями.
Например, возьмем число $137$.
$137-1=136$, $136-1=135$, $135-1=134$, $134-1=133$ ,$133-1=132$ ,$132-1=131$, $131-1=130$ ,$130 \Rightarrow 103$ , $103-1=102$, $102-1=101$, $101-1=100$
Количество операций $= 11$. Проверяем по формуле. summa(137)=11, nonzero(137)=2, edinica(137)=1. Итого получаем $11+2-1-1=11$

3. Если первая цифра числа $N$ больше единицы, но хотя бы на одной позиции числа, кроме последней, есть единица, то проводим следующие операции:
Сначала уменьшаем последнюю цифру, пока она не станет нулем, затем переставляем цифры: поставим на место первой цифры единицу, а первую цифру сделаем последней, а нуль, который стоял в конце числа, поставим на место бывшей первой цифры. После этого будем действовать согласно алгоритму пункта №2.
Например, число $318$.
$318-1=317$, $317-1=316$, $316-1=315$, $315-1=314$, $314-1=313$, $313-1=312$, $312-1=311$, $311-1=310$, $310 \Rightarrow 103$, $103-1=102$, $102-1=101$, $101-1=100$
Итого $12$ операций. Просчитываем по формуле summa(318)+nonzero(318)-edinica(318)-1.
Получаем $12+2-1-1=12$.

4. Если ни на одной из позиций числа $N$, кроме, возможно, последней, нет единиц, но в числе есть хотя бы одна ненулевая цифра, кроме первой, то проводим следующие операции:
Последнюю цифру делаем нулевой, переставляем последний нуль с любой ненулевой цифрой, кроме первой, пока на последнем месте не окажется последняя ненулевая цифра (не считая первую), последнюю ненулевую уменьшаем не до нуля, а до единицы, переставим единицу с первой цифрой, новую последнюю цифру сделаем нулевой.
Например, число $3028$.
$3028-1=3027$, $3027-1=3026$, $3026-1=3025$, $3025-1=3024$, $3024-1=3023$, $3023-1=3022$, $3022-1=3021$, $3021-1=3020$, $3020 \Rightarrow 3002$, $3002-1=3001$, $3001 \Rightarrow 1003$, $1003-1=1002$, $1002-1=1001$, $1001-1=1000$
Получаем $14$ операций. Проверяем по формуле summa(3028)+nonzero(3028)-edinica(3028)-1 $= 13+2-0-1=14$.

5. Если первая цифра числа $N$ больше единицы, а все другие цифры — нулевые, то проводим следующие операции:
Отнимем от числа $N$ единицу, а дальше будем использовать один из раннее написанных алгоритмов в пунктах 2-4.
Например, число $300$.
$300-1=299$, $299-1=298$, $298-1=297$, $297-1=296$, $296-1=295$ $=$ … $291-1=290$, $290 \Rightarrow 209$, $209-1=208$ $=$ … $202-1=201$, $201 \Rightarrow 102$, $102-1=101$, $101-1=100$
Итого $22$ операции. summa(300-1)+nonzero(300-1)-edinica(300-1) $= 20+2-0=22$.

6. Подсчет операций от $1$ до $10^{n-1}$.
Для того, чтобы перейти от числа $10^{n-1}$ к $10^n$, понадобится число $10^n – 1$,которое равно $k$. По предыдущим алгоритмам, понадобится:
summa(k)+ nonzero(k) edinica(k) - 1 $=$ $9 \cdot n + (n-1) -0 -1=10 \cdot n – 2$ операций, где $n > 1$.
Если $n=1$, то количество операций $= 10 \cdot n – 2 =8$.

Количество операций можно посчитать по формуле $(5 \cdot n -1) \cdot (n – 1)$ ,где $n$- количество цифр заданного числа.

# Задача

Дан массив целых чисел. Ваша задача — отсортировать его в порядке неубывания.

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

В первой строке входного файла содержится число $N (1 \leqslant N \leqslant 100000)$ — количество элементов в массиве. Во второй строке находятся N целых чисел, по модулю не превосходящих $10^9$.

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

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

# Тесты

 № Входные данные Выходные данные 1 10 1 8 2 1 4 7 3 2 3 6 1 1 2 2 3 3 4 6 7 8 2 9 7 39 8 1 4 2 65 10 5 1 2 4 5 7 8 10 39 65 3 12 -3 7 -7 -11 40 -30 25 30 2 7 -30 1 -30 -30 -11 -7 -3 1 2 7 7 25 30 40

# Решение

Для решения задачи используем функцию сортировки из библиотеки algorithm. Для начала создаем одномерный массив, потом с помощью цикла записываем значения в массив. С помощью функции sort(), сортируем и записываем изменения в массив. Потом с помощью цикла выводим результат.

# Задача

В натуральном числе $A$ удалили некоторые цифры так, чтобы получить наибольшее натуральное число $B$ с разными цифрами. Какое это число?

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

Натуральное число $x \ (1 \leqslant x \leqslant 10^{100})$.

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

Натуральное число $B$.

# Тесты

 № Входные данные Выходные данные 1 575747 754 2 123231 321 3 314159265359 4192653 4 1092010 9210 5 112221332 213

# Код

Нажмите здесь, чтобы выполнить этот код.

# Решение

По условию, нам предстоит работать с натуральным числом, но для решения задачи более оптимально рассматривать его как строку с одним важным уточнением: ноль не может быть первым символом этой строки. Легко видеть, что в ответе должны фигурировать все цифры из «входных данных» — наибольшим будет число максимально возможного порядка. Следовательно, для каждого разряда числа нам нужна такая цифра, выбор которой не уменьшит разрядность в дальнейшем.

Рассмотрим пример: для числа $121323$ правильным ответом будет $213$.

Ход рассуждений следующий: поскольку в числе содержатся три цифры, ответ также будет трехзначным. Наибольшая цифра в числе — 3, следовательно, она должна быть первой цифрой ответа. Для выполнения этого условия придется «вычеркнуть» все предыдущие цифры, но тогда мы сможем получить лишь двухзначное число $32$. Следующим кандидатом является двойка, и этот выбор нас полностью устраивает, поскольку справа от нее есть остальные цифры «входного» числа. Записав в ответ $2$, рассмотрим число за ней: $1323$. Мы можем видеть, что двойка повторяется, однако в ответе ее быть уже не может по условию задачи. Отбросим ее за ненадобностью и рассмотрим получившееся число $133$. Для полученного числа нам необходимо выполнить те же операции, что и для предыдущего, а значит, мы столкнулись с задачей на динамическое программирование (о чем нам, правда, уже заботливо сообщил e-olymp прямо под условием). Рассуждения аналогичны: взять $3$ мы не можем, поскольку это вынудит нас отбросить $1$, что в результате даст нам число $23$, то есть даже меньшее, чем то, что мы получали в начале. Следовательно, добавляем к ответу $1$. Последнюю оставшуюся цифру можно сразу добавлять к ответу, поскольку сравнивать ее не с чем. Получаем искомый ответ — $213$.

Как и оговаривалось вначале, работать будем со строчным представлением числа. До объявления цикла в строке 22 выполняются подготовительные процедуры: создается множество с целью определения цифр, составляющих число, а затем массив, в который помещаются элементы множества в порядке убывания. В теле цикла проходим по всем элементам массива, пока не находим такой, справа от которого будут все остальные элементы. Здесь важно отметить две вещи: во-первых, меня не интересуют сами цифры, имеет значение лишь их количество в соответствующих множествах; во-вторых, поскольку справа от элемента могут находится ему идентичные, включаем его в срез строки и проверяем, можно ли опустить левую часть числа без ущерба количеству цифр в нем. Если да, то этот элемент добавляется в ответ и извлекается из массива для следующего прохода, а если нет — программа переходит к следующему по старшинству элементу.

# Задача

Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$. Наприклад:

• при $N$ = $7$ кодом буде $504$, бо $7!$ = $5040$;
• при $N$ = $17$ кодом буде $096$, бо $17!$ = $355687428096000$.

За даним натуральним числом $N$ знайти три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$.

# Вхідні дані

Вхідний файл містить єдине ціле число $N$. $(7 \leqslant N \leqslant 1000000000)$.

# Вихідні дані

Вихідний файл має містити рівно три цифри — шуканий код.

# Тесты

 № Входные данные Выходные данные 1 7 504 2 17 096 3 50 512 4 1000000000 144

# Решение

Поскольку процесс расчёта факториала больших чисел занимает много времени, его можно ускорить использованием массива факториалов некоторых чисел. Полное значение факториала не нужно, поэтому массив содержит последние $8$ ненулевых цифр значений факториалов чисел, кратных $10000000$, которые можно получить с помощью следующего кода:

Если на входе — число $N$, меньшее $10000000$, его факториал рассчитывается обычным циклом, попутно отбрасывая ненужные цифры высших разрядов. В конце выводятся искомые последние три цифры факториала числа $N$. Если на входе — число $N$, большее $10000000$, выбирается соответствующее значение из массива по индексу $N/10000000$, и далее с помощью цикла считается произведение оставшихся чисел из $N!$. С уменьшением кратности чисел, факториалы которых содержатся в массиве, увеличивается скорость выполнения программы.

# Задача

Задан массив из $n$ целых чисел. Выведите только его отрицательные элементы, изменив первоначальный порядок на противоположный.

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

Первая строка содержит число $n (1 \leqslant n \leqslant 100)$. Во второй строке записаны $n$ целых чисел, каждое из которых не превышает по модулю $100$.

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

В первой строке выведите количество отрицательных элементов массива. Во второй строке выведите сами отрицательные элементы в обратном порядке. Если отрицательных элементов в массиве нет, то выведите $«NO»$.

# Тесты

 # ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ 1 7 -2 5 4 -3 7 -1 0 3 -1 -3 -2 2 5 2 1 0 1 5 NO 3 3 -1 -2 -3 3 -3 -2 -1

# Решение задачи

Для решения этой задачи, прежде всего, необходимо объявить две целочисленные переменные ― $n$ и $count$. Переменная $n$ считывает первое число в строке ввода, и после объявления некоторого массива arr[n], она становится значением числа его элементов. Переменной $count$ обязательно присваиваем значение $0$, ведь именно она позднее будет отвечать за подсчет отрицательных элементов заданного массива.

С помощью цикла for задаем массив, начиная с нулевого элемента и заканчивая $n$-ым элементом (не включительно!). Внутри цикла размещаем условный оператор if, который прибавляет единицу к переменной count каждый раз, когда элемент массива отрицателен. После окончания цикла важно не забыть о еще одном условном операторе, который будет выводить $«NO»$ и заканчивать работу программы, если значение $count$ равно нулю (то есть именно в том случае, если в массиве не будет ни одного отрицательного элемента). Но если в массиве всё же есть отрицательные элементы, то программа должна продолжить работу, что мы и предусматриваем, выполняя все остальные операции в рамках оператора else. Отлично! Теперь полученное значение переменной $count$ (если оно больше нуля) можно вывести, однако это еще не конец, ведь также необходимо вывести все отрицательные элементы в обратном порядке, так что переходим на новую строку с помощью endl и продолжаем.

Реализация подобной процедуры не так сложна, как кажется. Для этого необходимо создать еще один цикл for, перебирающий массив с конца (то есть от $n-1$ до $0$ включительно). Внутри цикла вновь создаем условный оператор if, который каждый раз выводит элемент массива (с пробелом), если он оказывается отрицательным. Не забываем закрыть скобку оператора else, ведь эта процедура также выполняется внутри условного оператора.

Готово!

# Задача

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

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

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

В первой строке вводятся два числа $n$ и $k$ $(1 \leqslant n \leqslant 10000, 0 \leqslant k \leqslant 20)$, $n$ — количество ступенек на лестнице, $k$ — максимальное количество ступенек, через которые Коля может перепрыгнуть за один прыжок (то есть, например, на первом шаге Коля может прыгнуть на $(k + 1)$-ую или более низкие ступеньки). Во второй строке вводятся $n$ чисел: $i$-ое число указывает на длительность в минутах того мероприятия, которое проведёт культ-орк, стоящий на $i$-ой ступеньке. Каждое мероприятие не может длиться более $24$ часов. Ступеньки нумеруются снизу вверх, ступенькой номер $n$ считается весь этаж столовой.

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

Выведите одно число — минимальное количество минут, которое Коле придётся распланировать.

# Тесты

 № Входные данные Выходные данные 1 5 2 7 3 9 2 11 14 2 6 1 59 32 4 21 5 1 42 3 10 3 40 55 85 29 158 105 115 281 320 10 144 4 15 4 67 20 85 12 345 9 234 115 190 47 5 17 23 89 130 156 5 4 0 100 20 31 49 200

# Решение

Для каждой ступеньки будем считать минимальное время, которое она отнимет у эльфа, учитывая сколько ступенек можно пропустить (от $0$ до $k + 1$). То есть будем прыгать со ступенек пониже (если это возможно) и сравнивать значения на каждой. Под значением подразумевается сумма уже найденного значения на более низкой ступеньке и времени, которое отнимет мероприятие $i$-ой ступеньки. Таким образом мы узнаем, какие ступеньки выгодно перепрыгнуть. $0$-я ступенька займет $0$ минут, так как эльф не потратит время. Изначально за минимум на ступеньках до $k + 1$ включительно можно взять время мероприятия соответствующей ступеньки, для остальных — сумму значения предыдущей ступеньки и времени мероприятия данной ступеньки. В случае, если эти значения не минимальные, они заменятся на подходящие.
Ответом будет значение на последней ступеньке, так как к ней будет проложен путь, который «займет» минимум времени эльфа на развлечения.

# Ссылки

Условие задачи на e-olymp
Код программы на ideone

# Условие

Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает — слишком большой вес рюкзак может просто не выдержать.

Много раз он выкладывал одни вещи и на их место помещал другие, пытаясь как можно выше поднять стоимость взятых драгоценностей.

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

Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $w$. Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i}$ $(i = 1, 2, \ldots, n)$.

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

В первой строке содержится два натуральных числа $w$ и $n$ $(1 \leqslant w \leqslant 250, 1 \leqslant n \leqslant 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_{i}$ и $v_{i}$ $(1 \leqslant w_{i} \leqslant 250, 1 \leqslant v_{i} \leqslant 250)$ — вес предмета типа $i$ и его стоимость.

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

Выведите максимальную стоимость груза, вес которого не превышает $w$.

# Тесты

 № Входные данные Выходные данные 1 10 2 5 10 6 19 20 2 250 35 187 100 28 109 245 142 123 83 237 78 36 172 15 248 90 24 181 137 40 233 8 99 231 128 79 132 43 217 156 104 45 191 130 113 105 225 206 5 26 120 26 119 64 138 23 147 19 202 79 54 149 185 158 79 209 88 110 133 235 209 188 230 15 220 107 164 235 137 60 167 4067 3 35 4 20 4 1 2 10 8 7 6 70

# Решение

Допустим $w = 9$, $n = 2$, первый предмет $w_{1} = 3$, $n_{1} = 4$, а второй предмет $w_{2} = 2$, $n_{2} = 1$. После того как считаем условие в два одномерных или один двумерный массив (как вам удобнее). Создадим одномерный массив в котором его размер будет равен $w$ и первый элемент будет равен 0, а остальные будут равны минус бесконечности или как в нашем случае (в коде) -1, как показано на (рис. 1). И дальше как показано на (рис. 2) начиная с элемента с номером веса предмета мы прибавляем его стоимость к стоимости предыдущей как показано в коде s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];, если прошлый не минус бесконечность. И так же со вторым элементом, когда они пересекаются с первым мы их сравниваем и вписываем в массив, больший. И в самом конце проходим заново массив и выбираем самый больший элемент, где бы он ни был как показано на (рис. 3). И таким образом на последних позициях которые равняются весу, будут записаны самые дорогие комбинации, благодаря записи самых дорогих элементов в ячейки.

Ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp

# Условие

Задан массив из $n$ целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.

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

В первой строке записано натуральное число $n$. В следующей строке записаны $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Выведите элементы обновленного массива.

# Тесты

Ввод Вывод
1 7
6 -3 -7 4 -7 -4 5
-7 -7 6 -3 4 -4 5
2 2
100 -100
-100 100
3 6
-2 -2 7 3 99 -2
-2 -2 -2 7 3 99
4 5
1 1 1 1 1
1 1 1 1 1

# Решение

Вместо обычных массивов будем использовать векторы, чтобы было удобнее добавлять элементы в конец. Минимальный элемент можно найти с помощью простого цикла: если какой-либо элемент вектора меньше min, то min присваивается значение этого элемента, и так пока не найдено наименьшее число. Подсчитаем, сколько раз оно встречается в векторе. Столько же раз его нужно добавить в новый вектор. Наконец, переносим в v2 все оставшиеся элементы, не равные min.

# Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Вывести обновленный массив.

# Тесты

Входные данные Выходные данные
7
3 5 -7 7 5 -9 -4
5 3 7 -7 -9 5 -4
8
-9 81 27 -38 2 6 -56 -21
81 -9 -38 27 6 2 -21 -56
2
25 -76
-76 25
3
55 44 33
44 55 33
1
99
99

# Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

# Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

# Задача

Дано масив з $N$ цілих чисел. Визначте, скільки в цьому масиві різних елементів.

# Вхідні дані

В першому рядку записано число $N$. В наступному рядку записано $N$ цілих чисел. Всі числа за модулем не перевищують $100$.

# Вихідні дані

Кількість різних елементів в масиві.

# Тести

 № Вхідні дані Вихідні дані 1. 7 3 5 -7 7 5 -9 -4 6 2. 5 1 25 59 75 100 5 3. 6 1 2 3 1 2 4 4

# Решение

Ставим отметку числу как будто видим его впервые.
Далее задача пройти по всем предыдущим числам и проверить не встретится ли такое же число.
Если встретится, то отметку снимаем, а пройдя по всем предыдущим числам так и не встретив числа равного текущему, значит «видим его впервые» и отметка поставлена справедливо.
Считаем количество отметок.

# Решение

Сначала, предположим, что все числа разные. Т.е. количество различных чисел равно $n.$ Далее в цикле for отметим читаем числа из потока и отмечаем в векторе vector<bool> a, что число встретилось. Встретив число ранее уже отмеченное уменьшаем счетчик различных чисел.

# Задача

Международный номерной регистрационный знак легкового автомобиля состоит из $A$ арабских цифр и $B$ больших букв латинского алфавита. Будем считать, что для обеспечения уникальности номера разрешено использовать любую последовательность букв и цифр.

Сколько существует различных таких номеров?

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

В единственной строке через пробел $2$ неотрицательных целых числа $B$ и $A$. Оба числа не превышают $26$.

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

Единственное число — ответ к задаче.

# Тесты

Входные данные Выходные данные
1 3 3 17576000
2 2 5 67600000
3 7 1 80318101760
4 1 1 260
5 26 26 615611958020715731079667428840020377600000000000000000000000000

# Решение

Начнем с того, что к условию задачи прилагается картинка, на которой видно, что во всех номерных знаках буквы и цифры не перемешаны между собой произвольно, а имеют свои четко распределенные места, в примере это последовательность, в которой на первой позиции стоит буква, далее три цифры и на последних двух позициях снова буквы. Это важный момент, поскольку если бы действительно было разрешено использовать любую последовательность, возможных комбинаций было бы гораздо больше. Поскольку в латинском алфавите $26$ букв, для выбора буквы на первое место существует $26$ возможных вариантов, на второе тоже $26$, как и на третье, четвертое и т. д. То есть для того чтобы найти все комбинации из букв для $B$ мест, нужно умножить $26$ на $26$ $B$ раз. Точно так же это работает с арабскими цифрами. Их всего $10$, соответственно, умножаем $10$ на $10$ $A$ раз, где $A$ — количество мест в номерном знаке для цифр. Поэтому, чтобы найти количество возможных комбинаций букв и цифр, перемножаем полученные результаты. Отсюда получаем формулу $26^B\cdot 10^A$.

Сложность задачи заключается скорее не в формуле вычисления, а в реализации кода, поскольку большинство значений уже на этапе возведения в степень не помещаются даже в самые большие типы данных. Именно поэтому код состоит не из пяти строк и встроенной операции возведения в степень, а из более сложных операций, подходящих для работы с большими числами. По сути, у нас возникает проблема, связанная с перемножением больших чисел, которые не помещаются в стандартные типы данных С++. Для решения этой проблемы я выбрала модель представления, в которой числа записываются в виде массивов в десятичной системе, и каждая цифра числа является элементом массива. Младший разряд числа находится в нулевом элементе массива, а старший в $n-1$-ом соответственно. Далее была реализована функция «MULT», которая фактически осуществляет алгоритм умножения поэлементно с сохранением остатка от деления на $10$ в соответствующем элементе массива и добавлением частного от деления на $10$ к следующему элементу массива. Следует отметить, что данная функция принимает два числа, записанные в выше указанной модели представления (в виде массивов), и характеристиками этих чисел является пара: сам массив и количество разрядов в числе (размер массивов иными словами). На выходе функция возвращает количество разрядов полученного произведения. Сам же результат умножения сохраняется в виде массива, который является одним из параметров функции. В коде данная функция внесена в цикл для многократного перемножения чисел, то есть для возведения в нужную степень. Домножение на $10^A$ осуществляется в последнем цикле приписыванием A нулей к полученному результату.

# Ссылки

Задача на сайте e-olymp
Код решения на ideone

# Задача

Напишите программу, которая считывает строку и проверяет, содержит ли она действительное число. Действительное число может содержать десятичную точку или показатель степени (начинающийся с $e$ или $E$), или и то и то одновременно. Также число может содержать обыкновенный набор десятичных цифр. Если число содержит десятичную точку, то должна присутствовать хотя бы одна цифра с каждой стороны точки. Перед числом или экспонентой может находиться плюс или минус (или одновременно и там и там) (без пробелов после знака). Экспонентой является целое число (не содержит десятичной запятой). Пробелы могут присутствовать до или после числа, но не внутри него. Обратите внимание, что границ диапазона входных чисел не существует, но для простоты будем предполагать, что входные строки содержат не более $1000$ символов.

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

Первая строка содержит количество тестов $t$. Дальше следует $t$ строк, каждая из которых содержит одно число.

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

Вывести $t$ строк, каждая из которых содержит слово $LEGAL$ или $ILLEGAL$.

## Тесты

 № Входные данные Выходные данные 1. 2 1.5e+2 3. LEGAL ILLEGAL 2. 4 752.45e+24 0.762e. -0.355.6432e LEGAL ILLEGAL ILLEGAL 3. 1 -652.32e+45 LEGAL 4. 3 542.512e+3 123.456E+42 123.456.789 LEGAL LEGAL ILLEGAL

## Решение

Для решения задачи нам понадобится функция idigit() проверки того, является ли символ цифрой. В STL существует одноименная функция, которая выполняет ту же самую задачу, однако для практики, я написал свою. В функции анализа вещественных чисел isreal() нужно указать условия, при которых синтаксис будет нарушен. Т.е. не будут выполнены условия, описанные в задаче. Затем, если в символьном массиве не было замечено ошибок — возвратить trueв основную функцию. Важно то, что в числе не должно по условию быть других символов кроме «e», «E», «.», «+», «-» и цифр. Что касается окаймляющих пробелов, то при вводе строки через cin они игнорируются.

## Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

# Условие

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой платформы до $n$-ой (последней) и список (последовательность) платформ, по которым нужно пройти.

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

Первая строка содержит количество платформ $n (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.

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

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

# Тесты

 № Ввод Вывод 1 4 1 2 3 30 29 4 1 2 3 4 2 2 7 23 16 2 1 2 3 5 0 1 0 1 0 0 3 1 3 5

# Решение

Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:

1. Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
2. Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.

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

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

# Задача

Подсчитайте количество способов, которыми можно получить сумму $n$ бросая игральный кубик один или несколько раз. Каждый бросок дает результат между 1 и 6.

Например, если $n = 3$, то имеется 4 способа:
1 + 1 + 1
1 + 2
2 + 1
3

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

Одно целое число $n$ $(1 \leqslant n \leqslant 10^6)$.

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

Выведите количество способов по модулю $10^9+7$.

# Тесты

 № Входные данные Выходные данные 1 1 1 2 3 4 3 5 16 4 6 32 5 8 123

# Код программы

Первый способ (выполняется быстрее, но использует больше памяти)

Второй способ (использует меньше памяти, но выполняется дольше)

# Решение

Создадим массив на $n+1$ элемент. В который мы сразу запишем количество перестановок для сумм 1,2..,6. Для остальных случаев, когда $n>7$ воспользуемся следующей идеей. Будем вычислять количество перестановок для сумм, начиная с 7 до тех пор, пока не дойдем до заданного нам $n$. Будем делать это по такой формуле $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6}$  . Для первых шести сумм вычисляем по этой же формуле, с учетом, что $0 < i-k \; (1 \leqslant k \leqslant 6)$ и добавляя еще 1 перестановку, так как мы можем получить сумму ( $i$ ), подбросив кубик 1 раз. Рассмотрим для $n=7$. Чтобы получить 7 достаточно подбросить кубик ещё один раз, так как мы знаем количество для $n$ от 1 до 6. Если выпадет 1, то остается $a_{6}$ возможных перестановок, если выпадет 2, то остается  $a_{5}$  и так далее. Затем нам требуется просуммировать, так как кубик может выпасть 6 способами, как было сказано ранее. Соответственно для $n=8$ количество комбинаций увеличится на  $a_{7}$ и уменьшится на  $a_{1}$, так как кубик имеет только 6 граней.

# Ссылки

Условие задачи на e-olymp

Код программы на ideone

# Задача

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|y_{2} — y_{1}|^2$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3|y_{3} -y_{1}|^2$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-й платформы до $n$-й (последней).

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

Первая строка содержит количество платформ $n$ $(2 \leqslant n \leqslant 10^5)$, вторая — $n$ целых чисел, значения которых не превышают по модулю $4000$ — высоты платформ.

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

Выведите единственное целое число — искомую величину энергии.

# Тесты

 № Входные данные Выходные данные 1 4 1 2 3 30 731 2 4 0 1 6 8 40 3 8 1 15 16 23 42 10 84 5 828 4 7 57 54 -55 -34 21 88 -100 55189 5 7 -4000 4000 -4000 4000 -4000 4000 -4000 0

# Решение

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

• прыжок с предыдущей $i — 1$ платформы.
• суперприём, то есть прыжок c $i — 2$ платформы.
• 3-й вид: суперприём с $i — 1$ платформы на $i + 1$ и прыжок назад на $i$.

«Цены» за обычный прыжок и суперприём мы можем найти из формул данных в условии, с 3-м же сложнее — результатом будет сумма «цены» суперприёма $3(y_{i+1} — y_{i-1})^2$ и «цены» прыжка назад $(y_{i} — y_{i+1})^2$.

Для понимания схемы можно рассмотреть в качестве примера второй тест.
Синим обозначен 3-ий тип. Красными цифрами — весь путь.

второй тест

Каждый из 3-х путей даст своё значение энергии, равное сумме «цены» прыжка на $i$-ю платформу и значения в той, из которой герой совершил прыжок. Наименьшей энергией для этой платформы будет минимум из этих трех значений.
На второй платформе $(i = 1)$ в случае суперприёма мы выходим за границы массива и получаем независимое значение, поэтому эффективнее будет в качестве «цены» выбирать максимум из двух других уже найденных значений. Аналогично на последней  $(i = n — 1)$ и 3-м типе прыжка, максимум будет невыгодным и соответственно не будет выбран как минимум в $energy_{i}$.

# Ссылки

Условие задачи на e-olymp
Код программы на ideone

# Задача

Отсортируйте время согласно заданному критерию

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

Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно)

Тесты

 № Входные данные Выходные данные 1 $\begin{matrix} 4 & & \\ 10 &20 &30 \\ 7 &30 &00 \\ 23&59 &59 \\ 13&30 &30 \end{matrix}$ $\begin{matrix} 7 & 30 &00 \\ 10&20 &30 \\ 13&30 &30 \\ 23& 59 & 59 \end{matrix}$ 2 $\begin{matrix} 6\\ 12 &55 &59 \\ 8 &33 &34 \\ 6 &56 &46 \\ 10 &23 &52 \\ 3 &20 &00 \\ 19 &31 &0\\ 10&23&52 \end{matrix}$ $\begin{matrix} 3 &20 &0 \\ 6 &56 &46 \\ 8 &33 &34 \\ 10 &23 &52 \\ 12 &55 &59 \\ 19 &31 &0 \end{matrix}$

## Решение

Создадим 4 массива где мы будем хранить время(отдельно часы, минуты, секунды), а также четвертый в котором мы будем хранить все время в одной удобной для нас единице измерения — секундах. Читаем поток ввода и переводим полученные данные, сравниваем их потом сортируем полученные результаты и выводим ответ.

# Задача

Отсортируйте время согласно заданному критерию.

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

Сначала задано число $n$ $\left(1 \leqslant n \leqslant 100 \right),$ а затем $n$ моментов времени. Каждый момент времени задается $3$ целыми числами — часы (от $0$ до $23$), минуты (от $0$ до $60$), и секунды (от $0$ до $60$).

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

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

# Тесты

 № Входные данные Выходные данные 1 4 10 20 30 7 30 00 23 59 59 13 30 30 7 30 0 10 20 30 13 30 30 23 59 59 2 5 12 40 45 23 56 12 7 45 34 8 23 34 2 56 45 2 56 45 7 45 34 8 23 34 12 40 45 23 56 12 3 3 23 56 45 21 45 54 6 45 23 6 45 23 21 45 54 23 56 45

# Решение задачи (код 1)

Для решения задачи переведём в секунды каждый момент времени и введём их в массив d[i]. Далее, в этом массиве проверяем какой элемент больше if (d[i] > d[j]) и упорядочиваем эти элементы в порядке возрастания используя swap().

# Решение задачи (код 2)

Для решение задачи вторым способом создадим структуру unsortedtime. Каждый элемент в этой структуре будет соответствовать часу, минуте, секунде. После чего создадим оператор > , в котором будем сравнивать моменты времени. В случае необходимости будем менять их местами, используя функцию swap(). В результате выведем с помощью цикла моменты времени, упорядоченные в порядке неубывания.

# Ссылки

• Условие задачи на e-olymp
• Код программы (1) на ideone
• Код программы (2) на ideone

# e-olymp 8688. Количество чисел без 8

### Задача

Напишите программу, которая определяет количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.

Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

### Тесты

 Входные данные Вывод программы 10 9 25833798135522720 4918510377816614 88888888888888 20334926626631