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

Вы по-прежнему работаете под руководством д.б.н., проф. О.Б. Ломова и изучаете интеллект обезьян. Ваши подопечные уже очень далеко ушли от столь элементарной задачи, как сбор квадрата. Теперь вы работаете над тем, чтобы обучить их намного более сложной задаче. Вы по-прежнему даёте обезьянам набор из \(N\) палочек, но на этот раз вы хотите, чтобы они собрали из этих палочек треугольник.

Конечно, решить эту задачу в элементарном варианте — выбрать три палочки и собрать из них треугольник — ваши подопечные могут без каких-либо проблем; вы же хотите их обучить, чтобы они собирали один большой треугольник из всех выданных им палочек сразу. Таким образом, они должны разбить палочки на три группы так, чтобы, сложив палочки каждой группы в один большой отрезок, получить три отрезка, из которых можно собрать треугольник. Полученный треугольник должен быть невырожденным, т.е. его площадь должна быть строго больше нуля.

Как и в прошлый раз, вам понадобилась программа, которая определит, разрешима ли задача для данного набора палочек.

В городе N строят метро. Вася, житель города N, хочет знать, сколько станций окажутся недалеко от его дома. Помогите ему.

Город N отличается очень строгой планировкой улиц: каждая улица идёт либо строго с юга на север, либо строго с востока на запад; при этом расстояние между соседними параллельными улицами одинаково. Соответственно, в городе есть много перекрёстков, расположенных в вершинах квадратной сетки. По планам, первая линия метро будет прямой и будет иметь станции на каждом перекрёстке, через который она пройдёт. Вася считает, что станция находится недалеко от его дома, если расстояние по прямой от его дома до станции не превосходит некоторой фиксированной величины \(R\).

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

Стоимость стакана чая и кофе в автомате предполагается установить равной пяти рублям. Автоматы будут принимать монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда пассажиру надо выдавать сдачу (т.е. когда пассажир бросил в автомат десятирублёвую монету или 10-, 50- или 100-рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же пассажир бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим пассажирам.

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

Рассмотрим два числа \(a\) и \(b\). По ним можно однозначно определить такое целое \(k\), что \(\) b^k\leq a< b^{k+1}; \(\) это \(k\) мы будем называть целой частью логарифма \(a\) по основанию \(b\).

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