Задача A. Равнобедренные треугольники

Треугольник называется равнобедренным, если хотя бы две из трёх сторон имеют одинаковую длину. Посчитайте количество равнобедренных треугольников, у которых длина каждой стороны - целое число от $1$ до $N$. Не забывайте, что треугольник существует только в том случае, когда длина каждой стороны меньше суммы длин двух других сторон. В единственной строке вводится одно натуральное число $N$. Выведите количество подходящих треугольников. Это задача состоит из 10 тестов, каждый оценивается в 10 баллов:

1. 2 теста при $1 <= N <= 100$
2. 3 теста при $1 <= N <= 5000$
3. 5 тестов при $1 <= N <= 10^6$

Вход

4

Ответ

12

Подходящие треугольники:
1 1 1
2 2 1
2 2 2
2 2 3
3 3 1
3 3 2
3 3 3
3 3 4
4 4 1
4 4 2
4 4 3
4 4 4

Задача B. Четные цифры

Дается два целых натуральных числа $L$ и $R$. Нужно посчитать сколько существует чисел от $L$ до $R$, включительно, у которых все цифры в десятичной записи четные. Найдите ответ. В первой строке входных данных дано два натуральных числа $L$ и $R$ $(1 <= L <= R <= 10^{10})$. Выведите одно целое число — ответ на задачу. Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $1 <= L <= R <= 10^2$. Тесты с номерами 1-2.
2. $1 <= L <= R <= 10^6$. Тесты с номерами 3-4.
3. $1 <= L <= R <= 10^{10}$. Тесты с номерами 5-10.

Вход

3 10

Ответ

3

Задача C. Ресторан

В ресторане есть $n$ официантов. Они пронумерованы от $1$-го до $n$. На столе стоят $m$ стаканов. Они пронумерованы от $1$-го до $m$. Изначально все стаканы пустые. Каждый официант должен налить напиток в некоторые стаканы. $i$-й официант должен налить в стаканы с номерами от $l_i$ до $r_i$ по $x_i$ миллилитров напитка. Какой-то официант проспал и забыл сделать это. Все остальные кроме него выполнили задание. Вам дано количество миллилитров напитка в каждом стакане. Нужно найти список, тех официантов, кто возможно проспал. В первой строке дается два целых числа $n$ и $m$ $(1 <= n, m <= 10^5)$ — количество официантов и количество стаканов. В следующих $n$ строках заданы по три целых числа $l_i$, $r_i$ и $x_i$ $(1 <= l_i <= r_i <= m$, $1 <= x_i <= 10^3)$. В следующей строке заданы $m$ целых числа $a_1$, $a_2$, $\dots$, $a_m$, где $a_i$ обозначает количество миллилитров напитка в $i$-м стакане. Выведите номера в отсортированном порядке, тех официантов, кто возможно проспал. Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $1 <= n, m <= 100$. Тесты с номерами 1-2.
2. $1 <= n, m <= 3000$. Тесты с номерами 3-5.
3. $1 <= n, m <= 10^5$. Тесты с номерами 6-10.

Вход

5 4
1 3 2
2 4 3
1 3 2
3 4 1
3 3 1
2 5 7 4

Ответ

1 3

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

Вам дано целое число $n$. Найдите количество чисел от $1$ до $n$, которые имеют четное количество делителей. В первой строке одно целое число $n$ $(1 <= n <= 10^9)$. Выведите ответ. Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $1 <= n <= 1000$. Тесты с номерами 1-6.
2. $1 <= n <= 10^5$. Тесты с номерами 7-8.
3. $1 <= n <= 10^9$. Тесты с номерами 9-10.

Вход

10

Ответ

7

В примере:

1. У числа $1$ делители: $1$. Количество $1$ - нечетно.
2. У числа $2$ делители: $1, 2$. Количество $2$ - четно.
3. У числа $3$ делители: $1, 3$. Количество $2$ - четно.
4. У числа $4$ делители: $1, 2, 4$. Количество $3$ - нечетно.
5. У числа $5$ делители: $1, 5$. Количество $2$ - четно.
6. У числа $6$ делители: $1, 2, 3, 6$. Количество $4$ - четно.
7. У числа $7$ делители: $1, 7$. Количество $2$ - четно.
8. У числа $8$ делители: $1, 2, 4, 8$. Количество $4$ - четно.
9. У числа $9$ делители: $1, 3, 9$. Количество $3$ - нечетно.
10. У числа $10$ делители: $1, 2, 5, 10$. Количество $4$ - четно.

Задача E. Второй максимум

Вам дана последовательность $a_1, a_2...a_n$ длины $n$. Для каждого $k$ от $2$ до $n$ найдите значение второго по величине элемента среди первых $k$ элементов последовательности $a$. В первой строке одно целое число $n$ $(1 <= n <= 10^5)$. Во второй строке $n$ целых чисел $a_1, a_2... a_n$ $(1 <= a_i <= 10^9)$. Выведите ответ для каждого $k$ от $2$ до $n$. Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $1 <= n <= 100$. Тесты с номерами 1-3.
2. $1 <= n <= 5000$. Тесты с номерами 4-6.
3. $1 <= n <= 10^5$. Тесты с номерами 7-10.

Вход

7
1 2 3 3 7 5 6

Ответ

1 2 3 3 5 6

В примере:

1. $k=2$. Первые $k$ чисел $\underline{1}, 2$. Ответ $1$
2. $k=3$. Первые $k$ чисел $1, \underline{2}, 3$. Ответ $2$
3. $k=4$. Первые $k$ чисел $1, 2, \underline{3}, 3$. Ответ $3$
4. $k=5$. Первые $k$ чисел $1, 2, \underline{3}, 3, 7$. Ответ $3$
5. $k=6$. Первые $k$ чисел $1, 2, 3, 3, 7, \underline{5}$. Ответ $5$
6. $k=7$. Первые $k$ чисел $1, 2, 3, 3, 7, 5, \underline{6}$. Ответ $6$

Задача F. Тройки

Дан массив $a$ длины $n$, который состоит из целых натуральных чисел. Все числа в массиве различные. Вам нужно посчитать количество троек $i$, $j$, $k$, что $i \ne j$, $i \ne k$, $j \ne k$ и $a_i*a_j=a_k^2$. В первой строке задано одно целое число $n$ $(3 <= n <= 10^5)$. В следующей строке задано $n$ целых натуральных чисел $a_1$, $a_2$, $\dots$, $a_n$ $(1 <= a_i <= 3 * 10^5)$. Выведите одно целое число — ответ на задачу. Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $n <= 100$, $1 <= a_i <= 500$. Тесты с номерами 1-3.
2. $n <= 5000$, $1 <= a_i <= 10000$. Тесты с номерами 4-6.
3. $n <= 10^5$, $1 <= a_i <= 300000$. Тесты с номерами 7-10.

Вход

6
6 3 9 4 12 27

Ответ

6