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

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

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

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

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

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

Кроме этого, будем считать, что продажа и покупка будет осуществляться только с акциями одного типа. На начало этого периода вы располагаете суммой в x рублей. Для каждого из дней известна цена a_i (от ask — цена предложения), по которой можно купить одну акцию, и цена b_i (от bid — цена спроса), по которой можно одну акцию продать. При этом в соответствии с действующими правилами торгов на бирже разрешается продавать и покупать только целое число акций (например, если у вас есть 5 рублей, а акция стоит 2 рубля, то вы можете купить не более двух акций).

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

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

Петя пытается добиться того, чтобы последовательность чисел, написанных на карточках стала строго монотонной (возрастающей или убывающей). Для этого ему разрешается совершать следующие действия: выбрать два числа l и r, такие что 1 ≤ l≤ r ≤ n и перевернуть каждую из карточек от карточки номер l до карточки номер r.

Напомним, что последовательность c₁, . . . , c_n называется строго возрастающей, если выполняются неравенства c₁ < c₂ < … < c_n, и строго убывающей, если выполняются неравенства c₁ > c₂ > … > c_n.

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

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

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

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

Так как во Флатландии повсеместно внедрены информационные технологии, то подготовка плаката велась с помощью специальной программы. В этой программе (как и во многих других) цвета представляются в так называемом RGB-формате. Это означает, что цвет кодируется тремя целыми числами, каждое из которых находится в пределах от 0 до 31 (обычно используются значения от 0 до 255, но оборудование, используемое для печати, обладает ограниченными возможностями цветопередачи). Эти числа обозначают интенсивность красной, зеленой и синей компонент цвета (0 соответствует отсутствию соответствующей компоненты, а 31 — ее максимальной интенсивности).

Таким образом, черный цвет кодируется как (0; 0; 0), а белый — как (31; 31; 31).

Цвета различных областей плаката определяются следующим образом. Изначально весь плакат заполняется белым цветом (таким образом, исходно все точки имеют цвет (31; 31; 31)), после чего выполняется рисование прямоугольников, заданных в описании плаката. При рисовании прямоугольника цветом, который кодируется как (r; g; b), новые цвета точек, находящихся внутри этого прямоугольника, определяются так: если до рисования точка имела цвет (r1; g1; b1), то после того, как прямоугольник будет нарисован, ее цвет будет равен ((r1+r) mod 32; (g1+g) mod 32; (b1+b) mod 32).

Например, на рисунке приведен плакат, который получается из белого листа размера 10 # 10 изображением двух прямоугольников: цвета (12; 0; 12) с координатами левого нижнего угла (0; 0) и правого верхнего (5; 5), а затем цвета (0; 12; 0) с координатами левого нижнего угла (4; 4) и правого верхнего (6; 6).

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

Как и у каждого мальчика, у Феди есть игрушечные машинки. Однако ему повезло больше, чем обычному мальчику — все \(n\) его машинок являются радиоуправляемыми. Целыми днями он может устраивать различные автогонки и играть с друзьями.

Из всех видов гонок Федя предпочитает гонки по прямой. В данном формате соревнования трасса имеет форму прямой и является бесконечной (соревнования идут до тех пор, пока Феде это не надоест). Изначально каждая из \(n\) машинок находится на некотором расстоянии от старта — имеет фору \(x_i\) метров. По команде все машинки начинают свое движение от старта, при этом каждая машинка движется во время гонки с постоянной скоростью \(v_i\) метров в секунду. Все машинки движутся в одном направлении — удаляются от старта.

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

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