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

Опишем подробнее суть фокуса. Два человека из толпы называют по одному целому числу каждый. Для определенности назовем эти числа n и m. Далее Дэвид производит в уме вычисления (это занимает у него ровно 0.42 секунды) и выдает секретное число x. Что же такое x? Это такое целое положительное число не превышающее n, для которого выполняется соотношение для любого k > 0 ( — операция взятия остатка от деления). Дэвиду стало известно, что таких чисел может быть очень много, поэтому он решил узнать, а сколько же таких чисел можно подобрать для заданных n и m?

Разнообразие вкуснях застало Бернарда врасплох, когда ему на глаза попалась коробка с конфетами. Коробка состояла из n × n секций и в каждой секции находились конфета определенного типа. Растерянному Бернарду только что и оставалось выбрать какой-то прямоугольник из секций и съесть все конфеты в них, но хладнокровие никогда не подводило его, поэтому каждый прямоугольник имел одинаковый шанс быть выбранным. А нам всего лишь интересно какое математическое ожидание количества различных конфет будет съедено сию секунду.

Клуб любителей детективных историй проводит свои заседания каждый день начиная с 13 сентября 1842 года. Каждый день слово для выступления брал человек, номер клубного билета которого равен x. Более чем 150 лет организаторы клуба вели статистику выступавших и наконец решили ее проанализировать. Оказывается, в первый день работы клуба выступал член с билетом 1, во второй день – 2, в третий – 4, в четвертый – 6, в пятый – 3 и т.д. Председатель клуба заметил, что в каждый новый день номер билета выступающего является минимальным натуральным числом, не совпадающим с номерами билетов выступавших ранее и одновременно не являющимся взаимно простым с номером билета предыдущего выступавшего.

По традиции клуба номера выступающих вывешивали в качестве объявления, но в век современных технологий объявление было заменено на автоматическое цифровое табло, которое каждый день меняло номер выступающего. Клуб любителей детективов заказал программное обеспечение для подсчета номера билета выступающего в день n, но его работоспособность подвергнута сомнению, поскольку алгоритм вычислений очень непростой. Не могли бы Вы помочь клубу?

Флеш появился появился на свет в середине 20-х годов XX века. Соответственно, в настоящее время ему уже скоро исполнится 100 лет и по правилам Лиги справедливости он вынужден будет сложить с себя полномочия супергероя и выйти на заслуженный отдых.

Супергероям тоже нужно зарабатывать на жизнь, поэтому Флеш решил зарегистрировать свой бренда и получать плату за его использование. Бренд Флеша представляет собой ломанную линию, состоящую ровно из шести точек. Если двигаться вдоль ломанной, то поворот к следующей точке будет чередоваться (сперва левый, затем правый, затем левый и т. д.) и он будет резкий (угол поворота более ). Такая ломанная напоминает молнию.

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

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

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

В Бандиатерре избирательным правом обладает n жителей, которые приписаны к избирательным округам. Каждый избирательный округ содержит в себе равное число жителей. По такому же принципу округа делятся на подокруга, подокруга на подподокруга, подподокруга на подподподокруга и так далее до тех пор пока количество жителей предыдущей административной единицы делится нацело на какое-то целое число.

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

Барбато был одним из основателей этой избирательной системы, поэтому исключительным правом разделения населения на округа обладает только действующий президент. Исключительное право разделения на округа заключается в том, что Барбато может определить структуры округов (количество жителей в них) и состав (какие именно жители входят в подокруга). Структура округов определяется в соответствии с правилами, описанными выше. Разумеется, у президента в планах обширная агитационная кампания в его поддержку, чтобы убедить местных жителей голосовать за него. Какое минимальное количество жителей должно поддерживать президента в день выборов, чтобы разделение на избирательные округа обеспечило Барбато победу?

В далёкой-далёкой Мексике растут целые плантации кактусов. А еще там живут начинающие жулики Карлос и Педро. Они посмотрели фильм «Крёстный отец» и решили стать крупными мафиози. Но контрабандисты, которые торгуют оружием и наркотиками, не взяли их к себе. Поэтому они решили продавать кактусы пылким иностранным коллекционерам. Придя на плантацию, Карлос и Педро обнаружили, что не унесут в руках огромный кактус. Тогда горе-бандиты решили разрезать его на кусочки, содержащие не больше двух ребер. Посчитайте возможное количество различных способов разрезать несчастный кактус. Возьмите это огромное, как горе Карлоса и Педро, число по модулю 10⁹ + 7.

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

Быть преподавателем — тяжкий неблагодарный труд. Сначала студенты весь семестр прогуливают твои пары, предпочитая им теплую мягкую постель (хотя бы предупреждали, что не придут, не только им ведь хочется спать!), а потом приходится выслушивать их несуразные ответы на зачете. Устав от этого безобразия, почтенный профессор придумал новый способ принятия зачета.

За каждым человеком из группы, в которой учится n² студентов, закрепляется клеточка на квадратном поле, в которой стоит «Не зачтено». Ничего не подозревающий староста называет произвольное число k, и начинается самое интересное. Профессор выбирает произвольную строку или столбец и меняет там все отметки на противоположные. Такую операцию он проделывает до тех пор, пока ровно у k студентов не будет стоять «Зачтено». После этого зачет завершается и k счастливчиков отправляются праздновать успешное завершение сессии. Однако бывают случаи, когда по системе профессора невозможно получить k зачетов на бланке. Тогда на пересдачу отправляется вся группа. Отличник должен помочь старосте и ответить, получат ли несколько счастливцев сегодня зачет, если тот назовет число k.

— Нужно добавить совсем простую задачу.

— A + B?

— Да, давай, пойдет.

— Хорошо, сейчас сделаю.

...

— Я добавил, но есть одна проблемка.

— Какая?

— Я случайно удалил все тесты и теперь остались только правильные ответы :(

— Ничего страшного. Заливай их как тесты.

— Так а задача тогда в чем?

— По заданной сумме найти подходящие a и b.

Банковское ПО – самое надежное ПО в мире. По крайней мере, так утверждали разработчики. Но даже оно может дать сбой, что и случилось в отделении банка «Рога и копыта». Все данные по кредитным выплатам потерялись, осталась лишь база данных с фамилиями должников. Сложилась пренеприятнейшая ситуация. Все заёмщики утверждают, что их небольшие, в сущности, долги были выплачены почти полностью. Но директора банка Плюшкина терзают смутные сомнения. Поэтому он решил, что сумму долга для каждого из них нужно рассчитать заново. Сумма долга вычисляется как разность кредита и уже выплаченной должником суммы, которые представляют из себя n-значные целые числа (возможно с лидирующими нулями). Рассчитывают долг так: специалист по работе с клиентами Дурилкин называет цифру, а заёмщик Накупилкин вставляет её по своему усмотрению в еще незаполненную позицию числа кредита или выплаты , после чего процедура повторяется, пока полностью не заполнятся оба числа. Дурилкин стремится максимизировать долг, а Накупилкин – сделать его минимальным. Вам предоставляется возможность побыть на обеих сторонах. И также вам необходимо при всем этом действовать оптимальный образом. И конечно же ваш оппонент будет действовать оптимально.

В тридевятом царстве в тридесятом государстве жил-был Царь-Батюшка, и было у него два сына. Первый,младший сын, очень любил математические заковыристые задачки, а звали его Алеша Попович. Старший сын, Илья Муромец, не очень любил математику. Он изучал боевые искусства, чтобы в будущем защищать от врагов землю свою родную. Но всё же братья находили общие занятия и играли друг с другом каждый день. Однажды Царь-Батюшка решил подарить детям вишневый сад в форме квадрата с противоположными углами в координатах (0, 0) и (1, 1). Все вишневые деревья были посажены строго внутри сада. Сыновья были очень довольны, ведь там можно было не только бегать и играть, а также объедаться сладкими вишенками.

Но вскоре ребята выросли, и серьёзно поссорились: Илье не нравилось, что Алеша занимается математикой и совсем не хочет изучать боевые искусства, ведь на государство в любую минуту могут напасть враги. И пришлось поделить им вишневый сад. Так как в тридевятом царстве старшему сыну всегда достается больше, чем младшему, Илья решил забрать кусок сада с большим количеством вишневых деревьев себе (при равенстве количества деревьев любой). Алеша даже не стал спорить, лишь бы больше не слушать про врагов и подготовку к бою. Ребята выбрали две случайные точки на различных сторонах сада (каждая пара точек имеет равную вероятность быть выбранной), протянули между ними напрямую веревку и разделили сад на две части — по обе стороны от веревки. Часть с бОльшей частью деревьев осталась у Ильи, а меньшая - у Алеши. Можете считать, что вероятность протянуть прямую ровно через дерево равна нулю, т.е. всегда можно однозначно сказать какой части принадлежит дерево.

Весь следующий год Илья кушал вишенки и занимался спортом. Но вскоре Илье стало скучно, ведь вишенки закончились, а на государство так никто и не напал. А вот Алеша полностью посвятил себя математике. Он задумался, а сколько вишневых деревьев ему досталось бы, если бы братья выбрали другие случайные точки для разделения сада? Ведь главное только, чтобы у Алеши было не больше деревьев, чем у Ильи. Ему стало очень интересно, каково математическое ожидание количества вишневых деревьев в его части сада. Помогите Алеше справиться с этой непростой задачей.