Информатика

У Эвана есть любимое число k и массив a_i длины n. Теперь он просит вас ответить на m запросов.

Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor чисел a_i, a_i + 1, ..., a_j равен k.

Входные данные:
В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤ 10⁶) — длина массива, количество запросов и любимое число Эвана соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ a_i ≤ 10⁶) — имеющийся у Эвана массив.
Дальше идут m строк. В i-й строке записаны числа l_i и r_i (1 ≤ l_i ≤ r_i ≤ n), определяющие i-й запрос.

Выходные данные:
Выведите m строк, ответы на запросы в порядке их появления во входных данных.

Примеры:
 

Входные данные	Выходные данные
6 2 3 1 2 1 1 0 3 1 6 3 5	7 0
5 3 1 1 1 1 1 1 1 5 2 4 1 3	9 4 4

Имеется массив натуральных чисел a₁, a₂, ..., a_n. Рассмотрим некоторый его подмассив a_l, a_l + 1, ..., a_r, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через K_s число вхождений числа s в этот подмассив. Назовем мощностью подмассива сумму произведений K_s·K_s·s по всем различным натуральным s. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.

Необходимо вычислить мощности каждого из t заданных подмассивов.

Входные данные
Первая строка содержит два целых числа n и t (1 ≤ n, t ≤ 200000) — длина массива и количество запросов соответственно.
Вторая строка содержит n натуральных чисел ai (1 ≤ a_i ≤ 10⁶) — элементы массива.
Следующие t строк содержат по два натуральных числа l и r (1 ≤ l ≤ r ≤ n) — индексы левого и правого концов соответствующего подмассива.

Выходные данные
Выведите t строк, где i-ая строка содержит единственное натуральное число — мощность подмассива i-го запроса.

Примеры:
 

Входные данные	Выходные данные
3 2 1 2 1 1 2 1 3	3 6
8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7	20 20 20

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).  Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта C в пункт D и из пункта E в пункт F.
В ответе запишите целое число.
 

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K−1). Ведущие нули в числах допускаются.

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A₁ рублей. Те, у кого совпали первые две цифры числа — получают A₂ рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A₃ рублей. И так далее. Угадавшие все число полностью получают Am рублей. При этом если игрок угадал t первых цифр, то он получает A_t рублей, но не получает призы за угадывание t−1, t−2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

Входные данные
В первой строке задаются числа N (количество телезрителей, сделавших свои ставки, 1 ≤ N ≤ 100000), M (длина чисел 1 ≤ M ≤ 10) K (основание системы счисления 2 ≤ K ≤ 10). В следующей строке записаны M чисел A₁, A₂, ..., A_M, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1 ≤ A₁ ≤ A₂ ≤ ... ≤ A_M ≤ 100000). В каждой из следующих N строк записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.

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

Примеры

№	Входные данные	Выходные данные
1	10 3 2 1 3 100 000 000 001 010 100 100 100 100 110 111	011 6
2	1 1 10 100 0	1 0

У вас есть q запросов и мультимножество A, изначально содержащее только число 0. Запросы бывают трёх видов:

• + x — добавить в мультимножество A число x.
• - x — удалить одно вхождение числа x из мультимножества A. Гарантируется, что хотя бы одно число x в этот момент присутствует в мультимножестве.
• ? x — вам даётся число x, требуется вычислить максимальное значение побитового исключающего ИЛИ (также известно как XOR) числа x и какого-нибудь числа y из мультимножества A.

Мультимножество — это множество, в котором разрешается несколько одинаковых элементов.

Входные данные:
В первой строке входных данных содержится число q (1 ≤ q ≤ 200000) — количество запросов, которые требуется обработать Василию.

Каждая из последующих q строк входных данных содержит один трёх символов «+», «-» или «?» и число x_i (1 ≤ x_i ≤ 10⁹). Гарантируется, что во входных данных встречается хотя бы один запрос «?».

Обратите внимание, что число 0 всегда будет присутствовать в мультимножестве.

Выходные данные:
На каждый запрос типа «?» выведите единственное целое число — максимальное значение побитового исключающего ИЛИ для числа x_i и какого-либо числа из мультимножества A.

Пример:
 

Входные данные	Выходные данные
10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11	11 10 14 13

При регистрации в компьютерной системе каждому пользователю присваивается идентификатор фиксированной длины, состоящий из трех частей. Первая часть включает 8 заглавных английских букв (всего английских букв 26); каждый символ кодируется отдельно с использованием минимально возможного количества битов. Вторая часть – целое число от 0001 до 9999, для его кодирования используется минимальное число бит. Третья часть - два любых символа из набора $%^&*#@, каждый из которых также кодируется минимальным числом бит. Для кодирование полного идентификатора выделяется целое число байтов. Кроме того, для каждого пользователя хранятся дополнительные сведения, которые занимают 10 байт. Определите максимальное число пользователей, данные которых можно сохранить, используя 2400 байтов памяти.

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

Скачать файл

Учитель составляет все 7-буквенные слова из букв Э, К, З, А, М, Е, Н и записывает их в алфавитном порядке. 
Вот начало списка:
1. ААААААА
2. ААААААЕ
3. ААААААЗ
4. ААААААК
5. ААААААМ
6. ААААААН
7. ААААААЭ
… …
Под каким номером стоит первое слово, начинающееся на букву К, в котором все буквы различны и при этом гласные и согласные чередуются?
 

На рисунке схема дорог некоторого района изображена в виде графа, в таблице звёздочка обозначает наличие дороги между населёнными пунктами. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера пунктов Д и Е, найденные номера запишите в порядке возрастания без разделителей. Например, если бы ответом были пункты П1 и П6, то в качестве ответа нужно было бы указать 16.
Если возможных ответов несколько, укажите тот, который имеет меньшее числовое значение.

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

– символ «?» означает ровно одну произвольную цифру;

– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

 

Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю.
 

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

 

Формат вывода: для каждого из шести таких найденных чисел в отдельной строке сначала выводится само число, затем – значение М.

Строки выводятся в порядке возрастания найденных чисел.

Квадрат разлинован на N × N клеток (1 < N < 21). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю клетку правее текущей; по команде вниз – в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед каждым запуском Робота он обладает запасом энергии в 1000 единиц. При перемещении Робот тратит такое количество энергии, которое указано в той клетке, куда Робот перемещается. Это также относится к начальной и конечной клеткам маршрута Робота.
Определите минимальный и максимальный запас энергии, который может остаться у Робота при перемещении из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальный запас, затем максимальный.

Исходные данные представлены в форме электронной таблицы размером N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.

Пример входных данных:

Для указанных входных данных при условии, что начальный запас энергии равен 300 единиц, ответом является пара чисел:
73 215

Скачать файл
 

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n <= 2;
F(n) = 4 × F(n − 1) - 2 × F(n − 2) + n, если n > 2 и при этом кратно трем;
F(n) = F(n − 1) - F(n – 2) + n, если n > 2 и при этом не кратно трем.
Чему равно значение функции F(35)?
 

Значение арифметического выражения записали в восьмеричной системе счисления. Сколько раз в данной записи непосредственно слева от меньшей цифры стоит большая?
Например, в записи 76573 данное условие выполняется 3 раза.
 

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 128 символов и содержащий только десятичные цифры и символы из 2040-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме идентификатора, для каждого объекта хранится дополнительная информация.
Известно, что для хранения данных об 1024 объектах потребовалось 376 Кбайт. Сколько Кбайт занимает дополнительная информация обо всех объектах?
В ответе запишите только целое число – количество Кбайт.
 

С помощью текстового редактора определите, сколько отдельных слов «лакей», начинающихся со строчной буквы, встречается в тексте романа Л.Н. Толстого «Анна Каренина». Другие формы слова «лакей», такие как «лакеем», «лакею» и т.д., учитывать не следует.
В ответе укажите только число.

Скачать файл

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

Скачать файл

Все 6-буквенные слова, составленные из букв В, Е, С, Н, А, записаны в алфавитном порядке и пронумерованы.
Вот начало списка:
1. АААААА
2. АААААВ
3. АААААЕ
4. АААААН
5. АААААС
6. ААААВА
… …
Под каким номером стоит последнее слово, в котором есть все буквы из набора, но никакие две одинаковые не стоят рядом?
 

Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится восьмеричная запись числа N.
2. К полученной записи дописываются разряды. Если число четное, справа дописывается 57, если число нечетное – слева дописывается 5 и справа 2.
3. Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Восьмеричная запись числа N: 15.
2. Число нечетное, следовательно слева дописываем 5, справа 2 – 5+15+2 = 5152. Десятичная запись числа 2666
3. На экран выводится число 2666.

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

Для кодирования некоторой последовательности, состоящей из букв А, Н, Т, И, В, Е, С, решили использовать неравномерный двоичный код, гарантирующий однозначное декодирование. Для букв Е и В использовали соответственно кодовые слова 111, 1101. Найдите наименьшую возможную длину кодовой последовательности для слова АТТЕСТАТ.
 

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