Информатика

Реализуйте структуру данных для эффективного вычисления сумм подряд идущих элементов массива.

Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление суммы.

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

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

Ввод	Вывод
5 4 4 8 7 8 2 1 2 1 3	8 16

На плоскости даны N точек. Вам требуется построить выпуклую оболочку данного множества точек. Выведите два числа: периметр и площадь.

Входные данные
Первая строка содержит количество точек N, 1≤N≤10000. Каждая из последующих N строк содержит два целых числа – координаты xi и yi. Все числа по модулю не превосходят 104.

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

Ввод	Вывод
4 0 0 3 4 3 1 6 0	16.0000000000 12.0000000000

Дано N целых чисел. Найти второй по величине максимальный элемент последовательности (элемент, который бы стоял предпоследним, если бы входные данные отсортировали по неубыванию).

Входные данные
В первой строке задается число N (\(2<=N<=10^4\)). Далее идут N строк, в каждой строке по одному целому числу, не превышающему 10⁵ по модулю. 

Выходные данные
Выведите второй максимальный элемент.

 

Примеры

№	Входные данные	Выходные данные
1	7 10 15 20 35 14 35 10	35
2	5 10 5 7 11 9	10

Даны координаты точки (x, y). Выведите на экран слово YES, если точка попадает в заштрихованную область, в противном случае - выведите NO. Точка, расположенная на границе с заштрихованной областью, считается не попавшей в нее.

Входные данные: На вход программе подаются два вещественных числа - координаты точки (x, y)
Выходные данные: Выведите ответ на задачу

 

Примеры

№	Входные данные	Выходные данные
1	0.0 -0.5	NO
2	1.0 1.5	YES

Даны координаты точки (x, y). Выведите на экран слово YES, если точка попадает в заштрихованную область, в противном случае - выведите NO. Точка, расположенная на границе с заштрихованной областью, считается не попавшей в нее.

Входные данные: На вход программе подаются два вещественных числа - координаты точки (x, y)
Выходные данные: Выведите ответ на задачу

 

Примеры

№	Входные данные	Выходные данные
1	0.0 0.0	NO
2	1.0 1.5	YES

Даны координаты точки (x, y). Выведите на экран слово YES, если точка попадает в заштрихованную область, в противном случае - выведите NO. Точка, расположенная на границе с заштрихованной областью, считается не попавшей в нее.

Входные данные: На вход программе подаются два вещественных числа - координаты точки (x, y)
Выходные данные: Выведите ответ на задачу

 

Примеры

№	Входные данные	Выходные данные
1	0.0 1.0	NO
2	1.0 0.5	YES

По данному натуральному \(n >= 2\) вычислите сумму \(1\cdot2+2\cdot3+...+(n-1)\cdot n\). Ответ выведите в виде вычисленного выражения и его значения в точности, как показано в примере.

Входные данные
Вводится одно натуральное число.

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

 

Примеры

№	Входные данные	Выходные данные
1	4	1*2+2*3+3*4=20

Дано натуральное число \(n  <= 10^9,\) определите количество натуральных чисел, меньших \(n\) и взаимно простых с \(n\). Это число обозначается \( f(n) \)и называется фи-функцией Эйлера. Сложность алгоритма должна быть \( O(\sqrt{n})\) .

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

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

 

Примеры

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

Даны целые неотрицательные числа a, b, c, d, при этом (0 <= c <= d) . Выведите в порядке возрастания все числа от a до b включительно, которые дают остаток c при делении на d.
 

Входные данные
Вводятся четыре целых числа  a, b, c, d. Каждое число с новой строки.

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

Примеры

№	Входные данные	Выходные данные
1	2 5 0 2	2 4

Даны два четырёхзначных числа A и B. Выведите в порядке возрастания все четырёхзначные числа в интервале от A до B, запись которых содержит ровно три одинаковые цифры.

Входные данные
Вводятся два целых числа A и B.

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

Примеры

№	Входные данные	Выходные данные
1	1900 2100	1911 1999 2000 2022

Квадрат трехзначного числа оканчивается тремя цифрами, которые образуют число равное исходному числу. Найдите и выведите все такие числа.
Например, одно из таких чисел это число 376² = 141376.

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

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

Пришедших на занятия учеников требуется рассадить за парты. Всего пришло N учеников. За одну парту могут сесть не более L учеников. Какое минимальное число парт потребуется? Написать программу: вводятся два целых числа N и L; вывести одно число - ответ на задачу

Примеры

№	Входные данные	Выходные данные
1	40 10	4

 
 

Даны два четырёхзначных числа A и B. Выведите все четырёхзначные числа на отрезке от A до B, запись которых является палиндромом.

Входные данные
Вводятся два целых числа A и B (\(1000 \leq A,\ B \leq 9999\)).

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

Найдите и выведите все двузначные числа, которые равны удвоенному произведению своих цифр.

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

Выходные данные 
Выведите ответ на задачу (числа выводите в одной строке через пробел в порядке возрастания). 

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

Входные данные 
Вводится одно натуральное число.

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

 

Примеры

№	Входные данные	Выходные данные
1	1	9 7 5 3 1

Даны два целых числа A и В. Выведите все числа от A до B включительно, в порядке возрастания, если \(A < B\), или в порядке убывания в противном случае.

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

Выходные данные 
Выведите ответ на задачу. Числа можете выводить как в строчку через пробел, так и в столбик (способ вывода не важен).
 

 

Примеры

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

Даны натуральные числа a, b, c. Если уравнение \(ax+by=c\) имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите слово Impossible.

Входные данные 
Вводятся три натуральных числа.

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

Примечание
Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.
 

Примеры

№	Входные данные	Выходные данные
1	1 2 3	1 1
2	10 6 8	2 -2

В Хогвартсе проходит традиционная ежегодная олимпиада по теории магии среди младшекурсников. Завхозу школы Аргусу Филчу поручили заняться распределением студентов по аудиториям.

Каждый факультет выставил своих лучших учеников на олимпиаду. От Гриффиндора участвует G студентов, от Слизерина S студентов, Пуффендуй представляет H студентов и Когтевран — R студентов. В распоряжении Филча находится M аудиторий. На аудитории наложено особое заклятие расширения, поэтому при необходимости они могут вместить любое количество студентов. При рассадке необходимо учесть, что ученики одного факультета, находящиеся в одной аудитории, могут, воспользовавшись случаем, начать жульничать, обмениваясь идеями по решению задач. Поэтому в любой аудитории количество студентов с одного факультета, попавших в нее, следует свести к минимуму. Назовем рассадку, удовлетворяющую такому требованию, оптимальной.

Помогите посчитать, какое минимальное количество студентов с одного факультета все же придется посадить в одной аудитории даже при оптимальной рассадке.

Входные данные: В первой строке идут четыре целых числа G, S, H и R (1 ≤ G, S, H, R ≤ 1000) — количество учеников, представляющих каждый из факультетов школы.

Во второй строке идет целое число M (1 ≤ M ≤ 1000) — количество классов в распоряжении у Филча.

Выходные данные: Выведите минимальное количество студентов с одного факультета, которое Филчу придётся посадить в одну аудиторию даже при оптимальной рассадке.
Примеры

№	Входные данные	Выходные данные
1	4 3 4 4 2	2
2	15 14 13 14 3	5