Всем привет. Продолжаем линейку статей про летнюю школу точных наук. Второй день выдался достаточно сложным. С утра была лекция про геометрию. Участники школы были в бешенстве от такого взрыва мозга. Что там участники, я сам чувствовал себя не очень.
Итак начнем, задач было предложено 5.
Задача А. Праздник равенства. Ограничение по времени: 1 секунда
В Берляндии наступил праздник равенства. В честь праздника король решил за счёт государственной казны уравнять благосостояние всех граждан Берляндии.
Всего в Берляндии n граждан, благосостояние каждого из которых оценивается целым числом в ai бурлей (бурль — денежная единица Берляндии).
Вы — королевский казначей, которому требуется посчитать минимальные расходы королевства на подарок короля. Король может только давать деньги, а отбирать их он не имеет права.
Входные данные
В первой строке входных данных содержится целое число n (1 ≤ n ≤ 100) — количество граждан Королевства.
Во второй строке содержатся n чисел a1, a2, …, an, где ai (0 ≤ ai ≤ 106) — благосостояние i-го гражданина.
Выходные данные
В единственную строку выходных данных выведите выведите целое число S — минимальное количество бурлей, которое придётся потратить.
входные данные
5
0 1 2 3 4
выходные данные
10
входные данные
5
1 1 0 1 1
выходные данные
1
входные данные
3
1 3 1
выходные данные
4
входные данные
1
12
выходные данные
0
Разбор:
Раз не можем уменьшать числа, то нам придётся увеличить все числа как минимум до max(a1, a2, …, an). Если все числа равны max(a1, a2, …, an), то их не имеет смысла увеличивать дальше, так как мы на это только потратим лишние бурли.
Таким образом, следует найти max(a1, a2, …, an) с помощью одного прохода по массиву. И потом ещё раз пройти, прибавляя к общей сумме разность максимального элемента и очередного. То есть, посчитав max, для очередного элемента количество бурлей, затраченных на его увеличение, равно max - ai.
Тема: математика
Время работы — O(n).
Задача В. МУХ и палочки. Ограничение по времени: 1 секунда
Белым медведям Меньшикову и Усладе из Санкт-Петербургского зоопарка и слонику Хорасу из Киевского зоопарка в рамках проверки их творческих способностей дали для игры шесть палочек. Меньшиков, Услада и Хорас решили собрать из этих палочек либо слона, либо медведя. Животные из палочек собираются так:
- Четыре палочки изображают лапы животного, эти палочки должны быть равными по длине.
- Две оставшиеся палочки изображают голову и тело животного. У медведя палочка-голова должна быть короче палочки-тела. У слона же есть длинный хобот, поэтому палочка-голова слона должна быть такой же длины, как палочка-тело. Обратите внимание, что нет никаких ограничений на отношения между палочками лап и палочками головы и тела животных.
От вас требуется узнать, какое животное можно собрать из заданного набора палочек. После игры палочки необходимо вернуть руководителю зоопарка, поэтому ломать их категорически запрещено, это даже медведям понятно.
Входные данные
В единственной строке через пробел даны шесть чисел li (1 ≤ li ≤ 9) — длины шести палочек. Гарантируется, что входные данные таковы, что собрать обоих животных из них никак не получится.
Выходные данные
Если из заданного набора можно собрать медведя, то выведите строку «Bear» (без кавычек). Если можно собрать слона, то выведите строку «Elephant» (без кавычек). Если ни медведя, ни слона собрать невозможно, то выведите строку «Alien» (без кавычек).
входные данные
4 2 5 4 4 4
выходные данные
Bear
входные данные
4 4 5 4 4 5
выходные данные
Elephant
входные данные
1 2 3 4 5 6
выходные данные
Alien
Разбор:
Нам даны длины шести палочек и надо проверить, какое животное мы может из них собрать. Единственное условие, общее для обоих животных, — четыре палочки-лапы должны быть одной длины. Так как это условие общее, то в случае отсутствия хотя бы четырех палочек одинаковой длины ответ будет однозначно «Alien». Если же такие четыре палочки есть, то кого-нибудь мы точно соберем, надо только решить кого. В этом случае ответ будет зависеть от того, равны ли оставшиеся две палочки. Весь алгоритм получается такой:
- Найти число, встречающееся не менее четырех раз.
- Если такого числа нет, то ответ — «Alien»
- Иначе надо удалить четыре вхождения этого числа из входного массива.
- Если два оставшихся числа равны, то ответ — «Elephant», а иначе — «Bear».
Чтобы искать сколько раз каждое число встречается, удобно воспользоваться сортировкой подсчетом.
Тема: реализация
Время работы — O(1).
Задача С. Парад. Ограничение по времени: 1 секунда
Совсем скоро в Берляндии состоится парад победы над инопланетными захватчиками. К сожалению, в войне погибли все солдаты, и теперь армия состоит исключительно из новобранцев, многие из которых даже не знают, с какой ноги начинается марш. Гражданское население тоже плохо понимает, с какой ноги начинается марш, поэтому важно лишь, чтобы как можно больше солдат шли в одну ногу.
В параде будут принимать участие n пеших колонн, i-я из которых состоит из li солдат, начинающих марш с левой ноги, и ri солдат, начинающих марш с правой ноги.
Красота парада вычисляется по следующей формуле: если L — это суммарное количество солдат на параде, начинающих марш с левой ноги, а R — это суммарное количество солдат на параде, начинающих марш с правой ноги, то красота будет равна |L - R|.
Вы можете выбрать не более чем одну колонну, и изменить с какой ноги начинают марш все солдаты данной колонны. Формально, разрешается не более одного раза выбрать какой-то индекс i и поменять местами значения li и ri.
Найдите номер колонны, при смене шага в которой красота парада станет максимально возможной, или определите, что такой операцией улучшить красоту парада нельзя.
Входные данные
В первой строке содержится одно число n (1 ≤ n ≤ 105) — количество пеших колонн. В следующих n строках находятся пары целых чисел li и ri (1 ≤ li, ri ≤ 500) — количество солдат в i-й колонне, начинающих марш с левой и с правой ноги соответственно.
Выходные данные
Выведите одно целое число k — номер колонны, в которой следует сменить шаг, или 0, если максимальная красота уже достигнута.
Считайте, что колонны пронумерованы от 1 до n в порядке их задания во входных данных. Если решений несколько, выведите любое.
входные данные
3
5 6
8 9
10 3
выходные данные
3
входные данные
2
6 5
5 6
выходные данные
1
входные данные
6
5 9
1 3
4 8
4 5
23 54
12 32
выходные данные
0
Разбор:
Посчитаем начальные значения L и R. Пусть maxk — это максимальная красота, которую можно достичь, изначально maxk = |L - R|.
Теперь пройдёмся циклом по всем колоннам и посчитаем красоту ki для i-й колонны, если в ней сменить шаг. ki = |(L - li + ri) - (R - ri + li)|. Если ki > maxk, то обновляем maxk и сохраняем i — номер колонны, в которой выгоднее всего сменить шаг.
Если не нашлось такого i, что ki > maxk, тогда ответ 0.
Тема: математика
Время работы — O(n).
Задача D. Четырехугольник с максимальной площадью. Ограничение по времени: 1 секунда
Яхуб нарисовал множество из n точек на декартовой плоскости. Он назвал их «особыми точками». Четырехугольник — это многоугольник без самопересечений, имеющий четыре стороны (или ребра) и четыре вершины (или угла). Пожалуйста, обратите внимание, что четырехугольник может не быть выпуклым. Особый четырехугольник — это такой четырехугольник, в котором все четыре вершины принадлежат множеству особых точек. Вам дано множество особых точек. Пожалуйста, вычислите максимальную площадь особого четырехугольника.
Входные данные
В первой строке записано целое число n (4 ≤ n ≤ 300). В каждой из следующих n строк записано по два целых числа: xi, yi( - 1000 ≤ xi, yi ≤ 1000) — декартовы координаты i-той особой точки. Гарантируется, что никакие три точки не лежат на одной прямой. Гарантируется, что никакие две точки не совпадают.
Выходные данные
Выведите единственное вещественное число — максимальную площадь особого четырехугольника. Ответ будет считаться правильным, если его относительная или абсолютная погрешность не превышает 10-9.
входные данные
5
0 0
0 4
4 0
4 4
2 3
выходные данные
16.000000
Разбор:
- Перебрать все отрезки, считая их диоганалями четырехугольников.
- Выбрать точку, образующую треугольник максимальной площади для одной полуплоскости
- Выбрать точку, образующую треугольник максимальной площади для другой полуплоскости. Чтобы вычислить площадь треугольника по координатам точек, надо воспользоваться векторный (косым, псевдоскалярным) произведением.
- Перебрать сумму всех треугольников
Тема: геометрия
Время работы: O(n3)
Задача Е. Сумасшедший город. Ограничение по времени: 1 секунда
Сумасшедший город представляет собой плоскость, на которой имеется n бесконечных прямых дорог. Каждая дорога задаётся уравнением aix + biy + ci = 0, где ai и bi не равны нулю одновременно. Дороги разбивают плоскость на связные области, возможно бесконечной площади. Каждую такую область назовем кварталом. Перекрестком будем называть точку пересечения хотя бы двух различных дорог.
Ваш дом расположен в одном из кварталов. Сегодня вам надо добраться до университета, также расположенного в некотором квартале. За один шаг вы можете переместиться из одного квартала в другой, если протяжённость их общей границы ненулевая (в частности это значит, что если кварталы смежны одному перекрёстку, но не имеют общего ненулевого отрезка границы, то перейти из одного в другой за один шаг нельзя).
Определите, какое минимальное количество шагов вам придётся сделать, чтобы оказаться в квартале, содержащем университет. Гарантируется, что ни ваш дом, ни университет не расположены на дороге.
Входные данные
В первой строке записано два целых чисел через пробел x1, y1 ( - 106 ≤ x1, y1 ≤ 106) — координаты вашего дома.
Во второй строке записано два целых числа через пробел x2, y2 ( - 106 ≤ x2, y2 ≤ 106) — координаты университета, где вы учитесь.
В третьей строке записано целое число n (1 ≤ n ≤ 300) — количество дорог в городе. В следующих n строках записаны через пробел по 3 целых числа ( - 106 ≤ ai, bi, ci ≤ 106; |ai| + |bi| > 0) — коэффициенты прямой aix + biy + ci = 0, задающей i-ю дорогу. Гарантируется, что никакие две дороги не совпадают. Кроме этого, ни ваш дом, ни университет не лежат на дороге (т. е. не принадлежат ни одной из прямых).
Выходные данные
В единственной строке выведите одно целое число — ответ на задачу.
входные данные
1 1
-1 -1
2
0 1 0
1 0 0
выходные данные
2
входные данные
1 1
-1 -1
3
1 0 0
0 1 0
1 1 -3
выходные данные
2
Разбор:
Несложно показать, что, если две исходные точки изначально находятся по разные стороны какой-то из прямых, эту прямую в любом случае придется пересечь. Поскольку все, что нам нужно — это пересечь все такие прямые, ответ на задачу — их количество.
Чтобы проверить, лежат ли точки по разные стороны прямой, достаточно подставить их координаты в ее уравнение, и проверить, что получившиеся два значения имеют разные знаки.
Тема: геометрия
Время работы — O(n).
Ну и как всегда фотки с сегодняшнего дня )