Типы данных

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0+ 1, 0+ 1+ 3, 0+ 1+ 3+ 5,

. . . , 0 + 1 + 3 + . . . + (2n − 1), . . ., составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, . . . , n², . . ..

Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k + 1, k + 1 + 3, k + 1 + 3 + 5, . . . ,k+ 1+ 3+. . .+ (2n−1), . . ..  В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.

Требуется написать программу, которая по заданному целому числу k определяет, квадрат какого минимального неотрицательного целого числа встречается в описанной последовательности,

либо выясняет, что в ней вообще не встречается полных квадратов.

Формат входных данных

В единственной строке содержится целое число k — начальное число в последовательности

(−10¹² <= k <= 10¹²).

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

Формат выходных данных

Выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной

последовательности. Если в последовательности не встречается квадратов целых чисел, выведите

«none».
 

Ввод	Вывод
0	0
-5	2
2	none

 

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

позволяющая эффективно обрабатывать большие объемы данных.

Суперкомпьютер имеет 2^k ячеек памяти, пронумерованных от 0 до 2^{k– 1}. Отрезком

[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,

включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является

корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.

Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются

отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,

6] и [7, 7].

Ключевой операцией в новой архитектуре является операция STORE, которая за одно

действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного

отрезка.

Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить

на суперкомпьютере программу обработки данных, но перед её запуском необходимо

инициализировать память определенным образом. А именно: первые с1 ячеек памяти

необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,

последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо

выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое

содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для

инициализации памяти достаточно трех операций STORE:

- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;

- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];

- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],

как и требуется.

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не

является корректным отрезком памяти.

Требуется написать программу, которая по заданному содержимому памяти

определяет минимальное количество операций STORE, которое необходимо выполнить для

инициализации памяти заданным образом.

Ввод	Вывод
3 3 2 1 1 2 2 5 1	3

В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.

Выполняется один или несколько шагов по удалению чисел в этом ряду. На

очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.

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

Например, пусть n = 13, k = 2.

- На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.

- На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.

- На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.

- На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.

Таким образом, число 13 будет удалено на третьем шаге.

Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n.

Первая строка входных данных содержит целое число n (3 ≤ n ≤ 10¹⁸).

Вторая строка входных данных содержит целое число k (2 ≤ k ≤ 100, k < n).

Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.
 

Ввод	Вывод
13 2	3

 

В современном многоэтажном офисе крупной компании установлен новый лифт. В

компании работает n сотрудников. Для проверки эффективности системы управления

лифтом требуется провести моделирование его работы в конце рабочего дня, когда все

сотрудники должны покинуть здание и спуститься на первый этаж.

В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й

сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.

На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной

сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван,

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

с ним лифт могут ожидать и другие сотрудники.

В каждый момент времени не более одного вызова является активным.

Изначально лифт свободен и находится на первом этаже. Когда поступает первый

вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если

несколько вызовов поступает одновременно, активным становится вызов от сотрудника с

меньшим номером.

Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт

оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже

ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один

этаж в секунду.

При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов

на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него

и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все

люди выходят из лифта, а лифт ожидает следующего вызова.

Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов,

активируется вызов, который поступил раньше других. Если несколько вызовов поступило

одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает

обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.

Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду

сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия

(лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается

решение, на какой вызов лифт должен отреагировать).

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

сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.

Формат входных данных

Первая строка входных данных содержит целые числа n и m — количество людей,

вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 10⁵, 2 ≤ m ≤ 10⁹).

Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых

числа ti и ai — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на

котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 10⁹, 2 ≤ ai ≤ m)

 

Выходные данные должны содержать n целых чисел, для каждого сотрудника

требуется вывести секунду, в которую он выйдет из лифта на первом этаже.
 

Ввод	Вывод
5 4 2 3 2 4 5 2 5 3 9 3	6 12 6 12 12

 

Пример работы лифта по шагам показан в следующей таблице. 


Использованные в пояснении к примеру обозначения

В лаборатории теории чисел одного университета изучают связь между

распределением квадратов и кубов натуральных чисел.

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных

чисел от a до b, включительно. Будем называть k-плотностью этого множества количество

пар натуральных чисел x и y, таких, что a ≤ x² ≤ b, a ≤ y³ ≤ b, причем |x²– y³| ≤ k.

Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как

подходят следующие пары:

Требуется написать программу, которая по заданным натуральным числам a и b, а

также целому неотрицательному числу k, определяет k-плотность множества натуральных

чисел от a до b, включительно.

Входные данные содержат три строки. Первая строка содержит натуральное число a,

вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное

число k (1 ≤ a ≤ b ≤ 10¹⁸, 0 ≤ k ≤ 10¹⁸).

Выходные данные должны содержать одно целое число: искомую k-плотность

множества натуральных чисел от a до b, включительно.

 

Ввод	Вывод
1 30 2	3

В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 2 до 5. Итоговая оценка по информатике выставляется как среднее арифметическое оценок на всех уроках, округленное до ближайшего целого числа. Если среднее значение находится ровно посередине между двумя целыми числами, то оценка округляется вверх.

Примеры округления оценок приведены в таблице.
 

Оценки на уроках	Среднее арифметическое	Итоговая оценка
2, 3, 5	\({ {2 + 3 + 5} \over 3 }= 3 {1 \over 3}\)	3
3, 3, 4, 4	\({ {3 + 3 + 4 + 4} \over 4 }= 3 {1 \over 2}\)	4
5, 5, 5, 3, 5	\({ {5 + 5 + 5 + 3 + 5} \over 5 }= 4 {3 \over 5}\)	5

 

Ввод	Вывод
2 0 0	2

 

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

 

Входные данные: Вводится список целых чисел. Все числа списка находятся на одной строке. Всего чисел не более 100000.

Выходные данные: Выведите ответ на задачу.

 

Примеры

№	Входные данные	Выходные данные
1	1 2 3 2 1	3

 

Напишите программу, которая будет выполнять последовательность запросов вида ADD num, PRESENT num и COUNT (без параметра). Программу обязательно следует писать с использованием шаблонного типа set.

 

Выполнение каждого запроса вида ADD num должно добавлять элемент num во множество (если такой элемент уже есть, добавление ещё одной копии не изменяет множество), на экран при этом ничего не выводится.

 

При выполнении каждого запроса вида PRESENT num должно выдаваться сообщение «YES» или «NO» (большими буквами, в отдельной строке), соответственно тому, есть ли такой элемент во множестве; значение множества при этом не изменяется.

 

При выполнении каждого запроса вида COUNT должна выдаваться на экран в отдельной строке текущее количество различных элементов в множестве; значение множества при этом не изменяется.

 

В первой строке стандартного входного потока задано количество запросов N (1 < N < 100000), далее следуют N строк, каждая из которых содержит по одному запросу согласно описанного формата.

 

Значения чисел не превышают по модулю 100000000.

 

Выводите на стандартный выход (экран) в отдельных строках результаты запросов PRESENT и COUNT; на запросы ADD ничего выводить не надо.

 

Примеры

№	Входные данные	Выходные данные
1	7 ADD 5 ADD 7 COUNT PRESENT 3 PRESENT 5 ADD 3 COUNT	2 NO YES 3

На вход программы подаются произвольные алфавитно-цифровые символы. Ввод этих символов заканчивается точкой. Требуется написать программу, которая будет печатать последовательность строчных английских букв ('a' 'b'... 'z') из входной последовательности и частот их повторения. Печать должна происходить в алфавитном порядке.

Например, пусть на вход подаются следующие символы:

fhb5kbfыshfm.

В этом случае программа должна вывести

b2

f3

h2

k1

m1

s1

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

Помогите ему решить эту задачу. 
 

Входные данные
Первая строка входных данных содержит общее количество ценников N, 2 <= N <= 10⁵, N – чётное число. Следующие N строк содержат целые положительные числа, не превосходящие 10⁹, идущие в порядке неубывания по одному в строке – числа, записанные на всех ценниках (как старых, так и новых). Гарантируется, что входные данные корректны,то есть решение существует.

Выходные данные
Программа должна вывести N/2  целых чисел в порядке неубывания – стоимости товаров после понижения цен.

 

Примеры

№	Входные данные	Выходные данные	Примечание
1	6 30 40 42 45 56 60	30 42 45	До распродажи цены товаров были 40, 56, 60, после снижения цены на эти товары стали равны 30, 42, 45.

Геном жителей системы Тау Кита содержит 26 видов оснований, для обозначения которых будем использовать буквы латинского алфавита от A до Z, а сам геном записывается

строкой из латинских букв. Важную роль в геноме играют пары соседних оснований, например, в геноме «ABBACAB» можно выделить следующие пары оснований: AB, BB, BA,

AC, CA, AB. 

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

Вам даны два генома, определите степень близости первого генома второму геному.

Программа получает на вход две строки, состоящие из заглавных латинских букв. Каждая строка непустая, и её длина не превосходит 10⁵.

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

Ввод	Вывод	Примечание
ABBACAB BCABB	4	Следующие пары оснований первого генома встречаются во втором геноме: AB, BB, CA, AB. Обратите внимание на то, что пара AB в первом геноме встречается два раза, поэтому и подсчитана в ответе два раза.