Пусть нам дано натуральное число \(N\). Рассмотрим множество различных целых чисел \(\{a_1, a_2, \dots, a_k\}\), где каждое число лежит в интервале от \(0\) до \(N-1\) включительно. Назовём такое множество свободным от сумм, если в этом множестве не найдётся таких трёх чисел, что сумма двух из них сравнима с третьим по модулю \(N\). Строго говоря, назовём множество свободным от сумм, если для каждой тройки (не обязательно различных) индексов \(x\), \(y\) и \(z\) (\(1\leq x,y,z\leq k\)) выполняется неравенство: \(\)(a_x+a_y) \bmod N \neq a_z\(\)

где \(p \bmod q\) — остаток от деления \(p\) на \(q\).

Например, при \(N=6\) множествами, свободными от сумм, не являются, например, \(\{0\}\) (т.к. \((0+0)\bmod 6=0\)), \(\{1,2\}\) (т.к. \((1+1) \bmod 6=2\)), \(\{3,4,5\}\) (т.к. \((4+5)\bmod 6=3\)), но множество \(\{1,3,5\}\) является свободным от сумм.

По заданному \(N\) определите, сколько существует множеств, свободных от сумм.

На досуге вы любите почитать сборники занимательных задач по математике. Недавно вы наткнулись в одном из таких сборников на следующую задачу:

Есть бесконечный резервуар с водой и два пустых сосуда объёмом 5 и 12 литров. Можно наливать воду из резервуара в любой сосуд до его заполнения, переливать воду из —одного сосуда в другой до заполнения второго или опустошения первого (смотря что будет раньше) и выливать воду из сосуда на землю до полного опустошения сосуда. Как таким образом можно отмерить 3 литра?

Вы решили написать программу, которая будет решать подобные задачи для произвольных объёмов сосудов.

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

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

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

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

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

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