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

Trapped in the Haybales#27295

Фермер Джон получили груз из N больших стогов сена (1≤N≤100,000), и разметил их в различных положениях вдоль дороги, ведущей к амбару. К несчастью, он полностью забыл, что корова Беси пасётся вдоль дороги и может попасть в ловушку между стогами сена.

Каждый стог j имеет размер S_j и позицию Pj определяющую его положение вдоль дороги. Беси может двигаться вдоль дороги вплоть до позиции стога, но не может пересечь эту позицию. Исключение – если она прошла в этом направлении D единиц расстояния, тогда она набрала достаточно скорости, чтобы протаранить стог любого размера строго меньше чем D. Конечно после этого она может продолжить движение и таранить другие стога.

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

ФОРМАТ ВООДА:

Первая строка ввода содержит N. Каждая из последующих N строк описывает стог, и содержит два целых числа определяющих размер и позицию в диапазоне 1…10⁹. Все позиции различны.

ФОРМАТ ВЫВОДА:

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

Ввод	Вывод
5 8 1 1 4 8 8 7 15 4 20	14

1 200средняяВойти и решать

Малыш и Карлсон#27293

Малыш может съесть банку варенья за А₁ минут, корзину печенья за B₁ минут, выпить бутылку молока за C₁ минут. А Карлсон может сделать это за A₂, B₂, C₂ минут соответственно. Напишите программу, вычисляющую, за какое минимальное время они смогут покончить с завтраком, состоящим из банки варенья, корзины печенья и бутылки молока?

В первой строке входного файла содержится три целых числа, разделенных пробелами – значения параметров A₁, B₁, C₁. Во второй строке входного файла содержится три целых числа, разделенных пробелами – значения параметров A₂, B₂, C₂. Все числа в диапазоне от 1 до 10⁶.

В выходной файл вывести одно число – минимальное время завтрака с точностью 10⁻⁵.

Ввод	Вывод
13 10 14 6 6 7	12.00000

(с) Южно-Уральский открытый командный чемпионат, 2006

Бинарный поиск по ответу Задачи на моделирование

✓ 5✗ 1231 200средняяВойти и решать

Квадратный корень и квадратный квадрат#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лёгкаяВойти и решать

Кубическое уравнение#27291

Даны четыре действительных числа: A, B, C, D. Найдите все корни уравнения Ax³+Bx²+Cx+D=0. Известно, что все корни этого уравнения не превосходят по абсолютной величине 1000. Известно, что любые два корня этого уравнения различаются не менее, чем на 10^-6.

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

Программа получает на вход четыре действительных числа: A, B, C, D. Любые из этих четырех чисел, но не все одновременно, могут быть равны 0.

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

Программа должна вывести от 0 до 3 действительных чисел: корни данного уравнения в порядке возрастания. Кратные корни должны быть выведены только один раз. Значения корней необходимо выводить с точностью до 6 знаков после точки.

Ввод	Вывод
0 0 1000 -1	0.001

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

✓ 30✗ 3381 000средняяВойти и решать

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

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

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

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

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

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

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

Where's Bessie?#27222

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

Картинка, получаемая камерой, может быть описана решёткой из N×N символов, каждый в интервале A…Z, представляющих один из 26 возможных различных цветов. ФД считает наилучшим такой алгоритм распознавания коров: PCL (возможное размещение коровы) - это прямоугольник на решётке (возможно вся решётка) со сторонами параллельными сторонам решётки, не содержащий внутри других PCL и обладающий следующим свойством: внутри этого прямоугольника должны присутствовать ровно два цвета, один формирует непрерывный регион, а другой формирует два или более непрерывных регионов.

Например, такой образ

AAAAA

ABABA

AAABB

есть PCL, поскольку символы A формируют непрерывный регион, символы B форрмируют более одного непрерывного региона. Интерпретация - это корова с цветом A и с пятнами цвета B.

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

По заданному образу камеры ФД определите количество PCL.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, размер решётки (1≤N≤20). Следующие N строк описывают образ, каждая состоит из N символов.

ФОРМАТ ВЫВОДА:

Количество PCL в образе.

Ввод	Вывод
4 ABBC BBBC AABB ABBC	2

Задача на реализацию Обход в глубину Перебор

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

Paired Up#27220

Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить M своих коров (M <= 10⁹, M - чётное) на M/2 пар. Каждую из этих пар он помещает в отдельное стойло, и все пары коров доятся одновременно.

Каждая из коров даёт различное количество молока. Если коровы в паре дают по A и B литров молока, то для дойки этой пары требуется A+B единиц времени.

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

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

Первая строка ввода содержит N (1 <= N <= 100000). Каждая из следующих N строк содержит два целых числа x и y, указывающих, что у ФД есть x коров с производством молока по y (1 <= y <= 10⁹) литров. Сумма всех x-ов есть M- общее количество коров.

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

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

Примеры

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

"Два указателя"Жадный алгоритм

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

Перестановки#27214

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

1. Шестнадцатеричные цифры в записи числа упорядочены по невозрастанию.

2. Если перевести это число в двоичную систему счсиления, то запись будет содержать не менее 5-ти идущих подряд единиц.

3. Любое шестнадцатеричное число, образованное перестановкой цифр этого числа и переведенное в двоичную систему счисления, также будет содержать в двоичной записи не менее 5-ти единиц подряд.

Перебор Системы счисления

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

Кладоискатель#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

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

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

Транспортировка#27126

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. Нато, чтобы довезти кружки от завода-изготовителя до ЛКШ,остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.

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

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

Алгоритм Дейкстры Бинарный поиск по ответу

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

Little Difference#27120

Little Lidia likes playing with numbers. Today she has a positive integer n, and she wants to decompose it to the product of positive integers.

Because Lidia is little, she likes to play with numbers with little difference. So, all numbers in decomposition should differ by at most one. And of course, the product of all numbers in the decomposition must be equal to n. She considers two decompositions the same if and only if they have the same number of integers and there is a permutation that transforms the first one to the second one.
Write a program that finds all decompositions, which little Lidia can play with today.

Input
The only line of the input contains a single integer n (1 ≤ n ≤ 10¹⁸).

Output
In first line output the number of decompositions of n, or −1 if this number is infinite. If number of decompositions is finite, print all of them one per line. In each line first print number ki of elements in decomposition. Then print ki integers in this decomposition in any order. Don’t forget that decompositions which are different only in order of elements are considered the same.

Input	Output
12	3 1 12 3 2 3 2 2 4 3
1	-1

In the second example 1 can be represented as product of any number of ones.

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

1 300средняяВойти и решать

Все возрастающие последовательности длины k из чисел 1..n#27093

По данным числам N и K выведите все возрастающие последовательности длины K из чисел 1..N в лексикографическом порядке.

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

Заданы 2 числа: N и K (1 ≤ K,N ≤ 100). Для всех тестов верно, что число требуемых последовательностей не превышает 5000.

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

Необходимо вывести все возрастающие последовательности длины K из чисел 1..N в лексикографическом порядке. Последовательности выводятся по одной в строке, числа внутри последовательностей разделяются пробелами.

Ввод	Вывод
5 2	1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5

Рекурсивный перебор Сочетания

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

Построить из строки следующую анаграмму#27091

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

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

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

Примеры

№	Входные данные	Выходные данные
1	4 aab aba baa aaa	aba baa aab aaa

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

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

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

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

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

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

Примеры

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

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

✓ 172✗ 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средняяВойти и решать

Кузнечик и лягушки#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

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

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

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

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

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

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

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

Примеры

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

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

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

Тяжелая, вариант-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средняяВойти и решать