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

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

Маленькому Леше улыбнулась удача: ему удалось раздобыть очень редкий и необычный массив A, состоящий из n целых чисел. Заполучив в свои руки такой ценный предмет, мальчик сразу же отнес его в свою подземную лабораторию, намереваясь постичь тайны устройства массива. Как опытный исследователь, Леша решил не спешить с проведением жутких экспериментов над бедным массивом, а сперва понаблюдать за ним. Он записал на листик бумаги результаты m наблюдений за массивом. Каждое наблюдение описывается тремя числами l_i, r_i и s_i, которые означают, что сумма элементов по модулю 2 на подотрезке [l_i, r_i] массива равна s_i. Леша подготовил все необходимое для проведения m + 1-го наблюдения, но тут он услышал, что мама зовет его обедать. По возвращении в свою лабораторию, мальчик увидел страшное: массив исчез. Совсем. Все надежды мальчика на получение Нобелевской премии в области исследования массивов рассыпались на глазах. Но потом Леша вспомнил, что у него все же осталась некоторая информация о массиве. Основываясь на записанных фактах, он решил построить компьютерную модель массива и проводить эксперименты над ней. Конечно, мальчик понимал, что он не сможет однозначно восстановить утерянный массив, потому что существует бесконечно много массивов, удовлетворяющих записанным фактам. Все мы знаем, что операции с большими числами занимают много времени, а если еще к тому же числа становятся отрицательными... Чтобы сделать свою компьютерную модель как можно более быстрой, Леша решил построить массив, удовлетворяющий известным фактам, элементы которого неотрицательны, а их сумма минимально возможная. Помогите ему сделать это!

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

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

Например, задумано тайное число 3219. Делается попытка 2310, в ответ приходит результат 12 — две коровы (две цифры 2 и 3 угаданы на неверных позициях) и один бык (одна цифра 1 угадана вплоть до позиции).

У Вас есть не более 8 попыток, чтобы отгадать загаданное число и покинуть живым обитель безумного фермера. Удачи!

Вам дано N чисел A_i. Требуется найти сумму A_i. К сожалению, числа во вводе перемешаны, т. е. число N может находится не на первой позиции.

Фермер Лёша владеет полем размера n клеток на m клеток. Позиция каждой клетки характеризуется парой чисел (i, j), которые обозначают номер строки и номер столбца соответственно. Каждая клетка этого поля является либо травой (обозначается символом '.') либо камнем (обозначается символом 'X').

Случилось несчастье — на поле начался пожар. Огонь начал разгораться из разных источников. Всего есть k источников огня. i-ый источник огня начал гореть из клетки с травой c координатами (x_i, y_i) и будет гореть c_i секунд. Каждую секунду огонь распространяется на соседние по сторонам клетки. Если в текущей клетке огню осталось горесть c секунд, то в соседней клетке, на которую он распространяется, ему останется гореть c - 1 секунду. Огонь из текущей клетки не распространяется, если ему остаётся гореть 0 секунд. Можно считать, что все огни горят независимо, то есть распространение огня никак не зависит от другого огня. Все источники огня имеют различные координаты. Камень не горит.

Лёше очень интересно, сколько же клеток с травой будут затронуты пожаром.

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

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

Устав изобретать велосипед, Леша решил изобрести абсолютно стойкий шифр. Матёрый криптоаналитик Вася прознал, что Лёша использует в своем алгоритме только такие x и y, что l_i ≤ x ≤ r_i и l_j ≤ y ≤ r_j для 1 ≤ i < j ≤ n. Помогите Васе взломать тайное послание Лёши. Для этого найдите количество четвёрок чисел x y i j таких, что количество единиц в двоичном представлении значения нечетно.

 — сложение по модулю 2, исключающее ИЛИ, строгая дизъюнкция, xor, поразрядное дополнение, побитовый комплемент.

Начинающий предприниматель Яша начитался книг по маркетингу и решил дать своей фирме название, которое будет находиться в алфавитном указателе городских организаций как можно раньше. Но администрация города, устав от бесконечных ООО «Абажур», выдала ему в качестве названия случайную строку, в которой необходимо сделать ровно одну модификацию, поменяв местами два любых символа, которые находятся друг от друга на расстоянии, равном любому из любимых чисел главы администрации. Расстояние вычисляется как абсолютная разница позиций символов в строке. Гарантируется, что такая модификация возможна.

Дано множество из n геометрических точек. Пусть выбрана произвольная точка P. Рассмотрим все возможные k невырожденных различных треугольников T_i, образованных точкой P и двумя другими точками из множества. Треугольники считаются различными, если отличаются хотя бы одной вершиной. Строго внутри каждого треугольника T_i (точки на границах не учитываются) лежит m_i точек t_i, j. Покрывающим расстоянием назовем величину , где dist(X, Y) обозначает евклидово расстояние между точками X и Y. Если для точки P не найдется ни одной точки t_i, j, подходящей под описанные выше критерии, то покрывающее расстояние считается равным -1.

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

Устали от длинных, запутанных, неинтересных, скучных сказок и легенд в условиях задач? Эти жалкие попытки авторов условий проявить талант писателя, которого у них отродясь не было... Ничем не объяснимое желание исковеркать кристально чистую, стройную и красивую математическую задачу и прибить ее гвоздями к нашей мрачной действительности... Довольно! В этой задаче вас ждет короткое, ясное и строгое условие.

Задан массив F, состоящий из n целых чисел. Дано m четверок a_i, b_i, c_i, d_i таких, что a_i ≤ b_i, c_i ≤ d_i. Для каждой четверки необходимо вычислить и вывести величину ans_i, равную количеству упорядоченных пар (u, v) таких, что a_i ≤ u ≤ b_i, c_i ≤ v ≤ d_i и F_u = F_v.