Задача A. Крутой подарок

У Темирлана недавно был день рождения. Из его друзей самый оригинальный подарок решил сделать его друг, Айсултан. Айсултан знает, что Темирлан любит крутые числа. Число называется крутым, если оно является квадратом целого числа. Например, $0$, $9$, $121$ — крутые числа; а $50$, $3$, $12$ — не крутые числа. В распоряжении Айсултана есть последовательность из $n$ целых чисел — $a_1, a_2, a_3, ..., a_n$. Чтобы сообразить подарок, Айсултан берет два числа из этой последовательности $a_j$ и $a_i$ таких, что $j < i$ и если число $a_j * a_i$ является крутым, то он подарит произведение этих двух чисел Темирлану. Помогите понять Айсултану, сколькими способами он может это сделать. Формально, найдите количество пар чисел $(a_j, a_i)$ таких, что $j < i$ и произведение $a_j * a_i$ является крутым числом. Первая строка входных данных содержит одно число $n$ — размер последовательности Айсултана $(1 \le n \le 10^3)$. Вторая строка входных данных содержит $n$ целых чисел $a_1, a_2, a_3, ..., a_n$ через пробел — последовательность Айсултана $(-1000 \le a_i \le 1000)$. В единственной строке выведите одно число — ответ на задачу. Вход

4
1 0 1 1

Ответ

6

Вход

2
-8 -2

Ответ

1

Вход

3
1 16 4

Ответ

3

Вход

1
0

Ответ

0

Данная задача содержит 3 подзадачи.

1. $0 \le a_i \le 1$ для всех $1 \le i \le n$.
2. $n = 2$, $-1000 \le a_i \le 1000$.
3. Ограничения из условия.

В первом примере всего существует 6 пар чисел и все они являются квадратами числа 0 или 1. Во втором примере единственная пара при произведении дает 16, что является квадратом целого числа. В третьем примере все три пары (1, 16), (1, 4), (16, 4) в произедении дают квадрат целого числа. В четвертом примере нет пар.

Задача B. Делимость

ОМА решил придумать свой признак делимости на 8. ОМА будет считать что число делится на 8 если существует перестановка цифр числа такая что новое число было без лидирующих нулей и число делится на 8. Вам надо сказать делится ли число на 8 по правилам ОМЫ. В первой строке дано цело число $n$ $(1 \leq n \leq 10^3) $ - длинна числа. $\\$ Во второй строка дана строка состоящая из цифр $s$ - число которое надо проверить. Выведите YES если число делится на 8 по правилам ОМЫ иначе NO Вход

2
23

Ответ

YES

Вход

3
101

Ответ

NO

Перестановка числа х - это число, состоящее из тех же цифр, что и х, но в другом порядке. Например, числа, которые можно получить путем перестановки цифр числа 123: 132, 213, 231, 312, 321 В первом примере из числа 23 можно получить делящееся на 8 число 32, ответ YES. Во втором примере из числа 101 невозможно получить число делящееся на 8, ответ NO. $\\$ $\\$ Subtask 1: $(n \leq 100)$ $\\$ Subtask 2: $(n \leq 1000)$

Задача C. Сумма квадратов

Даны два массива целых чисел длинны $n$. Даются $q$ запросов. Каждый запрос состоит из чисел $l$ и $r$, после каждого запроса требуется вывести чему равна сумма квадратов разностей чисел $a[i]$ и $b[i]$ где $i$= $l$, $l$+1,.., $r$. Первая строка содержит числа $n, q, (1 \leq n, q \leq 100000)$\newline Вторая строка содержит массив n целых чисел(массив a)\newline Вторая строка содержит массив n целых чисел(массив b)\newline $(-100000 \leq a[i], b[i] \leq 100000)$, $i$ = 1, 2, ... , $n$\newline Следующие $q$ строк содержат числа $l, r, (1 \leq l \leq r \leq n)$ Система оценки:\newline Для 40\% тестов - $(1 \leq n, q \leq 100)$\newline Для 60\% тестов - $(1 \leq n, q \leq 100000)$ В каждой строке выведите ответы на запросы Вход

3 1
1 0 5
1 2 3
2 3

Ответ

8

Задача D. Уравнитель

У Жарасхана есть массив $a$ из $N$ чисел,к каждому числу массива Жарасхан должен применить лишь одну операцию. Есть три типа операции:

1. Добавить к числу один.
2. Отнять от числа один.
3. Добавить к числу ноль.

К каждому элементу массива нужно применить одну из трех операции так, чтобы после применения операций ко всем элементам массива, количество одинаковых чисел в массиве стало максимальным. Помогите Жарасхану с этой непростой задачей. В первой строке входных данных дано одно целое число $N$ - размер массива. Во второй строке входных данных даны элементы массива $ a_{i} $. Выведите одно целое число — максимальное количество одинаковых чисел в массиве после применения операций. Данная задача имеет 4 подзадачи:

1. $1 \le N \le 2$. Оценивается в $10$ баллов.
2. $1 \le N \le 10^2$ и $1 \le a_{i} \le 10$. Оценивается в $20$ баллов.
3. $1 \le N \le 10^5$ и $1 \le a_{i} \le 2$. Оценивается в $20$ баллов.
4. $1 \le N \le 10^5$ и $1 \le a_{i} \le 10^5$. Оценивается в $50$ баллов.

Вход

7
3 1 4 1 5 9 2

Ответ

4

Вход

10
1 2 3 4 5 6 7 8 9 10

Ответ

3

В первом тесте можно изменить массив в такой вид: 2,2,3,2,6,9,2

Задача E. 80236 Докажи, что математик

После неудачного выступления на ACM ICPC 2018-2019, NEERC - Northern Eurasia Finals, команда Хранители335 решила подтянуть свои знания математики, ибо на этом контесте они не решили элементарную задачу по теории чисел. Сегодня один из членов команды придумал задачу, где надо просто определить является ли площадь треугольника целочисленной. Ваша задача состоит в том, чтобы помочь этим ребятам. В первой строке записаны три целых числа $a$, $b$ и $c$ ($ 1 \le a, b, c \le 5000 $) - длины сторон загаданного треугольника. Выведите единственное число — площадь треугольника если она является целочисленной. В остальных случаях выведите -1. Вход

3 4 5

Ответ

6

Вход

5 8 5

Ответ

12

Вход

3 3 3

Ответ

-1

Задача F. Формат времени

Вам даны два момента времени, причем гарантируется что они оба находятся в течении одних суток и первый из них находится строго раньше второго. По данной информации определите, использовался ли для их записи 12 часовой или 24 часовой формат. Напомним, что в 12 часовом формате часы записываются целыми числами с 1 до 12, в то время, как в 24 часовом нумерация начинается с 0 до 23 включительно. Для лучшего понимания ознакомьтесь с тестовыми примерами. В первой и второй строках находятся первых и второй момент времени соответственно. Времена заданы в формате HH:MM (00 $\leq$ HH $\leq$ 23, 00 $\leq$ MM $\leq$ 59) В зависимости от того в каком, 12 или 24 часовом, формате может быть записано данное время, выведите ``12-hour clock'' или ``24-hour clock'' соответственно. В случае неоднозначности выведите - ``both''. При выводе кавычки выводить не нужно. Вход

11:00
23:50

Ответ

24-hour clock

Вход

09:20
03:30

Ответ

12-hour clock

Вход

06:00
12:00

Ответ

both

Вход

00:00
01:00

Ответ

24-hour clock

Задача G. Депозит

У Жарасхана есть депозит в банке дураков. Сумма денег может быть отрицательной. Каждый день депозит пополняется на заранее известный процент. А также, Жарасхан может частично изымать деньги из этого депозита в любой момент когда ему будут нужны деньги. Но система банка работает таким образом, что можно изымать только определенный процент от денег в депозите. У Жарасхана есть история операций по депозиту за каждый день в виде процентов. Изначально у Жарасхана есть $s$ денег на депозите. Если Жарасхан изымал деньги то процент отрицательный, если банк пополнял то положительный соответственно. Жарасхану стало интересно, на какой день у него была максимально возможная сумма и на какой минимальная. Так как Жарасхан очень занят работой, он попросил вас найти те самые дни. В первой строке входного файла заданы два целых числа $n$ $(1 \le n \le 25)$ - количество дней в истории, $s$ $(-100 \le s \le 100)$ - изначальная сумма у Жарасхана на депозите. Во второй строке входного файла заданы $n$ чисел $a_i$ $(-2 \le a_i \le 2)$ - коэффициент процента на $i$-й день. Каждое $a_i$ задано с не более двумя знаками после запятой. Выведите два целых числа - день в котором у Жарасхана была максимально возможная сумма и день в котором у Жарасхана была минимально возможная сумма на депозите. Если соответствующих дней несколько - выведите самый ранний. Данная задача состоит из 4 подзадач:

1. $n = 1$. Оценивается в $13$ баллов.
2. $0 \le a_i \le 2$. Оценивается в $5$ баллов.
3. $1 \le n \le 15$. Оценивается в $40$ баллов.
4. Ограничения из условий. Оценивается в $42$ баллов.

Вход

3 100
0.1 -0.4 2

Ответ

2 3

Вход

3 100
0.5 1 2

Ответ

0 3

Вход

2 100
1 -0.5

Ответ

0 1

В первом тестовом примере сумма после каждого дня: $110, 66, 132$. Соответственно на второй день имеется минимально возможная сумма и на последнем максимальная. Во втором тестовом примере, так как сумма только возрастает изначальная сумма является минимальной.

Задача H. Возрастающие подмассивы

Вам дан массив $a$ длины $n$ и $q$ запросов. В каждом запросе вам даются два числа $l, r \ (1 \leq l \leq r \leq n)$, нужно разбить подмассив $a_l, a_{l+1}, \ldots, a_r$ на минимальное количество возрастающих подмассивов. Выведите это количество для каждого запроса. Первая строка содержит два числа $n, q$ - размер массива и количество запросов. Во второй строке находятся $n$ чисел - массив $a \ (1 \leq a_i \leq 10^5)$. Следующие $q$ строк содержат два числа $l, r$ - описания запросов. Выведите $q$ строк - ответы на запросы. Вход

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

Ответ

3
2
1

Подмассив $a_l, a_{l+1}, \ldots, a_r$ является возрастающим если для всех $l \leq i \leq r - 1$ выполняется условие $a_i < a_{i+1}$. $ \\ \\ $ Ответы на запросы в первом примере: $ \\ $ [3, 1, 4, 2] - [3], [1, 4], [2] $ \\ $ [3, 1, 4] - [3], [1, 4] $ \\ $ [4] - [4] $ \\ $ Подзадачи: $\\ 1 \leq n, q \leq 1000 - 40 \ баллов. \\ 1 \leq n, q \leq 10^5 - 60 \ баллов. \\$