Алгоритмы

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

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

Суперкомпьютер имеет 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

В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 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

 

Однажды, Вася взял без спроса у бабушки пульт от телевизора и выбежал во двор с прямого хода. Радиус двора - R метров. Прямой путь от парадного выхода до калитки - хорда AB, являющаяся диаметром этой окружности. Добежав до центра окружности, он увидел деда выскочившего ему наперерез. Василий принял решение сбежать через дырку в заборе. Но чтобы не портить бабушкины цветы и тем самым не добить её своим поступком, он подумал что лучше всего бежать по дорожкам. На картинке они обозначены.

Близжайщая тропинка ведущая до дырки - AC, к ней от центра ведёт дорожка ОН. 
 

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

1 < R < AC < 10^18

Входные данные:

10 16

24.000

(с) Медведев Д., 2018

Однажды на огород к Ивану Петровичу (сыну Деда Мороза и Снегурочки) забежало целых три оленя. Известно, что олени — весьма агрессивное нечто, особенно когда речь идет о борьбе за вкусную зелень. Поэтому каждый из трех оленей, заметив других козлов, замер на месте и начал наблюдать за оставшимися оленями: одним глазом за одним оленем, другим — за оленем номер 2. Естественно, для этого оленю нужно “косить” глазами.

Определите наибольший угол, на который пришлось “раскосить” глазами этим странным животным. Причём тут Иван Петрович и мы, и как олени “раскосили” глаза, мы в душе не знаем. Своего дилера мы не сдадим.

Программа получает на вход координаты трех точек, в которых стоят олени (сначала координаты первого оленя, затем — второго и третьего). Координаты — пара целых чисел, не превосходящих 104 по модулю.
 

Ввод	Вывод
0 0 3 0 0 4	90.000000

 

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.

 

Входные данные: 
- в первой строке задается сумма S;
- во второй строке - число N;
- в третьей строке  - N чисел P1, P2, ..., PN;
- в четвертой строке - число M;
- в пятой строке - M чисел Q1, Q2, ..., QM.
Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

 

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

Если они не могут рассчитаться, выведите строку Impossible.

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

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

fhb5kbfыshfm.

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

b2

f3

h2

k1

m1

s1

Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, какое число чаще всего записывала Снегурочка. Дед Мороз и Снегурочка – волшебные, поэтому число утренников N, на которых они побывали, может быть очень большим. Напишите программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Желательно, чтобы программа была эффективной как по времени работы, так и по используемой памяти. Программу будем считать эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программу будем считать эффективной по времени, если при увеличении размера входных данных N в t раз (t – любое число) время её работы увеличивается не более чем в t раз.

 

Входные данные

В первой строке вводится одно целое положительное число – количество утренников N. Каждая из следующих N строк содержит два целых числа: сначала D – количество пришедших на очередной утренник детей, а затем K – количество конфет в мешке Деда Мороза на этом утреннике. Гарантируется выполнение следующих соотношений: 1 ≤ N ≤ 10000, 1 ≤ D ≤ 100 (для каждого D), D ≤ K ≤ 1000 (для каждой пары D, K)

 

Выходные данные

Программа должна вывести одно число – то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.

Ввод	Вывод
7 10 58 15 315 20 408 100 1000 32 63 32 63 11 121	31

Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

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

Одно целое число N (1 <= N <= 10⁹).

 

Выведите одно целое число - N-й элемент последовательности.
 

Ввод	Вывод
1	1
4	5

Дано N отрезков провода длиной L₁, L₂, ..., L_N сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.

 

Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= L_i <= 10 000 000, все числа целые.

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

 

В первой строке находятся числа N и К. В следующих N строках - L₁, L₂, ..., L_N, по одному числу в строке.

 

Вывести одно число - полученную длину отрезков.
 

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

 

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

 

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

 

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

 

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

 

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

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

 

Входные данные

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X (1 ≤ A, B ≤ 109 , 2 ≤ K, M ≤ 1018, 1 ≤ X ≤ 1018).

 

Выходные данные

Выходной файл должен содержать одно целое число — искомое количество дней.

Ввод	Вывод
2 4 3 3 25	7

Дан набор гирь массой m­1, …, mN. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?

 

- в первой строке вводится натуральное число N, не превышающее 100;

- во второе строке вводятся N натуральных чисел mi, не превышающих 100.

 

Выходные данные: выведите YES или NO.

Дано N предметов массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?

 

- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второе строке вводятся N натуральных чисел mi, не превышающих 100.

 

Выходные данные: выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.

Дано N золотых слитков массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота можно унести в таком рюкзаке?

 

Входные данные: 
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второй строке вводятся N натуральных чисел mi, не превышающих 100.

 

Выходные данные: выведите одно целое число - наибольшую возможную массу золота, которую можно унести в данном рюкзаке.

Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно. 

Ими наполняют рюкзак, который выдерживает вес не более M. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.

 

Входные данные: 
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второй строке вводятся N натуральных чисел mi, не превышающих 100;

- в третьей строке вводятся N натуральных чисел сi, не превышающих 100.

 

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

Маленькому Арсению на кружке по системам счисления задали следующую задачу: перевести число X в системе счисления s1 в систему счисления s2. Недолго думая, он позвал на помощь своего лучшего друга Добрыню, который славился тем, что замечательно умел считать до 10 на пальцах. После нескольких бессонных ночей ребята общими усилиями справились с задачей.

 

Однако, на следующем занятии Арсению задали похожую задачу, где X, к сожалению, превышало 10. Тогда ребята решили обратиться в Летнюю Компьютерную Школу с просьбой написать универсальную программу, которая решает задачу для любых X, s1 и s2. Ваша цель – выполнить просьбу Арсения и Добрыни.

 

Во входных данных вашей программе дается 3 числа: исходное число X, основания систем счисления s1 и s2 (\(2  <=  s1,\ s2  <=  10\)). Число X в десятичной системе счисления не превышает \(2 \cdot 10^9\).

 

В выходных данных должно находиться одно число, равное числу X в системе счисления s2, или -1, если входные данные некорректны.

 

 

Примеры

№	Входные данные	Выходные данные
1	101 2 10	5
2	200 2 10	-1

 

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

 

В первой строке входного файла указано число N (0≤N≤1500). В следующих N строках заданы по 4 целых числа x1, y1, x2, y2 — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего (0≤x1≤x2≤10⁹, 0≤y1≤y2≤10⁹). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.

 

В выходной файл выведите единственное число — ответ на задачу.
 

Ввод	Вывод
3 1 1 3 5 5 2 7 4 2 4 6 7	23
2 0 0 2 2 1 3 2 4	5

На прямой задано некоторое множество отрезков с целочисленными координатами концов \([L_i, R_i]\). Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок \([0, M]\), (M — натуральное число), содержащее наименьшее число отрезков.

 

В первой строке указана константа M (\(1<=M<=5000\)). В каждой последующей строке записана пара чисел Li и Ri (\(|L_i|,|R_i| < 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.

 

В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка \([0; M]\). Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка \([0; M]\) исходным множеством отрезков \([L_i, R_i]\) невозможно, то следует вывести единственную фразу “No solution”.

 

Примеры

№	Входные данные	Выходные данные
1	1 -1 0 -5 -3 2 5 0 0	No solution
2	1 -1 0 0 1 0 0	1 0 1