Решения задач по предмету Информатика

Предмет: Информатика, автор: n1mekdep
Предмет: Информатика, автор: zavinskan2000
Предмет: Информатика, автор: molika1986m
Задача A. Баука и Гора Великих Чисел
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Баука любит прогуливаться по утрам, из-за этого с восходом солнца он пошел на гору Великих
Чисел. С собой он взял любимый массив из N элементов, где i-е число равно ai
. Баука хочет найти
великое число для своего массива.
Число x считается великим, если для него выполняется такое условие, что НОД(ai+x, aj +x) = 1
для всех 1 6 i < j 6 N.
Числа на горе представлены в виде Q запросов. В каждом запросе дается одно число. Помогите
Бауке определить, будет ли данное число великим для его массива.
Формат входных данных
В первой строке находятся два целых числа N и Q (2 6 N 6 105
, 1 6 Q 6 104
) - количество
чисел и запросов.
Во второй строке находятся N целых числа a1, a2, · · · , an (1 6 ai 6 105
).
В следующих Q строках дано по одному целому числу x (1 6 x 6 105
).
Формат выходных данных
На каждый из Q запросов выведите «YES», если число является великим, иначе выведите «NO».
Система оценки
Подзадача Дополнительные ограничения Баллы Необходимые подзадачи
0 Примеры 0 —
1 N = 2 20
2 N, Q 6 100 23 0
3 N, Q, ai
, x 6 104 27 0, 2
4 — 30 0, 1, 2, 3
Пример
стандартный ввод стандартный вывод
5 2
1 13 4 7 9
4
11
YES
NO
Замечание
Рассмотрим первый запрос. После того как мы добавим 4 к каждому числу у нас получится массив: 5 17 8 11 13. Если мы возьмем НОД(Наибольший общий делитель) каждой пары из полученного
массива то он не превысит 1, значит ответ YES.
Во втором запросе нужно добавить к изначальному массиву число 11. В полученном массиве
первое число будет равно 12, второе 24. НОД(12, 24) = 12, отсюда следует что ответ NO.
Предмет: Информатика, автор: molika1986m
Задача C. Суммарная площадь

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Альтаиру часто дарят интересные подарки. На этот раз Ариф подарил множество различных

точек на плоскости, он конечно поблагодарил Арифа. Но он совсем не знает что делать с этими

точками, поэтому он придумал задачу.

Альтаир определил функцию f(S), которая считает площадь минимального прямоугольника со

сторонами параллельными осям координат, который покрывает все точки из множества S (точка

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

функции кажется ему чем-то слишком простым и скучным, поэтому он хочет посчитать сумму

значений функции f по всем возможным непустым подмножествам точек.

Так как Альтаир не умеет использовать большие числа, а ответ может быть уж слишком большим, поэтому нужно посчитать его остаток при делении на 109 + 7.

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

В первой строке дано одно натуральное число n (1 6 n 6 105

) — количество точек в подарке.

Далее следуют n строк, в i-й записана пара чисел xi

, yi (1 6 xi

, yi 6 109

) — координаты i-й

точки.

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

Выведите одно число - ответ на задачу по модулю 109 + 7.

Система оценки

Подзадача Дополнительные ограничения Баллы Необходимые подзадачи

0 Примеры 0 —

1 n = 2 9

2 n 6 20 11 1

3 n 6 200 15 1, 2

4 n 6 2 000 25 1, 2, 3

5 n 6 100 000 40 1, 2, 3, 4

Пример

стандартный ввод стандартный вывод

3

4 10

5 7

7 9

19

Замечание

Рассмотрим пример. В этом примере есть 7 непустых подмножеств.

Площадь прямоугольника для подножества из первой и второй точки: f({1, 2}) = 3.

f({1}) = f({2}) = f({3}) = 0

f({1, 2}) = 3

f({1, 3}) = 3

f({2, 3}) = 4

f({1, 2, 3}) = 9

Сумма по всем f(S) – 19.