Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Разбиения на сумму нечетных#26985

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

Например, число 6 можно разложить на слагаемые следующими способами: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5.

Формат ввода

На вход подается число n (1 n 1000).

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

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

Пример

Ввод	Вывод
6	4

Примечания

Разбиение, состоящее из одного слагаемого, также считается разбиением.

Динамическое программирование: один параметр

✓ 2✗ 371 100средняяВойти и решать

Разбиение на пары#26982

Мария Ивановна написала на доске четыре числа: a, b, c и d. После чего предложила своему классу разбить эти числа на две пары так, чтобы сумма произведений чисел в парах была максимальна.

Например, если на доске написаны числа 5, 6, 7 и 8, то оптимально разбить их на пары (5, 6) и (7, 8), в этом случае искомая сумма равна 5 × 6 + 7 × 8 = 86.

Формат ввода

На вход подаются четыре целых числа: a, b, c и d. Все числа по модулю не превышают 1000.

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

Выведите искомую максимальную сумму.

Пример

Ввод	Вывод
5 6 7 8	86

Линейные алгоритмы

✓ 59✗ 65500лёгкаяВойти и решать

2048#26981

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

Напомним правила игры 2048. На поле 4 × 4 разбросаны числа, являющиеся степенями двойки от 2 до 1024, некоторые клетки могут быть пустыми. Каждый ход игрок может сдвинуть все плитки игрового поля в одну сторону. Если при сдвиге две плитки одного номинала «налетают» одна на другую, то они слипаются в одну, номинал которой равен сумме соединившихся плиток. За каждое соединение игровые очки увеличиваются на номинал получившейся плитки. Плитка, получившаяся при слипании двух других, не может больше участвовать в слипании.

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

Программа получает на вход четыре строки, в каждой из которых записано четыре числа. Числа являются степенями двойки от 2 до 1024. В некоторых клетках записано число 0, означающий, что данная клетка пуста.

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

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

Примеры

№	Входные данные	Выходные данные
1	2 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0	4
2	2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0	8
3	2 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0	4
4	2 2 4 0 0 2 2 2 0 2 4 0 2 4 4 0	16

Примечания

Внимательно прочитайте этот раздел для лучшего понимания правил игры.

Наилучший ответ на первый тест достигается движением вниз.
0 0 0 0
0 0 0 0
2 0 0 0
4 0 0 0

Наилучший ответ на второй тест достигается движением вниз.
0 0 0 0
0 0 0 0
4 0 0 0
4 0 0 0

Наилучший ответ на третий тест достигается движением влево.
4 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Наилучший ответ на четвертый тест достигается движением вниз.
0 0 0 0
0 2 4 0
0 4 2 0
4 4 8 2

Двумерные массивы

✓ 5✗ 161 000средняяВойти и решать

Бумага для олимпиады#26980

Лёлик решил провести у себя в школе олимпиаду. Для этого ему необходимо закупить много упаковок бумаги. Лёлику очень повезло, потому что один крупный канцелярский магазин объявил две рекламных акции: «купи A одинаковых товаров и получи еще один товар бесплатно», а также «купи B товаров по цене B-1 товара».

Лёлик узнал, что одна пачка бумаги в этом магазине стоит n рублей. Теперь он хочет определить сколько упаковок бумаги он сможет купить на p рублей. Помогите ему.

Формат ввода

На вход подаются четыре натуральных числа, разделенных пробелом: A, B, p и n (1 ≤ A ≤ 100, 2 ≤ B ≤ 100, 1 ≤ p, n ≤ 10000).

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

Выведите единственное целое число — максимальное количество упаковок бумаги, которое сможет купить Лёлик.

Пример

Ввод	Вывод
4 4 13 2	8
3 4 8 3	2
3 4 7 1	9

Примечания

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

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

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

Вывод формулы

✓ 28✗ 170900средняяВойти и решать

Логические выводы#26979

Болик решает логическую задачу. Для ее решения, он сначала сделал N базовых предположений. После этого происходит следующий процесс: Холмс разбивает все предположения на пары, из каждой пары отбрасывает наименее вероятное предположение (предположения таковы, что всегда есть наименее вероятное). Если получилось так, что какому-то предположению, пары не хватило, то Болик оставляет его для рассмотрения. Алгоритм повторяется пока у Болика не останется последнее предположение.

Болик также привык считать количество логических выводов, которое он сделал. Так, например, если рассматриваются 11-ое и 31-ое предположение и отбрасывается 11-ое, то Болик совершил один логический вывод. Если, например, 238-ому предположению не хватило пары, то Болик оставляет его для рассмотрения, но, конечно, не считает это действие за логический вывод. Более того, последний вывод Болик проверяет дважды.

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

Формат ввода

На вход подается натуральное число N (1 ≤ N ≤ 10²¹⁸) — количество базовых предположений.

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

Выведите единственное целое число — количество логических выводов.

Пример

Ввод	Вывод
3	3

Вывод формулы

✓ 33✗ 222800средняяВойти и решать

Максимальная сумма, не делящаяся на 4#25980

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

В результате программа должна вывести количество выбранных чисел и их сумму. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

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

На вход программе подаётся натуральное число N (\(N <= 1000\)), а затем N натуральных чисел, каждое из которых не превышает 10000.

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

Программа должна вывести два числа: сначала количество выбранных чисел, а затем их сумму.

Примеры

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

ЕГЭ - вычислительные задачи

✓ 484✗ 907500лёгкаяВойти и решать

Выборка чисел для максимальной суммы, кратной 4#25979

Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел была кратна 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Входные данные
На вход программе в первой строке подаётся количество троек N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

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

Примеры

№	Входные данные	Выходные данные
1	6 8 3 4 4 8 12 9 5 6 2 8 3 12 3 5 1 4 12	88

ЕГЭ - вычислительные задачи

✓ 208✗ 2 3191 000средняяВойти и решать

Задача#25974

Для чего производится описание массивов?

1) чтобы самому запомнить сколько ячеек в массиве
2) чтобы компьютер запомнил имя массива
3) чтобы компьютер зарезервировал память для хранения элементов массива
4) чтобы компьютер зарезервировал количество энергии для обработки массива

Одномерные массивы

300лёгкаяВойти и решать

Одномерные массивы. Введение#25971

В программе измените объявление массива таким образом, чтобы массив состоял из 30 элементов.

Линейные структуры

✓ 3 387✗ 1 567100лёгкаяВойти и решать

По мотивам ЕГЭ 2017#25970

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (a_i, a_j) этого набора, в которых \(1 <= i < j <= N\) и произведение элементов кратно 14.
Напишите эффективную по времени и по памяти программу для решения этой задачи.

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

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

Примеры

№	Входные данные	Выходные данные
1	5 14 7 7 2 19	6

ЕГЭ - вычислительные задачи

✓ 483✗ 678500лёгкаяВойти и решать

3-ий минимум#25969

От цифровых датчиков в компьютер поступает информация о характеристиках физического процесса. Результатом каждого измерения является целое число.

Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет выводить третье по величине (считая от минимума) значение измерения. Если несколько измерений имеют одинаковые значения, то они учитываются как одно измерение. Если искомого значения не существует (например, когда все значения измерений равны), то нужно вывести символ "#". Следует учитывать, что количество измерений может быть очень велико.

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

Примеры

№	Входные данные	Выходные данные
1	5 100 10 100 10 100	#

ЕГЭ - вычислительные задачи

✓ 271✗ 631600лёгкаяВойти и решать

Дипломы#25961

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причём, как оказалось, все они имели одинаковые размеры: w — в ширину и h — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w на h. Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Входные данные: на вход подаются три целых числа: w, h, n (\(1<=w,\ h,\ n <= 10^9\) ).

Выходные данные: необходимо вывести ответ на поставленную задачу.

Примеры

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

Бинарный поиск по ответу

✓ 926✗ 1 884500лёгкаяВойти и решать

Левый и правый двоичный поиск#25960

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

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

В первой строке входных данных записано два числа N и M (\(1<=N,\ M <=20000\)). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка.
Все числа в списках - целые 32-битные знаковые.

Формат входных данных
Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Бинарный поиск в массиве

✓ 849✗ 1 683600лёгкаяВойти и решать

Слажал - отжался#25917

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

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

В первой строке число содержится число N (2 <= N <= 1000) количество детей в классе. В

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

обозначает рост i-го школьника r_i (1 <= r_i <= 10⁹) в нанометрах.

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

Одно число суммарное количество отжиманий. Гарантируется, что школьники суммарно отожмутся не более 2 · 10⁹ раз.

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

Замечание

В примере школьники с ростом 1 и 2 поменяются местами и каждый отожмјтся по разу, затем школьники 1 и 3 (каждый отжимается 2 раза, суммарно плюс 4 отжимания), и последними школьники 2 и 3 (плюс 2 отжимания).

Использование сортировки реализация

✓ 194✗ 273400лёгкаяВойти и решать

Очень Важный Объект#25916

Антон сторож на очень важном объекте. Как и положено всем важным объектам, он обнесён забором. Правда, время не пощадило этот забор, и в нём есть дыры, через которые на объект могут попадать нарушители.

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

Поняв, что, если на объект будет попадать слишком много нарушителей, Антон решил взять инициативу в свои руки и заделать некоторые дыры. Для этого он попросил у начальства моток колючей проволоки. Полученный им моток из l метров колючей проволоки нужно будет потом вернуть в целости, поэтому Антону запрещено его резать. Антон может закрепить один из концов мотка с проволокой в любом месте на границе объекта.

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

Формат входных данных
В первой строке входного файла содержится три целых числа n (3 <= n <= 10⁵) количество столбов в заборе, l (0 <= l <= 10¹⁸) длина выданного Антону мотка проволоки и k (0 <= k <=n/2) количество дыр в заборе.

Во второй строке по возрастанию заданы k чисел a_i (1 < a_i <= n). Числу ai соответствует отсутствие секции забора между столбами a_i и a_i+1 mod n. Гарантируется, что из двух соседних секций хотя бы одна не отсутствует.

В следующих n строках находится по два целых числа x_i и y_i (|xi| <= 10¹⁸, |y_i| <= 10¹⁸) координаты i-го столба забора. Многоугольник может быть задан в порядке обхода как по, так и против часовой стрелки.

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

Выведите единственное число минимальную суммарную длину дыр в заборе после установки колючей проволоки. Ответ будет считаться правильным, если если он отличается от правильного не более, чем на p · 10^?6

, где p периметр многоугольника.

Примеры

Ввод	Вывод
6 4 3 1 3 5 0 0 3 0 4 1 3 2 0 2 -1 1	2.82842712474619

геометрия Задачи на моделирование реализация

✓ 8✗ 561 000средняяВойти и решать

Эвакуация#24913

Через T минут армия читаури под предводительством Локи атакует Землю. Мстители никак не успевают помешать открытию портала в Нью-Йорке, поэтому Капитан Америка принял решение эвакуировать из города всех его жителей. Ему необходимо выяснить, успеют ли жители города эвакуироваться до начала вторжения.

Окрестности Нью-Йорка можно представить как набор небольших городов, связанных между собой дорогами с односторонним движением. Каждая дорога характеризуется своей длиной и пропускной способностью. Длина дороги l означает, что въехав на нее в момент времени t, автомобиль окажется в конце этой дороги через l минут, в момент времени t + l. Пропускная способность дороги s означает, что каждую минуту на эту дорогу могут въехать не больше, чем s автомобилей. Приехав в какой-нибудь город, любой автомобиль может сразу продолжить путь, въехав на какую-то дорогу, выходящую из этого города, а может остановиться в этом городе на любое количество минут, и только потом уехать из него.

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

Формат входного файла

Первая строка входного файла содержит четыре целых числа n, m, K и T (1 ≤ n x T ≤ 10 000, 1 ≤ m, K ≤ 10 000) количество городов в окрестностях Нью-Йорка, количество дорог между ними, количество автомобилей, которым необходимо попасть из Нью-Йорка в безопасный город и время до вторжения захватчиков соответственно. Следующие m строк содержат описания дорог между городами.

Каждая дорога описывается четырьмя целыми числами u, v, l и s (1 ≤ u, v ≤ n, u != v, 1 ≤ s ≤ 3 000, 1 ≤ l ≤ 200) город, из которого выходит эта дорога, город, в который она ведет, ее длина и пропускная способность соответственно.

Между двумя городами может существовать только одна дорога, ведущая в каком-то направлении. Нью-Йорком считается город с номером 1, а безопасным городом город с номером n. в момент времени 0 все автомобили находятся в Нью-Йорке.

Формат выходного файла

Если все жители Нью-Йорка успеют добраться до безопасного города не более, чем за T минут, выведите в выходной файл минимальное количество минут, которое им на это понадобится. В противном случае выведите минимальное количество автомобилей, которым не удастся попасть в безопасное место за T минут. Да, не нужно выводить, какой из этих случаев имеет место :-).

Ввод	Вывод
5 5 10 10 1 2 2 2 2 3 1 1 2 4 1 1 4 5 2 4 3 5 2 4	9

Обход в глубину

✓ 0✗ 61 300средняяВойти и решать

Тессеракт#24912

Коварный Локи напал на Землю, использовав Тессеракт для того, чтобы переместиться из Асгарда. Понимая ценность этого артефакта, он решает защитить его от использования кем-либо, кроме себя. Для этого он решает немного изменить его внутреннюю структуру так, чтобы только он знал, как её можно восстановить.

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

Всего цепочка, которую собирается менять Локи, состоит из \(n\) кубиков. Среди них есть похожие, на чём и собирается сыграть Локи. Он берёт какой-то отрезок кубиков в этой цепочке, вырывает его, разворачивает и вставляет обратно. При этом, он выбирает отрезок таким образом, чтобы внешне цепочка не изменилась. Затем он повторяет то же самое с другим отрезком, который содержал в себе первый, но не совпадал с ним. Очевидно, после этих двух операций цепочка уже не будет совпадать с исходной, и артефакт будет испорчен.

Чтобы оценить вероятность быть уличённым в порче Тессеракта, Локи решил выяснить, сколькими способами он мог выбрать первый отрезок.

Рассмотрим, к примеру, цепочку \(aabaa\), в которой одинаковыми буквами обозначены похожие кубики. Тогда настоящий Тессеракт содержит цепочку \(a_1a_2ba_3a_4\). Локи может, например, проделать следующую последовательность действий: \(a_1a_2ba_3a_4 \to a_2a_1ba_3a_4 \to a_4a_3ba_1a_2\). Внешне ничего не изменилось, однако цепочка уже другая.

Формат входных данных
В первой и единственной строке задана цепочка, состоящая из маленьких латинских букв, длиной не более \(100{\,}000\).

Формат выходных данных
Единственное число — количество различных первых действий Локи.

Z-функция. Префикс-функция

✓ 0✗ 51 200средняяВойти и решать

Держать строй#24911

Ник Фьюри решил, что бойцы отряда спецназа, являющегося подразделением организации S.H.I.E.L.D., помогут мстителям отразить атаку войска Локи. Он решил, что в бой отправятся n бойцов, а все остальные понадобятся в других местах. Теперь ему осталось только выбрать, какие именно бойцы пойдут в атаку.

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

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

Формат входного файла

Первая строка входного файла содержит два числа n и m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000) количество солдат в строю и количество команд, которые подаст Ник. Вторая строка содержит n целых неотрицательных чисел, не превосходящих 10⁹ исходный рост солдат в строю. Следующие m строк содержат команды, подаваемые Ником. Если первый символ в строке, описывающей очередную команду, '!', то за ним следуют два числа k и x (1 ≤ k ≤ n, 0 ≤ x ≤ 10⁹), где k место в строю того солдата, которого должен заменить солдат роста x. Команда второго типа описывается знаком '?'.

Формат выходного файла

Для каждой команды второго типа в отдельной строке выведите "YES", если в данный момент солдаты в строю стоят по неубыванию роста, и "NO" в противном случае.

Ввод	Вывод
5 5 2 4 6 8 10 ? ! 2 7 ? ! 3 8 ?	YES NO YES

Задача на реализацию

✓ 11✗ 56900средняяВойти и решать

Поймать Халка#24910

Когда Локи ловил Халка, он немного не рассчитал своих сил, и случайно перенес его в параллельный n-мерный мир. После этого Локи намертво вморозил Халка в глыбу льда. Для окончательной победы Локи необходимо только отпилить от глыбы лишний лед так, чтобы остался только сам замороженный Халк. Пространство, в которое Локи перенес все происходящее, не более чем трехмерно. В одномерном пространстве глыба представляет из себя отрезок некоторой длины, а Халк внутри вложенный в него отрезок. В двумерном пространстве глыба и Халк прямоугольники со сторонами, параллельными оcям координат, причем Халк вложен в глыбу. Аналогично, в трехмерном пространстве глыба и Халк являются параллелепипедами со сторонами, параллельными осям координат.

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

Формат входного файла

Первая строка входного файла содержит одно число n (1 ≤ n ≤ 3) количество измерений в пространстве, в котором происходит действие. Следующая строка содержит n натуральных чисел ai (1 ≤ a_i ≤ 10000) координаты одной из вершин глыбы. Будем считать, что вершина глыбы, противоположная данной, находится в начале координат.

В следующей строке сначала перечислены n целых чисел b_i (0 ≤ b_i ≤ a_i) координаты одной из вешин Халка, затем еще n целых чисел ci (0 ≤ c_i ≤ a_i) координаты противоположной вершины Халка.

Формат выходного файла

Выведите единственное целое число минимальное количество разрезов, которые необходимо

сделать Локи, чтобы выпилить Халка.

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

Задача на реализацию

✓ 12✗ 18800средняяВойти и решать

НОД и НОК#24905

Дано число n – количество чисел. В следующей строке дано n чисел, каждое не больше 1000.
Вам необходимо вывести количество таких пар чисел (a, b), что НОК (a, b) = НОД (a, b).

НОК (a, b) - наименьшее общее кратное этих двух чисел, то есть наименьшее число, которое делится сразу на оба числа. \( НОК (20, 30) = 60\).
НОД (a, b) – наибольший общий делитель этих двух чисел, то есть наибольшее число, на которое делятся оба числа. \(НОД (20, 30) = 10\).
Напишите эффективную по памяти и времени программу.

Входные данные
В первой строке вводится натуральное число n – количество данных вам чисел.
Во второй строке вводятся сами числа, каждое из них целое и принадлежит отрезку [0; 1000].

Выходные данные
Выведите одно целое число – количество пар чисел (a, b), таких, что НОК(a,b) = НОД(a,b).

Примеры

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

НОД и алгоритм Евклида

✓ 636✗ 2 555600лёгкаяВойти и решать