e-olymp 595. Новый Лабиринт Амбера

Условие задачи

Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от [latex]1[/latex] до [latex]N[/latex]. Из ячейки под номером [latex]i[/latex] можно попасть в ячейки под номерами [latex]i+2[/latex] (если [latex]i+2 ≤ N[/latex]) и [latex]i+3[/latex] (если [latex]i+3 ≤ N[/latex]). На каждой ячейке лежит какое-то количество золотых монет [latex]{ k }_{ i }[/latex]. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером [latex]N[/latex]. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером [latex]N[/latex], вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

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

В первой строке входного файла содержится натуральное число [latex]N (2 ≤ N ≤ 100000)[/latex], а во второй [latex]N[/latex] целых чисел, разделенных одним пробелом, [latex]{ k }_{ i }[/latex] – количество монеток, лежащих в ячейке с номером [latex]i[/latex] [latex](0 ≤ i ≤ 1000)[/latex].

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

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

Тесты

Входные данные Выходные данные
1 5
1000 2 3 1 3
6
2 2
1 2
2
3 4
1 3 100 0
3

Решение с использованием цикла

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

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив [latex]dp[/latex] длиной [latex]n+1[/latex] элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего обнуляем значение нулевого элемента массива, поскольку ячейка, соответствующая ему, находится вне лабиринта, и первого, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером [latex]i[/latex] он может попасть или из ячейки с номером [latex]i-2[/latex], или из ячейки с номером [latex]i-3[/latex]. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения [latex]i[/latex]-й ячейки имеет вид [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex], и ответ к задаче хранится в [latex]n[/latex]-й ячейке массива. Дополнительно требуется проводить проверку на выход за границы массива.

Код на ideone.com.

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

e-olymp 1281. Простая задачка Шарика

Задача

Ещё задолго до того, как Шарик нашёл умную книжку, утерянную Печкиным, когда он только начинал свои эксперименты по распиливанию шахматных досок, когда ещё на шахматной доске белые поля были белыми, а чёрные – чёрными, он задал одну из своих первых задачек Матроскину.

«Сколько разных последовательностей длины $n$ можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд«?

Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.

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

Длина последовательности $n (n ≤ 64)$.

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

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

Тесты

Входные данные Выходные данные
1 2
2 4
3 7
4 13

Код задачи

 

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

Для решения задачи воспользуемся рекуррентным соотношением $f(n)=f(n−1)+f(n−2)+f(n−3)$, где $f$ — функция, возвращающая ответ на поставленную задачу. Из условия следует, что для любой последовательности рассматривать следует только три варианта её последних элементов: …Ч, …ЧБ, …ЧББ (где Ч — чёрная клетка, Б — белая), так как в случае, если конец последовательности квадратов содержит только чёрный квадрат, чёрный и белый или чёрный и два белых, то нарушить последовательность могли только предшествующие этим окончаниям, которые имеют длины $1, 2,$ и $3$ соответственно, последовательности. Именно это и влечёт справедливость указанного выше рекуррентного соотношения. Значения $f(n)$ при $n≤3$ можно вычислить вручную и сохранить, а остальные вычислять в цикле с использованием предыдущих, вплоть до получения требуемого.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 263. Три единицы

Задача

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

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

Длина последовательностей $n$ $\left ( 1 \leq n \leq 10^{5} \right ).$

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

Вывести количество искомых последовательностей по модулю $12345.$

Тесты

Входные данные Выходные данные
$1$ $2$
$4$ $0$
$263$ $10159$
$10000$ $8872$

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

Решение

Объявим массив $f,$ в котором будем сохранять значения $f(1), f(2),\dots, f(n).$ Далее читаем входные данные и заносим в соответствующие ячейки массива $f$ значения $f(1), f(2)$ и $f(3).$ Вычисляем значения $f(i)$ по рекуррентной формуле $f(n) = f(n – 1) + f(n – 2) + f(n – 3).$
Эту формулу получили так: сперва обозначили через $f(n)$ количество искомых последовательностей из $0$ и $1$ длины $n.$ Далее мы смотрим, если на первом месте последовательности будет находиться $0,$ то начиная со второго места можно построить $f(n – 1)$ последовательность. Если на первом месте стоит $1,$ то на втором месте возможны оба варианта. Если там стоит $0,$ то на следующих $n – 2 $свободных местах можно построить $f(n – 2)$ последовательности. Если $1,$ то на третьем месте обязательно должен находиться $0$ и начиная с четвертого места можно построить $f(n – 3)$ последовательности.
Вычисления значения $f(i)$ производим по модулю $12345.$ В результате выводим количество искомых последовательностей по модулю.

Ссылки

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

Код решения задачи ideone

e-olymp 1704. Умная черепашка

Задача

Карта, где ходит черепашка
Имеется клетчатое поле размером $m \times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие $30$.

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

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

Тесты

Входные данные Выходные данные
$4$ $3$ $10$
$5$ $5$ $70$
$4$ $8$ $120$
$10$ $10$ $48620$

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

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

Для решения задачи представим, что черепашка уже находится в правом верхнем углу поля. Начинаем движение сверху-вниз справа-налево, т.е возможные ходы черепашки только наоборот(черепашка может ходит вверх и направо). Если черепашка сместилась вниз по карте, т.e. j > 0, то прибавляем ячейке значение верхней, если черепашка сместилась налево, т.e. i < m-1, то прибавляем ячейке значение правой. Эта сумма будет накапливаться и будет равна количеству всех возможных ходов черепашки. Проходя через всю карту, попадем в левую нижнюю ячейку(старт черепашки), эта ячейка и будет содержать число возможных путей к правой верхней точки. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 44. Единицы

Задача


В арифметическом выражении разрешается использовать число [latex]1[/latex], операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число [latex]n[/latex]?

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

Одно число [latex]n[/latex] [latex](1 \leqslant n \leqslant 5000).[/latex]

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

Искомое количество единиц.

Тесты

# Входные данные Выходные данные
1 7 6
2 22 10
3 90 13
4 157 16
5 985 21

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

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

Нам нужно найти минимальное количество [latex]1,[/latex] с помощью которых можно составить заданное число. Если последней операцией будет сложение, то первое слагаемое будет состоять из [latex]f(i)[/latex] единиц, а второе — из [latex]f(n-i).[/latex] Значение [latex]i[/latex] будем выбирать таким, чтобы сумма этих двух слагаемых была минимальной. Если [latex]n[/latex] нацело делится на [latex]i[/latex], то последней операцией будет умножение. Первый множитель будет состоять из [latex]f(i)[/latex] единиц, а второй — [latex]\displaystyle f \left (\frac{n}{i} \right).[/latex] Тогда значение [latex]i[/latex] будем перебирать до [latex]\sqrt{n},[/latex] чтобы сумма этих слагаемых была минимальной. Затем выводим искомое количество единиц на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 595. Новый Лабиринт Амбера

Задача

Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от 1 до N. Из ячейки под номером i можно попасть в ячейки под номерами $i+2$ (если $i+2 ≤ N$) и $i+3$ (если $i+3 ≤ N$). На каждой ячейке лежит какое-то количество золотых монет $k_i$. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером N. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером N, вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

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

В первой строке входного файла содержится натуральное число $N$ $(2 ≤ N ≤ 100000)$, а во второй $N$ целых чисел, разделенных одним пробелом, $k_i$ – количество монеток лежащих в ячейке с номером $i (0 ≤ k_i ≤ 1000)$.

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

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

Тесты

Входные данные Выходные данные
$5$
$1000$ $2$ $3$ $1$ $3$
$6$
$2$
$1$ $2$
$5610$
$4$
$1$ $3$ $100$ $0$
$3$

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

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив $dp$ длиной $n + 1$ элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего значение первого элемента массива делаем отрицательным, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером $i$ он может попасть или из ячейки с номером $i — 2$, или из ячейки с номером $i — 3$. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения $i$-й ячейки имеет вид $dp_i = dp_i + max\{dp_{i — 2}; dp_{i — 3}\}$, и ответ к задаче хранится в $n$-й ячейке массива.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 4018. Черепашка

Задача

В левом верхнем углу прямоугольной таблицы размером $n × m$ находится черепашка. На каждой клетке таблицы разлито некоторое количество кислоты. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

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

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

В первой строке записаны два натуральных числа $n$ и $m$, не превосходящие $1000$ — размеры таблицы. Далее идёт $n$ строк, каждая из которых содержит $m$ чисел, разделённых пробелами — описание таблицы с указанием для каждой клетки содержания кислоты на ней (в миллилитрах).

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

Вывести минимальную возможную стоимость маршрута черепашки.

Тесты

Входные данные Выходные данные
[latex]3 \ 4[/latex] [latex]35[/latex]
[latex]5 \ 9 \ 4 \ 3[/latex]
[latex]3 \ 1 \ 6 \ 9[/latex]
[latex]8 \ 6 \ 8 \ 12[/latex]
[latex]1 \ 1[/latex] [latex]1[/latex]
[latex]1[/latex]
[latex]5 \ 6[/latex] [latex]25[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]4 \ 1[/latex] [latex]103[/latex]
[latex]100[/latex]
[latex]1[/latex]
[latex]1[/latex]
[latex]1[/latex]
[latex]1 \ 5[/latex] [latex]7[/latex]
[latex]1 \ 1 \ 2 \ 2 \ 1[/latex]

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

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

Для начала посчитаем значение для каждой клетки $0$-ой строки и $0$-ого столбца. Далее, для каждой клетки $\left (i, j \right )$, где $i > 0$ и $j > 0$, считаем значение клетки как сумму значения, лежащего в этой клетке и минимум из пути, откуда черепашка могла прийти (т. е. минимум из клетки $\left (i-1, j \right )$ и клетки $\left (i, j-1 \right )$). Ответом будет значение, лежащее в клетке $\left (n-1, m-1 \right ).$
Для считывания данных использовался BufferedReader, а не Scanner, так как Scanner работает дольше и из-за этого проходит не все тесты.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 4000. Обход в глубину

Задача

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

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

В первой строке содержится количество вершин графа $n$ и выделенная вершина $s$ $\left (1 \leq s \leq n \leq 100 \right).$ В следующих n строках записано по n чисел — матрица смежности графа, в котрой цифра «$0$» означает отсутствие ребра между вершинами, а цифра «$1$» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

Выведите искомое количество вершин.

Тесты

Входные данные Выходные данные
3 1
0 0 1
0 0 0
1 0 0
2
4 2
0 1 0 0
1 0 0 1
0 0 0 1
0 1 1 0
4
6 2
0 1 0 0 0 1
1 0 0 0 0 1
0 0 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 0
1 1 0 0 0 0
3
4 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1
5 3
0 1 0 0 1
1 0 1 0 1
0 1 0 1 0
0 0 1 0 1
1 1 0 1 0
5

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

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

Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа, $c$ будет искомым числом.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 3966. An ardent collector of butterflies

Задача взята с сайта e-olymp.com.

Условие

Как известно, Андрей Сергеевич — ярый коллекционер бабочек. Он имеет огромную коллекцию, экспонаты которой собраны со всего мира. Будем считать, что в мире существует 2000000000 видов бабочек.

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

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

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

В первой строке входного файла содержится единственное число N (1N100000) — количество видов бабочек в коллекции Андрея Сергеевича.

В следующей строке через пробел находятся N упорядоченных по возрастанию чисел — номера видов бабочек в коллекции.

Все виды бабочек в коллекции имеют различные номера.

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

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

Выходной файл должен содержать M строчек. Для каждого запроса выведите «YES«, если бабочка с данным номером содержится в коллекции, и «NO» — в противном случае.

Тесты:

Входные данные Выходные данные:
1 7
10 47 50 63 89 90 99
4
84 33 10 82
NO
NO
YES
NO
2 10
1 4 7 11 12 43 44 67 344 355
5
1 2 4 44 45
YES
NO
YES
YES
NO

Код на Java:

Алгоритм:

Вначале считываем необходимые нам значения: размер коллекции len, элементы коллекции (массив arr) и количество проверяемых экспонатов num:

Затем по очереди считываем номера проверяемых экспонатов, ищем их в массиве, используя алгоритм бинарного поиска, и затем сообщаем о наличии или отсутствии экспоната:

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

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com