Ученый с мировым именем Иннокентий только что синтезировал зелье бессмертия. К сожалению, он поставил колбу с этим зельем на полку, где хранились самые опасные яды всех времен и народов. Теперь на этой полке стоит n колб, и ученый совершенно не представляет, в какой же из них находится зелье бессмертия.

К счастью, у Иннокентия есть бесконечное количество подопытных кроликов. Но ученому неизвестно, как именно эти зелья действуют на кроликов. Единственное, что он знает наверняка — что если дать кролику попробовать содержимое ровно k колб с этой полки, то кролик выживет, если среди них было зелье бессмертия, и умрет в противном случае. Если же дать кролику попробовать число зелий, отличное от k, то результат будет абсолютно непредсказуем, поэтому ученый ни за что не будет так поступать.

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

Мальчики Гена и Петя написали на двух полосках бумаги по одинаковой строке s, состоящей из строчных латинских букв. Затем каждый взял себе по полоске, порезал ее на мелкие кусочки так, чтобы на каждом была одна буква, и положил все кусочки себе в карман. После этого Гена и Петя, пока их карманы не опустели, одновременно доставали из своего кармана по одному кусочку и радовались, если буквы на этих кусочках совпадали.

Определите ожидаемое число раз, которое мальчики радовались в процессе этого занятия.

Программисты компании «Периметр» работают над n проектами. Начальник программистов Шифтмэн прекрасно понимает, насколько важны комфортные условия для продуктивной работы — в компании нет ни дресс-кода, ни фиксированного рабочего графика, зато на кухне всегда есть чай и свежие киви. А когда команда проекта «Диплодок» стала жаловаться на то, что после выхода на работу новых сотрудников в комнате не протолкнуться, Шифтмэн понял — пора искать более просторный офис.

Новое офисное здание нашлось быстро. Оно расположено недалеко от метро, возле уютного парка. Кроме того, в подвале здания много парковочных мест. Узнав, что в новом офисе n больших комнат, Шифтмэн решил выделить по комнате каждому проекту, чтобы сотрудники создали там уникальную для каждого проекта рабочую атмосферу. Менеджер каждого проекта знает, какая комната идеально подойдет для его команды — с одной стороны, комната должна быть не слишком тесной, а с другой — не слишком большой, чтобы сотрудники не боялись того, что к ним могут подселить новый проект. Помогите менеджерам поделить комнаты самим, быстро и без вмешательства начальства.

Все знают, что битва при Эндоре — миф, придуманный Джорджем Лукасом ради раскрутки своего фильма. На самом деле никакой битвы при Эндоре не было, и Первая Галактическая Империя существует в полном здравии и по сей день.

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

Прислуга Императора не очень сильна в математике, поэтому вам необходимо посчитать, сколько всего бывает различных праздников такого вида. Два праздника считаются различными, если они отличаются множеством рас, которое дарит подарки, или множеством рас, которому дарят подарки.

Лабиринт — это прямоугольная сетка, каждая из клеток которой либо свободна, либо является стеной, причем перемещаться можно только между смежными по стороне свободными клетками.

Константин и Михаил — мировые лидеры по составлению лабиринтов. Они составили каждый по лабиринту размером n × m, и теперь обвиняют друг друга в плагиате. Они считают, что плагиат имел место, если существует путь из левой верхней клетки в правую нижнюю, являющийся кратчайшим в обоих лабиринтах. Разрешите их спор и скажите, имел ли место плагиат.

Через t единиц времени наступит конец света. В преддверии столь знаменательного события n людей подготовили m убежищ, в которых, как они думают, можно будет спастись. Однако каждое убежище вмещает в себя лишь k человек, а каждый человек за одну единицу времени проходит лишь одну единицу расстояния. К счастью, все люди и убежища находятся сейчас на одной прямой, что уменьшает путаницу и облегчает подсчеты.

Вам дано расположение людей и убежищ на прямой. Выясните, какое максимальное количество людей смогут спрятаться в убежищах и думать, что им удастся спастись.

Андрей в свободное от игр время обрабатывает изображения. Больше всего он любит обрабатывать картинки в градациях серого. Каждый пиксель на картинке в градациях серого имеет яркость, выраженную целым числом от 0 до 10⁹. Чем ближе яркость к нулю, тем темнее этот пиксель; яркость, равная нулю, соответствует черному цвету, а 10⁹ — белому. Андрей называет такие картинки цветными.

В процессе обработки цветной картинки Андрей выбирает целое число t в диапазоне от 0 до 10⁹ и создает новую картинку, состоящую всего из двух цветов: черного и белого (которые он обозначает как 0 и 1). Такие картинки он называет черно-белыми.

Принцип составления черно-белых картинок очень прост: Андрей рассматривает каждый пиксель исходной цветной картинки, и, если яркость этого пикселя строго меньше t, на новой картинке этот пиксель будет черного цвета, иначе — белого.

Вам дано k черно-белых картинок. Определите, могли ли они все быть получены в результате обработки Андреем какой-либо цветной картинки, и если да, то из какой именно, и какие именно значения t₁, ..., t_k он мог для этого использовать.

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

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

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

Перед Вами, как перед штатным программистом газеты, стоит задача — определить, могут ли это быть фотографии одной и той же тройки звезд.

Определим производные массива следующим образом:

• Нулевой производной массива a₁, ..., a_n называется сам этот массив a₁, ..., a_n.
• Первой производной массива a₁, ..., a_n, где n > 1, называется массив a'₁, ..., a'_n - 1, такой, что для всех i = 1,  ...,  n - 1 выполняется равенство a'_i = a_i + 1 - a_i.
• k-ой производной массива a₁, ..., a_n, где 1 < k < n, называется (k - 1)-ая производная массива a'₁, ..., a'_n - 1.

Даны n чисел b₀, ..., b_n - 1, каждое из которых равно либо нулю, либо единице. Постройте массив длины n такой, что его k-я производная строго возрастает, если b_k = 1, и строго убывает, если b_k = 0. Каждый элемент массива должен быть целым числом от  - 10⁹ до 10⁹. Если это невозможно, выведите «IMPOSSIBLE».

Ученый с мировым именем Иннокентий продолжает свои инновационные эксперименты с колодами карт. Теперь у него есть колода из n карт и k шаффл-машин для перемешивания этой колоды. Как мы знаем, i-ая шаффл-машина характеризуется своими собственными числами p_i, 1, p_i, 2, ..., p_i, n, такими, что если положить в нее n карт, занумерованных по порядку 1, 2, ..., n, и нажать на машине кнопку, то карты будут перемешаны таким образом, что образуется колода p_i, 1, p_i, 2, ..., p_i, n, где числа p_i, 1, p_i, 2, ..., p_i, n — это те же номера карт, но переставленные в некотором порядке шаффл-машиной.

В начале эксперимента карты в колоде располагаются в порядке a₁, a₂, ..., a_n, т.е. на первом месте находится карта с номером a₁, на втором — карта с номером a₂, и т.д. Ученый хочет сделать так, чтобы карта с номером x была на первом месте. Он может использовать все свои шаффл-машины столько раз, сколько ему захочется. Выясните, получится ли у него добиться желаемого результата.

Ученый с мировым именем Иннокентий почти закончил изготовление вечного двигателя. Основной его деталью является генератор энергии, который дает возможность работать остальным частям двигателя. Он состоит из двух длинных параллельных друг другу пластин, на одной из которых расположены n лазеров, а на другой — n приемников. Генератор энергии считается работающим, если каждый лазер испускает луч в приемник, причем в каждый приемник должен входить ровно один луч.

Разумеется, может возникнуть ситуация, когда лучи, испускаемые разными лазерами, пересекаются. Если два луча пересекаются, то из-за их взаимодействия каждую секунду будет выделяться энергия, равная одному джоулю. Таким образом, чем больше лучей пересекается друг с другом, тем больше энергии будет выделять генератор. Иннокентий заметил, что если генератор энергии будет выделять ровно k джоулей в секунду, то двигатель будет работать до 10 раз дольше. Ученый может направлять лучи лазеров в любые приемники, однако он пока не придумал конструкции, которая давала бы в точности необходимое количество энергии. Вам придется помочь ученому настроить генератор.

Андрей работает в министерстве правды. Его работа состоит в том, чтобы изменять статьи в газетах и журналах таким образом, чтобы они восхваляли партию и Большого Брата.

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

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

Функцией Хевисайда называется кусочно-постоянная функция, равная нулю для отрицательных значений аргумента и единице — для неотрицательных:

Дана функция f(x) = θ(s_1x - a₁) + θ(s_2x - a₂) + ... + θ(s_nx - a_n), где s_i =  ± 1. Посчитайте ее значение в точках x₁, x₂, ..., x_m.