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

Поле для игры#34839

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

На этом поле Петя уже разместил супермаркет, который представляет собой прямоугольник размером C на D клеток (C –– размер по горизонтали, D –– по вертикали), и нижняя левая клетка супермаркета имеет координаты A, B на игровом поле (см. примеры и рисунки). Теперь Пете нужно разместить на том же игровом поле здание биржи. Здание биржи представляет собой прямоугольник размером E на F клеток (E –– по горизонтали, F –– по вертикали). Естественно, что здание биржи должно полностью располагаться на игровом поле и не должно иметь общих клеток с супермаркетом (но может касаться его).

Сколькими способами Петя сможет разместить здание биржи?

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

Вводятся числа N, M, A, B, C, D, E, F, каждое в отдельной строке. Числа удовлетворяют следующим условиям: 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ A ≤ N, 1 ≤ B ≤ M, 1 ≤ A + C - 1 ≤ N, 1 ≤ B + D - 1 ≤ M, 1 ≤ E ≤ N, 1 ≤ F ≤ M.

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

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

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

Примечание

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

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

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

Оптом – дешевле!#34828

В Москве начал работать новый оператор сотовой связи, предоставляющий доступ в интернет посредством технологии 3G. Новый оператор предлагает простые и невысокие
тарифы, в частности, один мегабайт интернет-трафика стоит 1 рубль.

Кроме того, оператор предлагает покупать оптовые пакеты трафика – есть два предложения: купить пакет трафика на A мегабайт за B рублей и купить пакет трафика на C мегабайт за D рублей.

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

Программа получает на вход пять натуральных чисел N, A, B, C, D, записанных в отдельных строках, не превосходящих 500 000 каждое. Гарантируется, что A > B и C > D.
Программа должна вывести одно целое число – минимальную сумму, которую нужно заплатить для приобретения N мегабайт трафика.

Ввод	Вывод	Примечание
35 10 9 20 17	31	Пакет на 10 мегабайт стоит 9 рублей, пакет на 20 мегабайт стоит 17 рублей. Для оплаты 35 мегабайт нужно купить пакет на 10 мегабайт и пакет на 20 мегабайт, а за оставшиеся 5 мегабайт заплатить 5 рублей.
55 30 20 20 16	40	Пакет на 30 мегабайт стоит 20 рублей, пакет на 20 мегабайт стоит 16 рублей. Для оплаты 55 мегабайт нужно купить два пакета на 30 мегабайт, что суммарно будет стоить 40 рублей.

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

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

Дом у озера#34780

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

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

Следующие N строк содержат по M символов – план дома. Символ «.» в этих строках обозначает пустую клетку, символ «H» обозначает» обозначает клетку дома. План дома является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая дому. Следующие N строк по M символов в каждой содержат план озера, в этих строках символ «.» обозначает пустую клетку, символ «W» обозначает клетку, занятую озером. План» обозначает клетку, занятую озером. План озера является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая озеру.

Программа должна вывести одно число – максимальное значение длины общей границы дома и озера, измеряемую в сторонах клетки. При расположении дома рядом с озером его можно передвигать, но нельзя делать повороты и отражения. Вокруг озера есть неограниченное свободное пространство, дом может располагаться с любой стороны от озера.
Числа N и M являются целыми, положительными, не превосходят 15.

Ввод	Вывод	Примечание
5 6 ...... .HHHH. .HHHH. .HHHH. ...... ..WWW. ..WWW. ..WWW. ..WWW. ..WWW.	3	. . . . W W W H H H H W W W H H H H W W W H H H H W W W . . . . W W W
5 7 ...HHH. .H...H. .H.HHH. .H.H... .HHH... ....... ..WWWWW WWW...W W.W...W ..W....	11

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

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

Турнир#34778

В турнире участвуют N команд. Турнир проводится по олимпийской системе (команды играют на вылет, проигравшие команды выбывают из турнира, выигравшие проходят в следующий тур, ничьих не бывает). Число команд в этой задаче будет степенью двойки: N = 2 ^k .

Все команды пронумерованы числами от 1 до N. В первом туре играют команды с номерами 1 и 2, 3 и 4, 5 и 6 и т. д., всего играется N/2 матчей. По результатам этих матчей команды выходят во второй тур. Во втором туре играют победители первой и второй игры первого тура, победители третьей и четвёртой игры первого тура и т. д. Они выходят в третий тур. В третьем туре играют вместе победители первой и второй игры второго тура, победители третьей и четвёртой игры второго тура и т. д.

Вам даны результаты всех матчей. Определите номер команды, которая стала победителем турнира.
В первой строке входных данных записано число N – количество команд, участвовавших в турнире. Оно является степенью двойки и может принимать значения от 2⁰ = 1 до 2¹⁶ = 65536. Следующие N − 1 строк содержат результаты всех сыгранных матчей. Первые N/2 строк из них являются результатами матчей первого тура, затем идёт N/4 строк с результатами второго тура, N/8 строк с результатами третьего тура и т. д.

Результат каждого матча является одним из двух возможных чисел: 1 или 2. Число 1 означает, что в матче выиграла первая команда (номер которой меньше), число 2 означает, что в матче выиграла вторая команда (номер которой больше).
Программа должна вывести одно число – номер победившей в турнире команды.

Ввод	Вывод
8 1 2 2 1 2 1 1	4

Примечание к ответу
Далее нарисована схема турнира для примера из условия. В турнире участвовало 8 команд. Результаты матчей: 1, 2, 2, 1, 2, 1, 1.
В первом туре играли команды 1 и 2, 3 и 4, 5 и 6, 7 и 8. Результаты матчей первого тура: 1, 2, 2, 1, во второй тур вышли команды 1, 4, 6, 7.
Во втором туре играли команды 1 и 4, 6 и 7. Результаты матчей второго тура: 2, 1.
В третий тур вышли команды 4 и 6. В последнем, третьем, туре играют команды 4 и 6, результат матча: 1, поэтому победителем турнира является команда 4.

Задача на реализацию Задачи на моделирование Структуры данных

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

Сдача#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 110✗ 3 188500лёгкаяВойти и решать

Короткая последовательность#33550

Дано целое число N. Рассмотрим последовательность S₁S₂S₃...S_k..., где каждая группа цифр S_k состоит из записанных одно за другим чисел от 1 до k. Например, первые 75 цифр последовательности выглядят так:

112123123412345123456123456712345678123456789123456789101234567891011123456.

Требуется написать программу, которая определит: какая цифра находится на N-ой позиции в построенной последовательности.

Входные данные
Ввод содержит одно число N (0 < N < 32768).

Выходные данные
Выведите цифру, которая стоит на N-ой позиции в последовательности.

Ввод	Вывод
3	2
20	5

Задачи на моделирование Строки

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

Splash Bomb#33297

Имеется клетчатое поле размером NxM. В каждой клетке может лежать либо реактив A, либо B, либо ничего не лежать - 0. За ход можно положить в некоторую клетку реактив A, причем преобразование вещества идет по следующему правилу: 0+A->A, A+A->B, B+A->0. При этом в результате последней реакции происходит взрыв, а в соседние непустые клетки по сторонам света (если они есть), попадает по порции реактива A. Очки за ход = количество взрывов минус 1. Очки за отдельные ходы суммируются. Требуется очистить поле и при этом набрать максимальное количество очков.

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

В первой строке вводятся N и M (1 <= N, M <= 3). Далее идут N строк по M символов из алфавита (0, A, B) - описание поля.

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

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

Комментарий ко второму примеру: за первый ход не произошло ни одного взрыва, очки=0-1=-1; за второй ход произошел один взрыв и поле очистилось, очки=1-1=0; итого очков: 0+(-1)=-1

Ввод	Вывод
1 1 0	0
1 1 A	-1

Динамическое программирование Задачи на моделирование Перебор

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

Удаление чисел#33125

В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.

Выполняется один или несколько шагов по удалению чисел в этом ряду. На

очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.

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

Например, пусть n = 13, k = 2.

- На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.

- На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.

- На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.

- На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.

Таким образом, число 13 будет удалено на третьем шаге.

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

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

Первая строка входных данных содержит целое число n (3 ≤ n ≤ 10¹⁸).

Вторая строка входных данных содержит целое число k (2 ≤ k ≤ 100, k < n).

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

Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.

Ввод	Вывод
13 2	3

Задачи на моделирование Идеи Целые числа

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

вес Деда Мороза#33112

Дед Мороз очень любит раздавать «подарочки» и если он долго их не раздаёт, то начинает грустить и поедать печеньки (не факт, что печеньки не олени). И он начинает толстеть, но когда он дарит хотя бы один подарочек, то возвращается к начальному весу (Т-Т ©Маша). На какой максимальный вес потолстеет Дед Мороз, если на одном отрезке он дарит по 1 подарку на каждый целый индекс, а всего он обойдёт m домов. Даны n отрезков пути для Деда Мороза на его траектории раздачи подарочков и сами отрезки. Также дано количество домов, которое он обойдёт.

Изначальный вес Деда Мороза 227 ± 1 кг.

Ввод	Вывод
3 12 2 6 3 9 3 4	3

(с) Манаев В., Кашукова М., 2018 г.

Задачи на моделирование Отрезки

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

Танец#32980

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

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

На рисунке изображена начальная расстановка для N = 6 танцоров и два следующих шага танца. Расположение подиума отмечено точкой.
Определите, кто будет стоять рядом с танцором номер P через K шагов.

Программа получает на вход три целых числа N, P, K, записанные в отдельных строках. Первое число N – количество танцоров в кругу, N чётное. Второе число P – номер танцора, 1 ≤ P ≤ N. Третье число K – количество сделанных шагов после начала танца, 1 ≤ K. Максимальные значения для N и K <= 10⁹.

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

Ввод	Вывод	Примечание
6 5 2	2 4	Рисунок выше соответствует этому примеру.

Вывод формулы Задачи на моделирование

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

Преобразование дроби#32978

Дана правильная рациональная несократимая дробь a / b. С этой дробью выполняется следующая операция: к числителю и знаменателю дроби прибавляется 1, после чего дробь сокращается. Определите, можно ли при помощи таких операций из дроби a / b получить другую правильную дробь c / d.

Программа получает на вход четыре целых числа a, b, c, d, причём 0 < a < b ≤ 10⁵, 0 < с < d ≤ 10⁵, числа a и b взаимно простые, числа с и d взаимно простые, a / b ≠ c / d.

Программа должна вывести одно натуральное число – сколько описанных операций нужно применить, чтобы из дроби a / b получить дробь с / d. Если это сделать невозможно, программа должна вывести число 0.

Ввод	Вывод	Примечание
1 3 2 3	2	Дана дробь 1 / 3. После первой операции получается дробь 2 / 4, которая сокращается до 1 / 2. После второй операции получается дробь 2 / 3.
2 3 1 3	0	Получить из дроби 2 / 3 дробь 1 / 3 невозможно.

Вывод формулы Задачи на моделирование

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

Лифт в бизнес-центре#32974

Рабочий день закончился, и сотрудники бизнес-центра собрались по домам. Бизнесцентр представляет собой N-этажное здание, этажи пронумерованы от 1 до N снизу вверх. Все сотрудники хотят спуститься на парковку, которая расположена в подвальном помещении на один этаж ниже первого. Бизнес-центр оборудован лифтом, который может перевозить не более K человек одновременно. Лифт перемещается вверх или вниз на один этаж за одну секунду, посадка и высадка пассажиров происходят мгновенно. Изначально лифт расположен на уровне парковки. Известно, сколько людей хотят спуститься на парковку с каждого

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

Первая строка входных данных содержит наибольшее возможное число людей в лифте K, 1 ≤ K ≤ 10⁹

Вторая строка содержит число этажей в бизнес-центре N, 1 ≤ N ≤ 10⁵

Следующие N строк содержат целые неотрицательные числа – число людей, ожидающих лифт на 1, 2, … , N-м этаже соответственно, эти числа не превосходят 10⁹каждое. В здании находится хотя бы один человек.

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

Ввод	Вывод	Примечание
2 3 3 0 1	8	Лифт перевозит 2 человек, в здании 3 этажа. Лифт поднимается на первый этаж за 1 с, забирает 2 человек и за 1 с спускается на парковку, затем лифт поднимается на первый этаж, забирает 1 человека, вместе с ним поднимается на третий этаж, забирает 1 человека и спускается на парковку. Подъём на третий этаж занимает 3 с, спуск – ещё 3 с.

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

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

Часы#32947

Наручные часы на электронных чернилах могут показывать текущее время в нескольких разных формах. Одна из форм - это имитация механических часов со стрелками. Циферблат часов разделен на 12 больших часовых делений, а каждое из них - на 5 малых делений. Угол между малыми делениями на циферблате равен 6. Для экономии энергии перерисовка изображения происходит один раз в минуту, когда необходимо переместить минутную стрелку. Часовая стрелка также движется дискретно, перемещаясь через каждые 12 минут на одно малое деление. Таким образом в 12:35 часовая стрелка будет указывать на 2-е малое деление справа от 12 часов, а минутная будет указывать на 7 часов. Угол между стрелками в этот момент равен 162º. В 12:36 часовая стрелка переместится на 3-е малое деление после 12 часов, а минутная — на следующее малое деление после 7 часов. Угол между стрелками часов при этом не изменится.

Напишите программу, которая вычисляет величину "внутреннего" (меньшего) угла между часовой и минутной стрелкой в заданный момент времени.

Первая строка ввода содержит два целых числа, разделенных одним пробелом — время на часах, часы H и минуты M (\(1 <= H <= 12, 0 <= M <= 59\)).

Вывести одно целое число в диапазоне от 0 до 180 — величину угла между стрелками в градусах.

Примеры

№	Входные данные	Выходные данные
1	12 35	162

Задачи на моделирование Разбор случаев Условный оператор

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

Кинотеатр#31791

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

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

Программа получает на вход два целых числа N и K, 1 ≤ K ≤ N ≤ 10¹⁸, и должна вывести два целых числа в порядке неубывания – количество свободных мест с двух сторон от школьника, который последним занял место в ряду.

Ввод	Вывод	Примечание
10 1	4 5	В зале 10 свободных мест, первый школьник сел посередине, с одной стороны от него 4 места, с другой стороны – 5.
10 2	2 2	Второй вошедший в зал школьник садится посередине группы из 5 свободных мест, с каждой стороны от него остаётся по 2 свободных места.
10 3	1 2	После того, как два школьника сели на места, в зале остались группы свободных мест из 4, 2, 2 мест. Третий школьник садится посередине группы из 4 мест, поэтому с одной стороны от него 1 место, с другой стороны – 2 места.

Вывод формулы Задачи на моделирование

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

Постоянная Капрекара#30772

Возьмем четырехзначное число, в котором не все цифры одинаковы, например, 6264. Расположим цифры сначала в порядке убывания - 6642; затем, переставив их в обратном порядке, получим 2466. Вычтем последнее число из 6642. На следующем шаге с полученной разностью проделаем тоже самое. Через несколько таких действий получится число, переходящее само в себя и называемое постоянной Капрекара. Если разность получается трехзначная, надо в начале добавить ноль.

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

Входные данные: вводится одна строка, в которой записано четырехзначное число.

Выходные данные: выведите в первой строке постоянную Капрекара, во второй – количество шагов для ее получения.

Задачи на моделирование Строки

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

Лифт#30720

Лифт

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

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

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

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

Первая строка входного файла INPUT.TXT содержит последовательность нажатий на кнопки лифта. Символ «1» означает, что была нажата первая кнопка, а символ «2» – что была нажата вторая кнопка. Символы «1» и «2» не разделены пробелами. Количество нажатий от 1 до 100. Гарантируется, что лифт никогда не опускался ниже первого и не поднимался выше последнего этажа.

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

Следует вывести одно число – количество этажей в доме Вилли и Дилли.

Ввод	Вывод
11	3
21212	2
1221221221221	6

Задачи на моделирование Одномерные массивы

—Войти и решать

Trapped in the Haybales#28323

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

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

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

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

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

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

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

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

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

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

Вычислитель#27121

Дана блок-схема алгоритма. Какое целое положительное число w необходимо подать на вход, чтобы после завершения алгоритма получилось значение s ? В ответе укажите целое число. Примечание. Операция mod вычисляет остаток от деления первого аргумента на второй. Операция div вычисляет частное от целочисленного деления первого аргумента на второй.

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

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

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