Подошел к концу третий день, который выдался очень успешным из- за хорошо подобранных задач (Спасибо за это Аслану) и хорошему настрою наших участников школы.
Начнем снова публиковать задачи и разбирать.
Задача А. Робот профессора GukiZ. Ограничение по времени: 0.5 с
Профессор GukiZ собрал нового робота. Робот находится в точке с координатами (x1, y1) и должен попасть в точку (x2, y2). За один шаг робот может изменить (уменьшить или увеличить) любую из своих координат (возможно обе) на единицу. Таким образом, у робота имеется 8 возможных ходов. Определите наименьшее количество шагов за которое робот сможет попасть в точку назначения.
Входные данные
В первой строке находится пара целых чисел x1, y1 ( - 109 ≤ x1, y1 ≤ 109) — исходное положение робота.
Во второй строке находится пара целых чисел x2, y2 ( - 109 ≤ x2, y2 ≤ 109) — конечное положение робота.
Выходные данные
Выведите целое число d — наименьшее количество ходов, необходимое роботу, чтобы попасть в точку назначения.
входные данные
0 0
4 5
выходные данные
5
входные данные
3 4
6 1
выходные данные
3
Разбор:
Представим, что это точки левого верхнего и нижнего правого углов прямоугольника. Тогда выгоднее дойти по диагонали квадрата (сторона равна меньшей стороне прямоугольника), а потом по оставшейся части прямоугольника. Выходит, что ответ в задаче равен max(|x1 - x2|, |y1 - y2|).
Возможные ошибки: использовать long long (long, int64)
Тема: математика
Сложность времени: O (1).
Задача B. Компот. Ограничение по времени: 1 с
У Николая есть a лимонов, b яблок и c груш. Он решил приготовить из них компот. По рецепту фрукты должны быть в соотношении 1: 2: 4, то есть на каждый лимон в компоте должно быть ровно 2 яблока и ровно 4 груши. При этом фрукты нельзя измельчать, ломать или разрезать, поэтому в компот обязательно должны попасть целиком фрукты — лимоны, яблоки и груши.
Перед вами стоит задача определить максимальное суммарное количество лимонов, яблок и груш, из которых можно сварить компот по рецепту. Возможна ситуация, когда Николай не сможет для приготовления компота использовать ни одного фрукта, в таком случае выведите 0.
Входные данные
В первой строке следует целое положительное число a (1 ≤ a ≤ 1000) — количество лимонов, которые есть у Николая
Во второй строке следует целое положительное число b (1 ≤ b ≤ 1000) — количество яблок, которые есть у Николая.
В третьей строке следует целое положительное число c (1 ≤ c ≤ 1000) — количество груш, которые есть у Николая.
Выходные данные
Выведите максимальное суммарное количество лимонов, яблок и груш, из которых можно сварить компот по рецепту.
входные данные
2
5
7
выходные данные
7
входные данные
4
7
13
выходные данные
21
входные данные
2
3
2
выходные данные
0
Разбор:
Для начала вычислим, сколько порций компота (состав порции — 1 лимон, 2 яблока и 4 груши) можно приготовить. Это число будет равно min(a, b / 2, c / 4), где x / y обозначает целую часть дроби x / y. После этого полученное число надо домножить на 7, так как в каждой порции ровно 7 фруктов, и вывести результат.
Тема: математика
Сложность времени: O (1).
Задача C. Drazil и свидание. Ограничение по времени: 1 с
Как-то раз Drazil захотел пойти на свидание с Varda. Drazil и Varda живут на декартовой плоскости. Drazil живет в доме в точке (0, 0), а Varda живет в доме в точке (a, b). За каждый ход Drazil может пройти единичное расстояние по горизонтали или вертикали в любом направлении. Иными словами, он может переместиться из точки (x, y) в точки (x + 1, y), (x - 1, y), (x, y + 1) или (x, y - 1).
К сожалению, Drazil плохо ориентируется на местности. Поэтому каждым ходом он выбирает направление наугад. Например, во время своего путешествия он может случайно вернуться домой. Более того, Drazil может не заметить, что он прибыл в (a, b) и продолжить перемещаться дальше.
В конце концов, Drazil успешно прибыл в точку (a, b). Drazil сказал Varda: «Дорога от моего дома к твоему заняла у меня ровно sходов». Теперь Varda задаётся вопросом — возможно ли добраться из (0, 0) в (a, b) ровно за s ходов? Можете ли вы определить ответ на этот вопрос?
Входные данные
На вход подаются три целых числа a, b, и s ( - 109 ≤ a, b ≤ 109, 1 ≤ s ≤ 2·109).
Выходные данные
Если Drazil ошибся и ровно за s шагов невозможно добраться до дома Varda, выведите «No» (без кавычек).
В противном случае выведите «Yes».
входные данные
5 5 11
выходные данные
No
входные данные
10 15 25
выходные данные
Yes
входные данные
0 5 1
выходные данные
No
входные данные
0 0 2
выходные данные
Yes
Разбор:
Если Drazil выбирает кратчайший путь от (0,0) до (a, b), он будет равен |A| + |B| шагам. Если заданное количество шагов меньше чем количество шагов при кратчайшем пути, то ответ сразу “No”. Теперь рассмотрим, когда количество шагов не меньше |A| + |B|. Когда Drazil приходит к (a, b), он может сделать еще два шага, такие как (a, b) -> (a, b + 1) -> (a, b), чтобы оставаться в одном и том же положении. После того как он в (a, b), то ему останется пройти еще s — (|a| + |b|) шагов. Таким образов, если оставшееся количество шагов кратно двум, то ответ “Yes”, иначе “No”.
Возможные ошибки: забыли рассмотреть случай, когда указанная точка лежит не в первой четверти. Так как нам важна длина пути, то берем модуль от координат точки.
Тема: Математика
Сложность времени: O (1)
Задача D. k-й делитель. Ограничение по времени: 2 с
Даны два натуральных числа n и k. Найдите k-й в порядке возрастания делитель числа n, либо сообщите, что его не существует.
Делителем числа n является любое натуральное число, на которое число n делится без остатка.
Входные данные
В первой строке следуют два целых числа n и k (1 ≤ n ≤ 1015, 1 ≤ k ≤ 109).
Выходные данные
Если у числа n менее k делителей, выведите -1.
В противном случае, выведите k-й в порядке возрастания делитель числа n.
входные данные
4 2
выходные данные
2
входные данные
5 3
выходные данные
-1
входные данные
12 5
выходные данные
6
Разбор:
Утверждение: если найти все малые делители n, которые меньше, чем sqrt (n), то можно найти и остальные из них, делящие n на маленькие.
Пусть мы нашли a — делитель числа n. Тогда, сразу можем найти еще один делитель, поделив n на a.
Можно доказать, что если у числа нет делителей до корня из этого числа, то их вообще нет. То есть, все маленькие делители находятся до корня из числа, а все соответствующие им большие делители (выше написано, как находить) лежать после корня из этого числа. Найдем все маленькие, и запишем их в массив. Теперь легко можем вывести k -ый делитель, обратившись к нужному элементу массива. Только надо учитывать, делитель лежит после корня или нет. От этого зависит, что выводить, сам элемент массива или соответствующий больший делитель.
Тема: Математика, теория чисел
Сложность времени: O (sqrt(n)).
Задача Е. Степени двойки. Ограничение по времени: 3 с
Вам задано n чисел a1, a2, …, an. Найдите количество пар индексов i, j (i < j) таких, что ai + aj является степенью двойки (то есть найдется такое целое число x, что ai + aj = 2x).
Входные данные
В первой строке следует целое положительное число n (1 ≤ n ≤ 105) — количество чисел.
Во второй строке следует n целых положительных чисел a1, a2, …, an (1 ≤ ai ≤ 109).
Выходные данные
Выведите количество пар индексов i, j (i < j) таких, что ai + aj является степенью числа 2.
входные данные
4
7 3 2 1
выходные данные
2
входные данные
3
1 1 1
выходные данные
3
Разбор:
Для решения данной задачи заведем ассоциативный массив (map) cnt, а запомним в нем, сколько раз встречалось каждое число. Затем проитерируемся по всем заданным числам переменной i. Пусть текущее число равно ai. Для него переберем все возможные степени двойки (их будет не более 31). Пусть текущая степень двойки равна cur. Тогда существует ai чисел, которые дают вместе с ai - cur числом степень двойки. И тут существуют два случая:
- Когда они равны, то прибавить к ответу cnt[ai]* (cnt[ai]-1)/2.
- Когда не равны, то прибавить к ответу cnt[ai]* cnt[cur — ai].
Тема: Математика, теория чисел, структуры данных
Сложность времени: O (sqrt(n)).
Задача F. Большой день для Баша. Ограничение по времени: 2 с
Баш отправился в путешествие, чтобы стать величайшим мастером Покемонов. Чтобы получить первого покемона, он отправился в лабораторию профессора Зулу. Поскольку Баш — любимый студент профессора, Зулу разрешил ему взять столько покемонов из лаборатории, сколько Баш захочет.
Однако, профессор предупрел Баша, что группа из k > 1 покемонов с силами {s1, s2, s3, …, sk} склонна к драке между собой, если gcd(s1, s2, s3, …, sk) = 1 (gcd — это наибольший общий делитель).
Баш, будучи умным студентом, не хочет, чтобы его покемоны дрались между собой. В то же время, он хочет максимизировать количество покемонов, которые он возьмет. Можете помочь Башу найти максимальное число покемонов, которых он может взять с собой?
Обратите внимание: Один покемон не может драться сам с собой.
Входные данные
Входные данные находятся в двух строках.
Первая строка содержит целое число n (1 ≤ n ≤ 105) — число покемонов в лаборатории профессора.
Следующая строка содержит n целых чисел, где i-е из них равно si (1 ≤ si ≤ 105) — силе i-го покемона.
Выходные данные
Выведите одно число — максимальное число покемонов, которых Баш может взять.
входные данные
3
2 3 4
выходные данные
2
входные данные
5
2 3 4 6 7
выходные данные
3
Разбор:
Возьмем каждое число, найдем делители и будем проводить подсчет, какое число сколько раз является делителем с помощью сортировки подсчетом. Максимум в этом массиве и будет ответом.
Тема: Математика, теория чисел, жадные алгоритмы
Сложность времени: O (sqrt(n)).
Ну и как всегда фотки )
