Задача A. Окружность

На окружности на равном расстоянии друг от друга отмечены $N$ точек, пронумерованных против часовой стрелки целыми числами от $1$ до $N$. Вам даны несколько пар хорд этой окружности, концами которых являются данные точки. Для каждой пары хорд определите, пересекаются ли они (касание необходимо считать пересечением). На первой строке входного файла расположены два целых числа: $N$ и $K$ ($1 <= N <= 10^9$, $1 <= K <= 100$). На следующих K строках расположены по 4 целых числа: $A_1$, $B_1$, $A_2$, $B_2$ – номера концов первой хорды ($A_1$, $B_1$) и второй хорды ($A_2$, $B_2$). Числа в строках разделены пробелами. Для каждой пары хорд из входного файла выведите одну строку, содержащую YES, если диагонали пересекаются и NO, если они не пересекаются. Вход

4 3
1 3 2 4
1 2 3 4
1 2 3 2

Ответ

YES
NO
YES

Задача B. Делители

Положительное число $A$ называется делителем числа $B$, если число $B$ делится на $A$ без остатка. Например, у числа 15 есть 4 делителя: 1, 3, 5, 15. Для каждого из заданных чисел вам необходимо определить, четно или нечетно количество его делителей. Первая строка входного файла содержит целое число $N$ ( $1 <= N <= 10$ ). Следующая строка содержит $N$ чисел $X_i$ ( $1 <= X_i <= 10^{18}$ ). Числа в строке разделены пробелами Единственная строка выходного файла должна содержать $N$ чисел разделенных пробелом. i-е число должно быть $0$, если количество делителей $X_i$ четно, и $1$, если количество делителей $X_i$ нечетно. Вход

2
4 5

Ответ

1 0

Задача C. Выгода

Компьютер состоит из процессорного блока и монитора. На складе имеется $N$ системных блоков и $M$ мониторов. i-й блок стоит $A_i$ тугриков, j-й монитор – $B_j$ тугриков. Из-за мирового финансового кризиса, стоимость компьютера, в состав которого входит i-й системный блок и j-й монитор равна $A_i$ ∙ $B_j$ (умножение) тугриков. Вам надо собрать наибольшее возможное количество компьютеров так, чтобы их суммарная стоимость была максимально возможной. Первая строка входного файла содержит два целых числа: $N$ и $M$ ($1 <= N, M <= 1000$). Вторая строка содержит $N$ целых чисел: i-е число в строке – это $A_i$. Третья строка содержит $M$ целых чисел: j-е число в строке – это $B_j$. ($1 <= A_i, B_j <= 1000$). Числа в строках разделены пробелами. Выходной файл должен содержать два целых числа, разделенных пробелом – максимально возможное число компьютеров и их максимальную суммарную стоимость. Вход

3 2
1 2 3
4 5

Ответ

2 23

Задача D. Лень

Для подготовки к экзамену преподаватель дал ученикам $N$ вопросов. При этом он сказал, что для экзамена выберет из них $A$ вопросов, а ученик, чтобы получить пятерку, должен ответить на $B$ из этих $A$ вопросов. Хитрый ученик не хочет учить все вопросы. Какое минимальное количество вопросов ему надо выучить, чтобы при любом раскладе он смог получить пятерку? Единственная строка входного файла содержит три целых числа: $N$, $A$ и $B$ ($1 <= N <= 100000$, $1 <= B <= A <= N$). Числа разделены пробелами. Выходной файл должен содержать одно целое число – ответ к задаче. Вход

10 7 3

Ответ

6

Задача E. Спираль

Спираль размера $N$ – это таблица натуральных чисел размером $N$x$N$, в центре таблицы всегда 1, справа от нее 2, спираль закручивается против часовой стрелки. Выведите спираль размера $N$. Единственная строка входного файла содержит одно число – $N$ ($1 <= N < 100$, $N$ - нечетное). Выведите $N$ строк по $N$ чисел – спираль размера $N$. Числа в строках должны быть разделены пробелами. Вход

1

Ответ

1

Вход

3

Ответ

5 4 3
6 1 2
7 8 9

Вход

5

Ответ

17 16 15 14 13
18  5  4  3 12
19  6  1  2 11
20  7  8  9 10
21 22 23 24 25

Задача F. Степень

Вам даны целые числа $A$, $B$ и $C$. Выведите остаток от деления $A^B$ ($A$ в степени $B$) на $C$. Обратите внимание: $(X · Y) mod Z = ((X mod Z) · (Y mod Z)) mod Z$
$(X + Y) mod Z = ((X mod Z) + (Y mod Z)) mod Z$
Единственная строка входного файла содержит 3 целых числа: $A$, $B$, $C$ ($0 <= A, B <= 10^{18}$, $1 <= C <= 10^{18}$). Числа разделены пробелами. Выходной файл должен содержать одно число – ответ к задаче. Вход

3 4 5

Ответ

1