Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

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

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

Формула

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

Программа получает на вход одно целое положительное число M, не превосходящее 2×109
, – количество лопастей, которое есть у Дениса.
 
Программа должна вывести два целых числа – количество спиннеров с 3 лопастями и количество спиннеров с 4 лопастями, которые должен произвести Денис. Если у задачи есть
несколько решений, нужно вывести любое из них. Если Денис не может использовать ровно M лопастей для производства спиннеров, программа должна вывести два числа 0.

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

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

Формула

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

Болик также привык считать количество логических выводов, которое он сделал. Так, например, если рассматриваются 11-ое и 31-ое предположение и отбрасывается 11-ое, то Болик совершил один логический вывод. Если, например, 238-ому предположению не хватило пары, то Болик оставляет его для рассмотрения, но, конечно, не считает это действие за логический вывод. Более того, последний вывод Болик проверяет дважды. 
Теперь Болик хочет понять по имеющемуся количеству базовых предположений сколько ему предстоит сделать логических выводов. 
 
Формат ввода
На вход подается натуральное число N (1 ≤   N ≤   10218) — количество базовых предположений. 
 
Формат вывода
Выведите единственное целое число — количество логических выводов. 
 
Пример
Ввод Вывод
3 3

Выбор зала

Формула

Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала. Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом.
Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым, площадь зала должна находиться в пределах от A до B квадратных метров, включительно.
Чтобы разместить на стенах зала плакаты, рассказывающие об успехах школьников на олимпиадах, но при этом не создать ощущения, что успехов слишком мало, периметр зала должен находиться в пределах от C до D метров, включительно.
Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера. Залы с размерами Y × Z и Z × Y считаются одинаковыми. Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом, сколько различных залов удовлетворяют приведенным выше ограничениям. Требуется написать программу, которая по заданным A, B, C и D определяет количество различных залов, площадь которых находится в пределах от A до B, а периметр — от C до D, включительно.

Формат входного файла
Входной файл содержит четыре разделенных пробелами целых числа: A, B, C и D (1<=A<=B<=109 , 4<=C<=D<=109 ).
Формат выходного файла
Выходной файл должен содержать одно число — искомое количество залов.

Ввод:
2 10 4 8
Вывод:
3

Пояснения к примеру
В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2

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

Формула

Как известно, комета Бармалея видна с Земли каждые C лет. Любопытно, что это происходит в годы, кратные C, т.е. C, 2×C, 3×C и т.д. Не каждому суждено увидеть эту комету хотя бы однажды в жизни. Впрочем, находятся счастливые долгожители, заставшие её прилёт даже несколько раз.
Считается, что впервые эту комету увидел и документировал знаменитый средневековый астроном Бармалео Бармалей. В честь него она и получила своё имя. Говорят, за свою долгую жизнь он успел сделать много великих открытий в самых разных областях науки. Однако недавно историки засомневались, правда ли все открытия, которые ему приписываются, Бармалео Бармалей сделал сам. В частности, они заинтересовались, сколько раз за свою жизнь учёный мог видеть комету, названную в его честь.
 
Бармалео Бармалей родился 1 января в год A и умер 31 декабря в год B. Сколько раз за его жизнь комета была видна с Земли? Мы считаем, что он мог видеть комету, даже будучи младенцем или глубоким стариком, т.е. если она прилетала в год A или B.

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

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

Лифт

Условный оператор Формула

Петру необходимо попасть с этажа 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 единицу времени Петр выйдет из лифта.

Кольцевая линия

Формула

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

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

Друзья заметили, что выполняется следующее условие: если загадать некоторую станцию X и выписать для нее два числа: Da — расстояние от станции, на которой живет Андрей, до станции X и Db — расстояние от станции, на которой живет Борис, до станции X, то полученная пара чисел [Da, Db] будет однозначно задавать станцию X.

Например, если n = 4, Андрей живет на станции 1, а Борис живет на станции 2, то станция 1 задается парой [0, 1], станция 2 — парой [1, 0], станция 3 — парой [2, 1] и станция 4 — парой [1, 2].

Их одноклассник Сергей живет в соседнем городе и не знает, на каких станциях живут Андрей и Борис. Чтобы найти друзей, он заинтересовался, сколько существует вариантов пар станций A, B, таких что если Андрей живет на станции A, а Борис — на станции B, то выполняется описанное выше условие.

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

Формат входного файла
Первая строка входного файла содержит одно целое число n (3 ≤ n ≤ 40 000).
Формат выходного файла
Выходной файл должен содержать одно число — искомое количество вариантов.

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

Ввод Вывод
4 8
5 20

Пояснения к примерам
В первом примере подходят следующие варианты:
- Андрей живет на станции 1, а Борис на станции 2;
- Андрей живет на станции 1, а Борис на станции 4;
- Андрей живет на станции 2, а Борис на станции 1;
- Андрей живет на станции 2, а Борис на станции 3;
- Андрей живет на станции 3, а Борис на станции 2;
- Андрей живет на станции 3, а Борис на станции 4;
- Андрей живет на станции 4, а Борис на станции 1;
- Андрей живет на станции 4, а Борис на станции 3.

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

Формула

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

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

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


 

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

Формула

Лёлик решил провести у себя в школе олимпиаду. Для этого ему необходимо закупить много упаковок бумаги. Лёлику очень повезло, потому что один крупный канцелярский магазин объявил две рекламных акции: «купи 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. 
Во втором примере акциями воспользоваться нельзя. 
В третьем примере можно по одному разу воспользоваться каждой из двух акций и на оставшийся рубль купить еще одну упаковку бумаги. 

Выборы в USA

Формула

Выборы президента США проходят по непрямой схеме. Упрощённо схема выглядит так. Сначала выборы проходят по избирательным округам, на этих выборах голосуют избиратели (то есть все граждане, имеющие право голоса). Затем голосование проходит в коллегии выборщиков, на этих выборах каждый избирательный округ представлен одним выборщиком, который голосует за кандидата, победившего на выборах в данном
избирательном округе. Кандидатов в президенты несколько, но реально борьба разворачивается между двумя кандидатами от основных партий, поэтому для победы в выборах кандидату нужно обеспечить строго больше половины голосов в коллегии выборщиков. Но для того, чтобы выборщик проголосовал за данного кандидата, необходимо, чтобы в его избирательном округе этот кандидат также набрал строго больше половины
голосов избирателей. Известны случаи (например, в 2016 году), когда из-за такой непрямой избирательной системы в выборах побеждал кандидат, за которого проголосовало меньше избирателей, чем за другого кандидата, проигравшего выборы. 

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

Программа получает на вход два целых числа N и K (1 ≤ N ≤ 103 , 1 ≤ K ≤ 106 ) и должна вывести одно целое число – искомое количество избирателей.

Ввод Вывод Примечание
5
3
6
Чтобы данный кандидат получил большинство в коллегии
выборщиков, необходимо, чтобы 3 из 5 выборщиков
проголосовали за него, то есть кандидат должен одержать
победу в 3 округах. Каждый округ состоит из 3 избирателей,
поэтому для победы в округе необходимо набрать 2 голоса
в данном округе.