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

Комета Бармалея#32971

Как известно, комета Бармалея видна с Земли каждые C лет. Любопытно, что это происходит в годы, кратные C, т.е. C, 2×C, 3×C и т.д. Не каждому суждено увидеть эту комету хотя бы однажды в жизни. Впрочем, находятся счастливые долгожители, заставшие её прилёт даже несколько раз.

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

Бармалео Бармалей родился 1 января в год A и умер 31 декабря в год B. Сколько раз за его жизнь комета была видна с Земли? Мы считаем, что он мог видеть комету, даже будучи младенцем или глубоким стариком, т.е. если она прилетала в год A или B.

Программа получает на вход три целых числа A, B и C (1 ≤ A ≤ B ≤ 2×10⁹ , 1 ≤ C ≤ 2×10⁹ ) и должна вывести одно целое число – количество раз, которое комета была

видна между годами A и B включительно.

Ввод	Вывод	Примечание
1850 1900 50	2	Комета пролетала около Земли в 1850 и 1900 годах. Бармалео Бармалей застал оба раза.

Вывод формулы

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

Разбиение последовательности#32948

Последовательность натуральных чисел от 1 до `N` нужно разбить на две части от 1 до `K` и от `K+1` до `N` так, чтобы абсолютное значение разности суммы чисел в первой и второй части последовательности было как можно меньше. То есть нужно найти такое `K`, что значение выражения `|\ sum_{i=1}^K\ i\ -\ sum_{i=K+1}^N\ i\ |` минимально. Например, для последовательности чисел от 1 до 4 разбиение будет минимальным для `K=3`, так как `|\ (1+2+3)-(4)\ |\ =\ 2`, что меньше значения разности для `K=1` равного `|\ (1)-(2+3+4)\ |\ =\ 8` и для `K=2` равного `|\ (1+2)-(3+4)\ |\ =\ 4`.

Напишите программу, которая для заданного `N` находит минимальное разбиение.

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^9`).

Вывести одно целое число `K`. Если существует несколько вариантов разбиения, то вывести меньшее из возможных `K`.

Ввод	Вывод
4	3

Вывод формулы Вычисление по заданной формуле

✓ 2✗ 351 300средняяВойти и решать

Лифт#31924

Петру необходимо попасть с этажа A на этаж B. Для вызова лифта на всех этажах офисного здания, кроме первого и последнего, есть две кнопки – для перемещения вниз и перемещения вверх. В тот момент, когда Петр нажал нужную кнопку вызова, лифт находился на этаже C и вез одного пассажира на этаж D. Если лифт проезжает мимо этажа, на котором нажата кнопка вызова, и лифт движется в подходящем направлении, то лифт останавливается, чтобы посадить дополнительного пассажира. Лифт перемещается между соседними этажами за одну единицу времени, также одну единицу времени занимает остановка лифта на этаже для высадки или посадки пассажиров.

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

Первая строка ввода содержит четыре целых числа A, B, C и D, разделенных одним пробелом (1 ≤ A, B, C, D ≤ 20, A≠B, C≠D, A≠C).

Вывести одно целое число – количество единиц времени от момента вызова лифта до момента, когда Петр выйдет из лифта на этаже B.

Ввод	Вывод
3 9 2 5	10
3 9 5 2	13

Примечание:

Пояснение к примеру 1

Лифт за 1 единицу времени доедет до 3-го этажа, остановится на 1 единицу времени, чтобы Петр сел в лифт, затем через 2 единицы времени доедет до 5-го этажа и остановится на 1 единицу времени для высадки предыдущего пассажира, через 4 единицы времени лифт довезет Петра до 9-го этажа, и через 1 единицу времени Петр выйдет из лифта.

Вывод формулы Условный оператор

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

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

Не про спиннеры#31789

Саша совсем не любит спиннеры, поэтому он рисует в тетрадке. Он взял тетрадный лист из N × M клеточек и пронумеровал все клетки различными числами. Теперь ему стало интересно, сколько различных прямоугольников он может вырезать из этого листа бумаги по границам клеточек.

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

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

Ввод	Вывод	Примечание
2 2	9
3 1	6

Вывод формулы

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

Снова спинеры#31788

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

Программа получает на вход одно целое положительное число M, не превосходящее 2×10⁹

, – количество лопастей, которое есть у Дениса.

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

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

Ввод	Вывод	Примечание
10	2 1	10 = 3 × 2 + 4 × 1
1	0 0	Невозможно произвести спиннеры так, чтобы суммарное число лопастей было равно 1.

Вывод формулы

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

Спиннеры#31787

Спиннер – модная игрушка c подшипником в основании, к которому прикреплены лопасти. Афанасий открыл бизнес по производству спиннеров. Он выяснил, что за спиннер, у которого N лопастей, покупатели готовы платить A + B × N рублей, но при этом покупатель не станет покупать спиннер, если его цена будет выше C рублей. Определите максимальное число лопастей спиннера, который согласится приобрести покупатель. Программа получает на вход три числа A, B, C (стоимость основания спиннера, стоимость одной лопасти и максимальная стоимость всего спиннера). Все числа – целые положительные, не превосходящие 2×10⁹ , при этом A ≤ C.

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

Ввод	Вывод	Примечание
20 10 55	3	Спиннер с 3 лопастями будет стоить 50 рублей, а с 4 лопастями – 60 рублей. Максимальная возможная стоимость спиннера – 55 рублей, поэтому максимальное число лопастей равно 3.

Вывод формулы Вычисление по заданной формуле

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

RAID#28422

При хранении данных одна из основных задач – соблюдение баланса между расходами на количество дисков и надёжностью записи. Одним из компромиссных по надёжности и стоимости хранения данных является RAID-3 – избыточный массив независимых дисков с выделенным диском для хранения блоков чётности. Наш RAID-3 состоит из пяти дисков, на четырёх из которых содержится информация, а на пятом – блоки контрольных битов чётности. При записи четырёх байтов (по байту на каждый из четырёх дисков) вычисляется контрольный байт четности, составленный из контрольных битов. Для каждого из восьми разрядов вычисляется сумма значений битов в этих разрядах во всех байтах данных, при этом значение контрольного бита выбирается так, чтобы сумма значений во всех разрядах (включая контрольный) была чётной. Например, у нас есть два основных диска и на них записывается байты 10010010 и 01110111. Тогда значение контрольного байта равно 11100101 – в каждом разряде сумма получается чётной.

Один из четырёх основных дисков в RAID-3 вышел из строя. Известны значения байтов в трёх оставшихся дисках и значение байта на контрольном диске. Какой байт был записан на сломавшемся диске? Все числа приведены в десятичной системе счисления.

– значения на первых трех дисках: 177, 177, 177, контрольный байт: 177;

– значения на первых трех дисках: 79, 79, 79, контрольный байт: 0;

– значения на первых трех дисках: 46, 56, 248, контрольный байт: 90;

– значения на первых трех дисках: 255, 0, 150, контрольный байт 96;

– значения на первых трех дисках: 137, 232, 23, контрольный байт 212.

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

пробелом.

Битовые операции Вывод формулы

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

Уравнение#27304

Курбат Егоров очень любит математику, особенно уравнения. Он решает их все свободное время. Но он не любит решать уравнеия, которые он не может решить, ибо это пустая трата времени, поэтому Курбат попросил Вас написать программу, которая будет определять, может ли он решить это уравнение. Курбат, как победитель всероса по информатике, разумеется, может написать эту программу сам, но у него совершенно нет на это времени - ему же нужно решать уравнения!

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

На вход подается одна строка без пробелов и знаков переноса строки.

В ней могут содержаться такие символы:

x - переменная, относительно которой Курбат должен решить

уравнение. Может стоять где угодно.

+-*/= - соответствующие знаки арифметических операций. НЕ могут стоять в начале уравнения. Могут стоять после икса или констант.

^ - возведение в степень. Может стоять только после икса. После может стоять только константа.

Числа от -10^1000 до 10^1000 - константы. Могут стоять после иксов,

знаков арифметических операций и знака возведения в степень.

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

Если курбат может решить уравнение, то выведите "Yes", иначе выведите "No".

Ввод	Вывод
10x+x=7	Yes

(с) Григорьев Е., 2017

Вывод формулы

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

Bovine Genomics №2#27221

У Фермера Джона есть N коров с пятнами и N коров без пятен. Как генетик, ФД уверен, что пятна на его коровах вызваны мутацией коровьего генома.

За большие деньги ФД выписал геномы своих коров. Каждый геном - это строка длины M, состоящая из четырёх символов A, C, G, T. Когда он выписал геномы всех коров, он получил таблицу, представленную ниже для N=3:

Позиция: 1 2 3 4 5 6 7 ... M

Пятнистая корова 1: A A T C C C A ... T

Пятнистая корова 2: G A T T G C A ... A

Пятнистая корова 3: G G T C G C A ... A

Корова без пятен 1: A C T C C C A ... G

Корова без пятен 2: A G T T G C A ... T

Корова без пятен 3: A G T T C C A ... T

Посмотрев внимательно на эту таблицу он предположил, что позиции 2 и 4 могут отвечать за пятнистость. Поскольку, глядя на символы в этих позициях, ФД может предсказать, какая из его коров пятнистая, а какая - нет (например, если он видит G и С - значит, корова не пятнистая).

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

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

Первая строка ввода содержит NN (1≤N≤500) и MM (3≤M≤50). Каждая из следующих N строк содержит по M символов. Это описание геномов пятнистых коров. Следующие N строк описывают геномы коров без пятен.

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

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

Ввод	Вывод
3 8 AATCCCAT GATTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT	22

Вывод формулы Перебор

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

Intelligence in Perpendicularia#27118

There are only two directions in Perpendicularia: vertical and horizontal. Perpendicularia government are going to build a new secret service facility. They have some proposed facility plans and want to calculate total secured perimeter for each of them.
The total secured perimeter is calculated as the total length of the facility walls invisible for the perpendicularly-looking outside observer. The figure below shows one of the proposed plans and corresponding secured perimeter.

Write a program that calculates the total secured perimeter for the given plan of the secret service facility.

Input
The plan of the secret service facility is specified as a polygon. The first line of the input contains one integer n — the number of vertices of the polygon (4 ≤ n ≤ 1000). Each of the following n lines contains two integers xi and yi – the coordinates of the i-th vertex (−10⁶ ≤ x_i , y_i ≤ 10⁶ ). Vertices are listed in the consecutive order. All polygon vertices are distinct and none of them lie at the polygon’s edge. All polygon edges are either vertical (x_i = x_i+1) or horizontal (y_i = y_i+1) and none of them intersect each other.

Output
Output a single integer — the total secured perimeter of the secret service facility.

Input	Output
10 1 1 6 1 6 4 3 4 3 3 5 3 5 2 2 2 2 3 1 3	6

Вывод формулы

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

Auxiliary Project#27115

Anna has just finished her course project. She has a lot of seven-segment LED displays as leftovers and a small power source. Each display consumes power proportionally to the number of lit segments, e.g. ‘9’ consumes twice more power than ‘7’.

Anna wonders what is the maximum possible sum of digits she is able to achieve, if her power source is able to light n segments, and she wants to light exactly n segments.
Input
The single line of the input contains one integer n — the number of segments that should be lit (2 ≤ n ≤ 10⁶ ).
Output
Output a single integer — the maximum possible sum of digits that can be displayed simultaneously.

Input	Output
4	4
7	11
6	14

In the first example, a single ‘4’ should be displayed (‘7’ has greater value, but has only three segments). In the second example ‘4’ and ‘7’ should be displayed, in the third one — two ‘7’s.

Вывод формулы Разбор случаев

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

Формула - 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лёгкаяВойти и решать

Время полета#27040

При полутах на самолетах в качестве времени вылета и прилета используется местное время аэропортов вылета и прилета.

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

Например, Москва расположена в часовом поясе UTC+3, а Новосибирск в часовом поясе UTC+7. Если вылететь из Москвы рейсом в 11:15 и временем полјта ровно в 4 часа, то прилет будет в Новосибирск будет в 19:15 (4 часа полёта и 4 часа разницы во времени).

Например, Москва расположена в часовом поясе UTC+3, а Новосибирск в часовом поясе UTC+7. Если вылететь из Москвы рейсом в 11:15 и временем полјта ровно в 4 часа, то прилјт будет в Новосибирск будет в 19:15 (4 часа полёта и 4 часа разницы во времени).

Часовые пояса могут изменяться от UTC-11 (Американское Самоа) до UTC+14 (острова Лайн, Кирибати).

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

пути.

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

В первой строке записаны целые числа H_D, M_D (0 <= H_D <= 23, 0 <= M_D <= 59) время вылета.

Во второй строке записаны целые числа H_F , M_F (0 <= H_F <= 10⁹, 0 <= M_F <= 59) время полёта.

В третьей строке записаны целые числа D, A (-11 6 D, A <= 14) часовые пояса аэропорта вылета и прилёта.

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

Выведите три числа H_A;M_A; Days время прилёта в часах и минутах, а также разницу в датах между датой вылета и датой прилёта.

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

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

Ввод	Вывод
11 15 4 0 3 7	19 15 0
12 0 1 0 -10 13	12 0 1

Замечание

Первый тест соответствуте разобранному в условии примеру с Москвой и Новосибирском.

Второй тест соответствует, например, часовому перелету из Американского Самоа на Самоа.

Самолет вылетает в 12:00, летит в течение часа и приземляется в 12:00 местного времени. Т.к. он пересёк линию перемены даты, то на Самоа уже наступил следующий день.

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

Вывод формулы

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

Дилемма Кубратова#27027

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

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

В единственной строке выходных данных содержится целое число M (-2^63 <= M < 2^63)

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

Выведите число, равное модулю числа M.

Пример:

Ввод	Вывод
5	5
-7	7

P.S. Задача была проверена неоднократно. Все тесты верные. Ошибок быть не может.

P.P.S Все имена вымышлены, все совпадения с реальными людьми случайны.

(c) Ярослав Свиридов и Владимир Линд

Вывод формулы

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

Бумага для олимпиады#26980

Лёлик решил провести у себя в школе олимпиаду. Для этого ему необходимо закупить много упаковок бумаги. Лёлику очень повезло, потому что один крупный канцелярский магазин объявил две рекламных акции: «купи A одинаковых товаров и получи еще один товар бесплатно», а также «купи B товаров по цене B-1 товара».

Лёлик узнал, что одна пачка бумаги в этом магазине стоит n рублей. Теперь он хочет определить сколько упаковок бумаги он сможет купить на p рублей. Помогите ему.

Формат ввода

На вход подаются четыре натуральных числа, разделенных пробелом: A, B, p и n (1 ≤ A ≤ 100, 2 ≤ B ≤ 100, 1 ≤ p, n ≤ 10000).

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

Выведите единственное целое число — максимальное количество упаковок бумаги, которое сможет купить Лёлик.

Пример

Ввод	Вывод
4 4 13 2	8
3 4 8 3	2
3 4 7 1	9

Примечания

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

Во втором примере акциями воспользоваться нельзя.

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

Вывод формулы

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

Логические выводы#26979

Болик решает логическую задачу. Для ее решения, он сначала сделал N базовых предположений. После этого происходит следующий процесс: Холмс разбивает все предположения на пары, из каждой пары отбрасывает наименее вероятное предположение (предположения таковы, что всегда есть наименее вероятное). Если получилось так, что какому-то предположению, пары не хватило, то Болик оставляет его для рассмотрения. Алгоритм повторяется пока у Болика не останется последнее предположение.

Болик также привык считать количество логических выводов, которое он сделал. Так, например, если рассматриваются 11-ое и 31-ое предположение и отбрасывается 11-ое, то Болик совершил один логический вывод. Если, например, 238-ому предположению не хватило пары, то Болик оставляет его для рассмотрения, но, конечно, не считает это действие за логический вывод. Более того, последний вывод Болик проверяет дважды.

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

Формат ввода

На вход подается натуральное число N (1 ≤ N ≤ 10²¹⁸) — количество базовых предположений.

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

Выведите единственное целое число — количество логических выводов.

Пример

Ввод	Вывод
3	3

Вывод формулы

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