Abay Baimukanov

Задача №1.

Задача H. Легкая математика

Ограничение по времени:

1 секунда

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

256 мегабайт

У Абая есть натуральное число $n$. Он может делать с этим числом 2 вида операций: 1) Умножить $n$ на $x$ ($x$ — любое натуральное число) 2) Заменить $n$ на $\sqrt{n}$ (в этом случае $\sqrt{n}$ должно быть целым числом) Обе операции можно делать любое количество раз. Помогите Абаю узнать, какое минимальное число можно получить, выполняя данные операции. Также Абая интересует, какое минимальное количество операций нужно проделать, чтобы получить минимальное число.

Формат входного файла

В единственной строке дано натуральное число $n$ ($1 <= n <= 10^6$).

Формат выходного файла

Выведите два числа: минимальное число, которое можно получить, затем минимальное количество операций для получения этого числа.

Примеры:

Вход

Ответ

10 2

Вход

Ответ

6 4

Замечание

Ответ для первого примера: 20 --> $20 \times 5 = 100$ --> $\sqrt{100} = 10$ — в итоге 2 операции. Ответ для второго примера: 5184 --> $\sqrt{5184} = 72$ --> $72 \times 18 = 1296$ --> $\sqrt{1296} = 36$ --> $\sqrt{36} = 6$ — в итоге 4 операции. ( Abay Baimukanov )
комментарий/решение(6) олимпиада

Задача №2.

Задача H. Легкая математика

Ограничение по времени:

1 секунда

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

256 мегабайт

Формат входного файла

В единственной строке дано натуральное число $n$ ($1 <= n <= 10^6$).

Формат выходного файла

Примеры:

Вход

Ответ

10 2

Вход

Ответ

6 4

Замечание

Задача №3.

Задача C. From And with love

Ограничение по времени:

1 секунда

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

256 мегабайт

Абай очень любит массивы. Еще больше он любит играть с подпоследовательностями массива. Подпоследовательность — это такая последовательность массива, которая может быть получена удалением нескольких (возможно ноль) элементов из этого массива. Вам дан массив $A$ из $N$ целых чисел. Рассмотрим какую--нибудь подпоследовательность массива. Пусть битовый AND этой подпоследовательности равен $X$. Тогда подпоследовательность называется хорошей, если в ней нет элемента со значением $X$. Посчитайте количество хороших подпоследовательностей.

Формат входного файла

В первой строке дается натуральное число $N$ — размер массива $A$. В следующей строке заданы $N$ целых неотрицательных чисел — элементы массива $A$.

Формат выходного файла

Выведите одно число — количество хороших подпоследовательностей. Так как ответ может быть достаточно большим, выведите его остаток от деления на $10^9 + 7$.

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

Это задача состоит из 5 подзадач и 25 тестов, каждый тест оценивается в 4 балла:

$1 <= N <= 15$, $0 <= A_i < 2^{20}$. Тесты 1 -- 3
$1 <= N <= 10^5$, $0 <= A_i < 2^4$. Тесты 4 -- 7
$1 <= N <= 10^5$, $0 <= A_i < 2^{10}$. Тесты 8 -- 12
$1 <= N <= 10^5$, $0 <= A_i < 2^{15}$. Тесты 13 -- 18
$1 <= N <= 10^6$, $0 <= A_i < 2^{20}$. Тесты 19 -- 25

Пример:

Вход

5
0 2 5 3 7

Ответ

Замечание

Одной из хороших подпоследовательностей является 2, 5, 7. Ее битовый AND равен 0, при этом число 0 не присутствует среди 2, 5, 7. Операция побитового AND существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string&$>>, в Pascal — как <>. Таблица для побитового AND.\\ 1 $and$ 1 = 1, 1 $and$ 0 = 0\\ 0 $and$ 1 = 0, 0 $and$ 0 = 0\\ ( Abay Baimukanov )
комментарий/решение(3) олимпиада

Задача №4.

Задача A. Матрицы

Ограничение по времени:

1 секунда

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

256 мегабайт

Вам дана матрица размера $N \times M$, состоящая из целых положительных чисел, а также целое число $K$. Назовем подматрицу хорошей, если она является квадратом и сумма этой подматрицы не больше $K$. Посчитайте количество хороших подматриц. Подматрицей называется такая матрица, которую можно получить из исходной, если удалить из нее несколько(возможно ноль) столбцов с левого и правого края, а также несколько(возможно ноль) строк с верхнего и нижнего края. При этом подматрица не должна быть пустой.

Формат входного файла

В первой строке заданы $3$ целых числа $N$, $M$, $K$ — размеры матрицы и ограничение на сумму. ($1 <= N, M <= 1500$, $0 <= K <= 10^9$) В следующих $N$ строках содержится по $M$ целых положительных чисел — содержимое матрицы (числа по значению от $1$ до $1000$).

Формат выходного файла

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

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

Данная задача содержит $6$ подзадач, в которых выполняются следующие ограничения:

Тесты из условия. Оценивается в $0$ баллов.
$N, M <= 2$. Оценивается в $15$ баллов.
$N, M <= 100$. Оценивается в $17$ баллов.
$N, M <= 500$. Оценивается в $24$ балла.
$N, M <= 1500$ и матрица состоит только из единичек. Оценивается в $15$ баллов.
Исходные ограничения. Оценивается в $29$ баллов.

Примеры:

Вход

Ответ

Вход

  
6 6 30
4 4 4 1 1 1
2 5 5 3 2 3
3 2 2 4 1 3
1 1 4 4 4 5
1 3 3 4 5 5
2 5 5 4 3 4

Ответ

( Abay Baimukanov )
комментарий/решение(2) олимпиада

Задача №5.

Задача D. Массив и запросы

Ограничение по времени:

1.5 секунд

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

256 мегабайт

Абай принес вам простую задачу без легенды. Задан массив $A$, состоящий из $N$ натуральных чисел, а также $Q$ запросов вида $L, R$. Ответом на запрос является максимальное целое $K$ ($K \ge 0$), что для него найдется натуральное $X$, при котором числа $X$, $2X$, $4X$, ..., $2^K \cdot X$ встречаются среди чисел $A_L$, $A_{L+1}$, ..., $A_R$. Ваша задача -- посчитать ответ на каждый запрос. Примечание: натуральным называется целое число больше нуля.

Формат входного файла

В первой строке выходных данных заданы два натуральных числа $N$ и $Q$ ($1 <= N, Q <= 5 \cdot 10^5$). Во второй строке задается массив $A$ ($1 <= A_i <= 10^{18}$). Начиная с третьей строки, задаются запросы $L$, $R$ ($1 <= L <= R <= N$). Каждый запрос задан в отдельной строке.

Формат выходного файла

Выведите $Q$ строк, в $i$-й строке должен быть ответ на $i$-й запрос.

Пример:

Вход

6 3
6 9 12 24 18 9
2 3
4 6
1 5

Ответ

0
1
2

Замечание

Пояснение к примеру: В во втором запросе можно выбрать 18 и 9, тогда $K = 1, X = 9$. В третьем запросе -- 6, 12 и 24 ($K = 2, X = 6$). ( Abay Baimukanov )
комментарий/решение олимпиада