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

Разнообразное питание#37987

Увлекшись машинным обучением, Вася совсем забыл про свои экзамены в университете, завалил их и пошел служить в армию. Однако, и тут ему пригодились его навыки программиста — у работников столовой возникла проблема с тем, что блюда постоянно повторяются, и солдаты начали слишком этому возмущаться. Узнав, что Вася разбирается в программировании, работники попросили его написать программу, которая сделает распределение блюд.
Работники столовой считают, что единственное, что характеризует распределение блюд — их «степень монотонности» — число одинаковых блюд, которые даются в последовательные приемы пищи. То есть, если представить расписание блюд как массив a, то «степень монотонности» будет равна количеству индексов i, таких что a_i = a_{i - 1}. Для начала вас просят найти не само распределение блюд, а хотя бы минимальную возможную «степень монотонности», которую можно было бы получить некоторой перестановкой заданного набора блюд. Помогите армейской столовой!
Входные данные
В первой строке содержится число n — количество блюд, которые должны войти в расписание (1 ≤ n ≤ 100).
В следующей строке содержится n чисел a_i — блюда (1 ≤ a_i ≤ 100). Одинаковые блюда обозначены одинаковыми числами, разные — разными.
Выходные данные
В единственной строке выведите одно число — минимальное возможное значение «степени монотонности».

Ввод	Вывод
5 1 2 3 1 1	0
6 1 1 2 3 1 1	1

Жадный алгоритм Задачи на моделирование

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

Много пирожных#37692

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

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

Формат входных данных
Первая строка входных данных содержит число n - количество видов пирожных на фабрике, 1 <= n <= 10⁵.
Следующие n строк содержат по одному числу ai - количество пирожных i-го вида, 1 <= ai <= 10⁵.
Сумма всех значений ai не превосходит 2 x 10⁹.

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

Ввод	Вывод
3 4 10 7	2 7

Пояснение к примеру. Имеется 3 вида пирожных количеством 4, 10 и 7 штук. Наилучший ответ будет, если взять по 7 пирожных второго и третьего вида.

Жадный алгоритм Использование сортировки

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

Сдача#34764

Определите количество различных способов выплаты сдачи в размере n рублей купюрами 10 рублей и монетами 5, 2 и 1 рубль.

Например, 5 рублей можно выплатить четырьмя различными способами: 5 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1.

Входные данные
На вход программе подается натуральное число n <= 100 — размер сдачи, которую необходимо выплатить.

Выходные данные
Выведите искомое количество способов выплаты.

Примеры

№	Входные данные	Выходные данные
1	2	2
2	5	4

Вложенные циклы Задачи на моделирование Комбинаторика

✓ 2 063✗ 3 164500лёгкаяВойти и решать

Числа Фибоначчи: Мемоизация рекурсии (C++)#33688

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

Примеры

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

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

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

Камни#33133

На столе лежат N камней. За ход игрок может взять:

- 1 или 2 камня, если N делится на 3;

- 1 или 3, если N при делении на 3 дает остаток один;

- 1, 2 или 3, если N при делении на 3 дает остаток два.

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

Входные данные: вводится целое число \(0 < N <= 100\).

Выходные данные: выведите 1 или 2 – номер игрока, который выиграет при правильной игре.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	3	2

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

✓ 821✗ 1 030500лёгкаяВойти и решать

Сложность двоичного поиска#33009

Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?

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

Вводится одно число N

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

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

Ввод	Вывод
5	3

Бинарный поиск Бинарный поиск в массиве

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

Несократимые дроби#31849

Дробь \({m \over n}\) называется правильной несократимой, если \(0 < m < n\) и \(НОД (m, n) = 1\). Найдите количество правильных несократимых дробей со знаменателем n.

Входные данные
В первой строке задается число знаменателей для которых надо найти количество правильных несократимых дробей N (\(N <=100\)). Каждая последующая строка число n (\(n < 10^9\)).

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

Примеры

№	Входные данные	Выходные данные
1	4 23 23456 7 17	22 11712 6 16

Арифметические алгоритмы (Теория чисел)Функция Эйлера

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

Небоскреб#31785

В небоскребе n этажей. Известно, что если уронить стеклянный шарик с этажа номер p, и шарик разобьется, то если уронить шарик с этажа номер p+1, то он тоже разобьется. Также известно, что при броске с последнего этажа шарик всегда разбивается.

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

Определите, какого числа бросков достаточно, чтобы заведомо решить эту задачу.

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

Программа получает на вход количество этажей в небоскребе n.

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

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

Примечание

Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа.

Подсказки

1. Как следует действовать, если шарик был бы только один?

2. Пусть шариков два и мы бросили один шарик с этажа номер k. Как мы будем действовать в зависимости от того, разобьется ли шарик или нет?

3. Пусть f(n) - это минимальное число бросков, за которое можно определить искомый этаж, если бы в небоскребе было n этажей. Выразите f(n) через значения f(a) для меньших значений a.

Примеры

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

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

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

Точки на прямой#28417

Маленький Петя очень любит точки. Недавно мама подарила ему n точек, лежащих на прямой OX. Пете стало интересно, сколькими способами он может выбрать три различные точки так, чтобы расстояние между двумя самыми удаленными из выбранных точек не превышало d.

Обратите внимание, что порядок точек внутри выбранной тройки значения не имеет.

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

Первая строка содержит два целых числа: n и d (1 ≤ n ≤ 10⁵; 1 ≤ d ≤ 10⁹). Следующая строка содержит n целых чисел x1, x2, ..., xn, по модулю не превосходящих 10⁹ — x-координаты точек, подаренных Пете.

Гарантируется, что координаты точек во входных данных строго возрастают.

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

Выведите единственное целое число — количество троек точек, в которых расстояние между двумя самыми удаленными точками не превосходит d.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Ввод	Вывод
4 3 1 2 3 4	4
4 2 -3 -2 -1 0	2
5 19 1 10 20 30 50	1

В первом примере нам подходит любая тройка различных точек.

Во втором примере нам подходят всего 2 тройки: {-3, -2, -1} и {-2, -1, 0}.

В третьем примере нам подходит одна тройка: {1, 10, 20}.

"Два указателя"Комбинаторика

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

Пары точек#28344

На прямой находятся N точек. Требуется подсчитать количество пар индексов (i, j) таких, что i не равно j и |a_i - a_j| <= D.

Формат входных данных
В первой строке находятся два числа N и D (1 <= N <= 10⁵, 1 <= D <= 10⁹). Во второй строке находится N неотрицательных чисел, каждое из котороых не более чем 2*10⁹.

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

"Два указателя"Использование сортировки

✓ 540✗ 2 833600лёгкаяВойти и решать

Квадратный корень и квадратный квадрат#27292

Найдите такое число x, что \(x^2 + \sqrt{x} = C\) , с точностью не менее 6 знаков после точки.

Входные данные
В единственной строке содержится вещественное число \(1 <=C <=10^{10}\).

Выходные данные
Выведите одно число — искомый \(x\).

Примеры

№	Входные данные	Выходные данные
1	2.0000000000	1.000000000
2	18.0000000000	4.000000000

Бинарный поиск значения функции Бинарный поиск по ответу

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

Приближенный двоичный поиск#27279

Реализуйте алгоритм приближенного бинарного поиска.

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

В первой строке входных данных содержатся числа N и K (\(0< N,\ K <100001\)). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию. В третьей строке вводится K чисел второго массива.
Каждое число в обоих массивах по модулю не превосходит \(2 \cdot 10^9\).

Формат выходных данных
Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

Бинарный поиск Бинарный поиск в массиве

✓ 793✗ 2 039600лёгкаяВойти и решать

Кладоискатель#27213

Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера N×M (1 ≤ N, M ≤ 100 , N×M ≤ 100). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).

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

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

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

Первая строка содержит 2 числа N и M, задающие размеры лабиринта. Далее следует описание лабиринта: N строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).

В (N+2)-й строке находится число K (1 ≤ K ≤ NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в x_i-й строке и в y_i-м столбце (1 ≤ x_i ≤ N, 1 ≤ y_i ≤ M). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

Необходимо вывести одно число - искомый номер входа (нумерация начинается с 1). Если до сокровища невозможно добраться, выведите -1.

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	1
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

Алгоритм Флойда Обход в ширину

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

Есть ли цикл?#27212

Дан ориентированный граф. Требуется определить, есть ли в нем цикл.

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

В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите 0, если в заданном графе цикла нет, и 1, если он есть.

Примеры

№	Входные данные	Выходные данные
1	3 0 1 0 0 0 1 0 0 0	0
2	3 0 1 0 0 0 1 1 0 0	1

Алгоритм Флойда Обход в глубину

✓ 814✗ 1 607500лёгкаяВойти и решать

Двоичные строки заданной длины в обратном порядке#27090

По данному числу N выведите все строки длины N из нулей и единиц в обратном лексикографическом порядке.

Входные данные
Задано единственное число N (\(1 <= N <= 10\)).

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

Примеры

№	Входные данные	Выходные данные
1	2	11 10 01 00

Простые задачи на перебор Размещения с повторениями

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

Опасные отходы#27085

При переработке радиоактивных материалов образуются отходы двух типов: А (неопасные) и B (особо опасные). Отходы каждого типа упаковываются в контейнеры, а затем контейнеры складываются в стопки. Стопка считается взрывоопасной, если в ней есть три или больше контейнеров с особо опасными отходами (типа B) расположены рядом. Для заданного количества контейнеров N определите, сколько есть способов составить безопасную стопку.

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

Входная строка содержит натуральное число – количество контейнеров N в стопке (1 <= N <= 35).

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

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

Примеры

№	Входные данные	Выходные данные
1	3	7

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

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

Зоомагазин-2#27084

В зоомагазине нужно расставить в один ряд клетки с кошками и собаками. В ряд помещается N клеток, при этом есть одно ограничение: нельзя ставить подряд три клетки с животными одного вида (иначе они передерутся). Предполагается, что в магазине есть неограниченное количество клеток с кошками и собаками. Определите, сколькими безопасными способами можно расставить N клеток в ряд.

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

Входная строка содержит одно натуральное число – количество клеток в ряду N .

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

Программа должна вывести количество безопасных способов расстановки N клеток в ряд.

Ввод	Вывод
5	16

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

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

Площадь треугольника#27074

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

Шесть чисел – координаты трёх вершин треугольника.

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

Одно число – величина площади треугольника.

Примеры

№	Входные данные	Выходные данные
1	1 1 2 4 3 2	2.50000

Вычислительная геометрия Элементарная геометрия

✓ 660✗ 1 268300лёгкаяВойти и решать

Упорядочите шарики#27053

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

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

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

В устройство может быть одновременно засосано больше одного шарика, при этом при выплевывании шарика первым выплевывается последний засосанный шарик, затем - предпоследний и т.д. (т.е. устройство работает по принципу стека). Шарики выплевываются по одному, т.е. можно выплюнуть только один шарик, остальные оставив внутри устройства (при этом дальше можно как продолжать «выплевывать» шарики в том же или в другом месте, так и засасывать новые шарики).

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

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

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

Во входном файле задано сначала число N — количество шариков (1<= N <= 1000). Далее идет N чисел, задающих номера шариков в порядке слева направо в их текущем расположении (каждое число — от 1 до N, и каждое из чисел встречается в последовательности ровно один раз).

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

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

Комментарии к примерам тестов

1.Можно засосать, например, шарик номер 2 и выплюнуть его между 1-м и 3-м шариком.

2. Можно действовать, например, так. Сначала засосем шарик номер 1, затем – шарик номер 2. Затем переместимся в начало и перед 4-м шариком выплюнем шарик (это будет шарик номер 2). Дальше засосем шарик номер 3, и выплюнем его между шариками 2 и 4. Дальше переместимся в начало и там выплюнем шарик номер 1. Впрочем, это не единственный возможный вариант упорядочения шариков в этом примере.

Примеры

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

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

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

Номер перестановки#27020

Вам даны две строки - S и одна из её перестановок - P. Требуется найти номер строки P среди всех перестановок строки S, отсортированных по убыванию в лексикографическом порядке.

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

На вход подаются две строки - S и P (1 =< |S| <= 9). В строках содержатся только строчные буквы латинского алфавита.

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

Выведите одно число - номер перестановки P.

Ввод	Вывод
abcd dcba	1
abc abc	6

(с) Ахмад Ибрахим

Комбинаторика Перестановки

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