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

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

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

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

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

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

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

Ввод	Вывод
5	16

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

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

Кузнечик и лягушки#27082

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.

На некоторых столбиках сидят лягушки, которые едят кузнечиков (Кузнечик не должен попадать на эти столбики!). Определите, сколькими способами Кузнечик может безопасно добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.

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

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 <= N, K <= 32 . Во второй строке записано число лягушек L ( 0 <= L <= N - 2 ). В третьей строка записано L натуральных чисел: номера столбиков, на которых сидят лягушки (среди них нет столбиков с номерами 1 и N ).

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

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

Примеры

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

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

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

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

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

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

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

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

Примеры

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

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

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

Огромное число#27070

Вася получил длинную последовательность из цифр следующим образом. Он брал подряд натуральные числа, начиная с 1, переводил их в четверичную систему счисления и записывал результаты перевода друг за другом. Вот начало этой последовательности:
123101112132021222330313233100…
Вася остановился только тогда, когда дописал в конец последовательности четверичную запись числа 1023₁₀. Затем он представил, что это одно большое число, записанное в четверичной системе счисления, и перевел его в шестнадцатеричную систему счисления.

Определите, какая шестнадцатеричная цифра стоит в этом числе на a-ой позиции, считая слева направо от начала числа. В ответе укажите эту шестнадцатеричную цифру.

Задача на реализацию Системы счисления

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

Тяжелая, вариант-2#27065

Гриша пишет дипломную работу на тему автостоянок в Берляндии. В ходе дипломной работы ему потребовалось решать следующую задачу.

Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.

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

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

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

В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.

В следующей строке находятся n неотрицательных чисел Xi (Xi < M) — точки, в которых располагаются левые границы машин.

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

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

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

Если не существует машины, которую можно было бы поставить, удовлетворяя все условия, выведите 0.

Пример входных и выходных данных

Ввод	Вывод	Примечание
4 21 1 1 7 12 3 16	1
4 30 3 1 24 5 11 18	1
2 20 3 1 7 10	0	В данном примере машины стоят вплотную, и между ними нельзя поставить никакую машину.

Задача на реализацию Задачи на моделирование

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

Тяжелая, вариант-1#27064

Гриша пишет дипломную работу на тему автостоянок в Берляндии. В ходе дипломной работы ему потребовалось решать следующую задачу.

Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.

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

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

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

В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.

В следующей строке находятся n неотрицательных чисел Xi (Xi < M) — точки, в которых располагаются левые границы машин.

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

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

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

Если не существует машины, которую можно было бы поставить, удовлетворяя все условия, выведите 0.

Пример входных и выходных данных

Ввод	Вывод
4 21 1 1 7 12 3 16	2
4 30 3 1 24 5 11 18	3
2 20 3 1 7 10	5

Задачи на моделирование Использование сортировки реализация

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

Легкая, вариант-2#27063

Сервер одной крупной аналитической компании делает резервное копирование всех данных каждые пол часа. Системный администратор Илья Филиппович Яковлев заступит сегодня на смену в известное время. Он знает, что сервер делает резервное копирование в полночь (00:00:00), но не может посчитать, когда же будет следующее резервное копирование после момента его заступления на смену.

Ваша задача — написать программу, которая определит время следующего резервного копирования после начала смены Ильи Филипповича. Считается, что резервное копирование происходит мгновенно. Таким образом, если Илья Филиппович заступает в момент резервного копирования, считается, что оно происходит уже в его смену.

Формат входного файла

На вход программе подается строка, в которой находится время заступления Ильи Филипповича в формате hh:mm:ss, где hh обозначает часы в 24-часовом формате, mm — минуты, а ss — секунды. Гарантируется, что время корректно.

Формат выходного файла

Требуется вывести время следующего резервного копирования в аналогичном формате.

Пример входных и выходных данных

Ввод	Вывод
12:55:00	13:00:00
00:00:00	00:00:00
18:30:03	19:00:00

Дата и время Задачи на моделирование

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

Легкая, вариант-1#27062

Сервер одной крупной аналитической компании делает резервное копирование всех данных каждые пол часа. Системный администратор Илья Филиппович Яковлев заступит сегодня на смену в известное время. Он знает, что сервер делает резервное копирование в полночь (00:00:00), но не может посчитать, когда же было последнее резервное копирование на момент его заступления на смену.

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

Формат входного файла

На вход программы подается строка, в которой находится время заступления Ильи Филипповича в формате hh:mm:ss, где hh обозначает часы в 24-часовом формате, mm — минуты, а ss — секунды. Гарантируется, что время корректно.

Формат выходного файла

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

Пример входных и выходных данных

Ввод	Вывод
12:55:00	12:30:00
00:00:00	23:30:00
18:30:03	18:30:00

Дата и время Задачи на моделирование

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

Формула - 3#27061

Напишите программу, которая вычисляет значение y.

\(y = \frac a {b \cdot c}\)

Входные данные
На вход подаются 3 целых числа a, b, c (b, с > 0).

Выходные данные
Выведите значение y.

Пример

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

Вещественные числа Вывод формулы

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

Формула - 4#27060

Напишите программу, которая вычисляет значение y.

\(y = 5.45 \cdot \frac {a + 2 \cdot b} {2-a}\)

Входные данные
На вход подается 2 целых числа a (a>2) и b.

Выходные данные
Выведите значение y.

Примеры

№	Входные данные	Выходные данные
1	4 2	-21.80
2	1 2	27.25

Вещественные числа Вывод формулы

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

Формула - 5#27059

Напишите программу, которая вычисляет значение y.

\(y = \frac {a + b} {2}\)

Входные данные
На вход подается 2 целых числа a и b.

Выходные данные
Выведите значение y.

Примеры

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

Вещественные числа Вывод формулы

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

Формула - 6#27058

Напишите программу, которая вычисляет значение y.

\(y = \frac {-1} {x^2}\)

Входные данные
На вход подается целое число x (x > 0).

Выходные данные
Выведите значение y.

Примеры

№	Входные данные	Выходные данные
1	2	-0.25
2	1	-1

Вещественные числа Вывод формулы

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

Вывод переменных - 1#27057

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

Пример

№	Входные данные	Выходные данные
1	5 7 8 9	line 1: 5 7 line 2: 8 9

Ввод, вывод данных Линейные алгоритмы

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

Вывод переменных - 2#27056

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

Пример

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

Ввод, вывод данных Линейные алгоритмы

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

Вывод переменных - 3#27055

Составить программу вывода на экран в столбик двух чисел, вводимых с клавиатуры через пробел. В конце первой строки добавьте фразу endline.

Пример

№	Входные данные	Выходные данные
1	5 7	5 endline 7

Ввод, вывод данных Линейные алгоритмы

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

Вывод переменной - 4#27054

Составить программу вывода на экран числа, вводимого с клавиатуры. Перед выводимым числом должно идти сообщение "It was".

Пример

№	Входные данные	Выходные данные
1	5	It was 5

Ввод, вывод данных Линейные алгоритмы

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

Упорядочите шарики#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лёгкаяВойти и решать

Пираты!#27043

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

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

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

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

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

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

В первой строке записано натуральные числа N и M (1 <= N, M <= 1 000 000) количество строк и столбцов на игровом поле.

Во второй строке записано натуральное число K (1 <= K <= 500) количество пиратских баз.

В следующих K строках записаны пары чисел R_i , C_i (1 <= R_i <= N, 1 <= C_i <= M) координаты пиратских баз (строка, столбец).

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

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

Система оценки

Решения, верно работающие при N, M 6<=500, будут набирать не менее половины баллов.

Ввод	Вывод
10 10 4 2 2 5 3 5 9 8 8	3

Замечание

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

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

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

Двумерный дождь#27041

Игра PitCraft происходит в двумерном мире, который состоит из блоков размером 1 на 1 метр.

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

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

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

В первой строке записано натуральное число N (0 <= N <= 100 000) количество столбцов, задающих ландшафт острова.

Во второй строке записано N натуральных чисел H_i (1 <= Hi <= 10⁹) высоты столбцов.

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

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

Система оценки

Решения, верно работающие при N <= 100, будут набирать не менее половины баллов.

Ввод	Вывод
11 2 5 2 3 6 9 3 1 3 4 6	18

Замечание

Пример соответствует рисунку. Черным цветом обозначен камень, серым вода.

Линейные структуры Префиксные суммы(минимумы, ...)

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

Формальное исполнение алгоритма, заданного на естественном языке или для конкретного исполнителя с заданным набором команд#27036

Цепочки цифр (строки) создаются по следующему правилу:

Первая строка состоит из двух цифр «1».

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

Эта цифра вставляется в начало, в конец и между всеми цифрами предыдущей строки.

Вот первые 4 строки, созданные по этому правилу:

(1) 11

(2) 21212

(3) 32313231323

(4) 43424341434243414342434

Таким образом, было построено еще 5 строк и в результате получена строка, содержащая цифры от 1 до 9 и состоящая из 767 цифр.

Напишите через пробел сначала цифру, стоящую на a позиции от начала, а затем на b позиции от начала. a и b считываются с клавиатуры (записаны в одной строке через пробел, номер позиции от начала отсчитывается с 1).

Задача на реализацию Задачи на моделирование

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