Aibar Kuanyshbay


Задача №1. 

Задача D. Выбор Айбара

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

У Айбара есть два массива $A$ и $B$, что размер каждого равен $n$. Для каждого $i$, что $(1 <= i <= n)$, Айбар должен выбрать либо $A_i$, либо $B_i$. Он хочет максимизировать произведение суммы выбранных $A_i$ и суммы выбранных $B_j$. Помогите Айбару найти максимальное значение. Гарантируется, что максимальное значение не превосходит $10^9$.
Формат входного файла
Первая строка содержит одно целое число $n$ $(2 <= n <= 1000)$. Вторая строка содержит $n$ целых чисел $A_1, A_2, A_3,...A_n$ $(1 <= A_i <= 10^9)$. Третья строка содержит $n$ целых чисел $B_1, B_2, B_3,...B_n$ $(1 <= B_i <= 10^9)$.
Формат выходного файла
Выведите одно целое число -- ответ на задачу.
Система оценки
Данная задача содержит шесть подзадач:
  1. $2 <= n <= 1000, 1 <= A_i, B_i <= 1$. Оценивается в $8$ баллов.
  2. $2 <= n <= 15, 1 <= A_i, B_i <= 10^9$. Оценивается в $9$ баллов.
  3. $2 <= n <= 1000, 1 <= A_i, B_i <= 10^9$ и $A_1 <= A_2 <= ... <= A_n$, $B_1 \ge B_2 \ge ... \ge B_n$ . Оценивается в $10$ баллов.
  4. $2 <= n <= 1000$, $A_i=B_i$ для всех $i$, сумма всех $A_i$ не больше $10^5$. Оценивается в $18$ баллов.
  5. $2 <= n <= 100$, сумма всех $A_i$ не больше 300, сумма всех $B_i$ не больше 300. Оценивается в $15$ баллов.
  6. $2 <= n <= 1000, 1 <= A_i, B_i <= 10^9$. Оценивается в $30$ баллов.
Примеры:
Вход
5
1 4 3 2 5
5 2 2 4 1
Ответ
108
Вход
2
5 7
3 5
Ответ
25
Вход
7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
Ответ
12
Замечание
В первом сэмпле Айбар выбирает в массиве $A$ позиции 2, 3, 5, а в массиве $B$ позиции 1 и 4. Тогда ответ $(4 + 3 + 5) * (5 + 4)=108$. ( Aibar Kuanyshbay )
комментарий/решение(1) олимпиада
Задача №2. 

Задача C. Четная сумма

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

У Айбара есть $n$ целых чисел. Он хочет выбрать некоторые из них, чтобы получить максимально возможную чётную (то есть, делящуюся на $2$) сумму. Пожалуйста, вычислите, на что может рассчитывать Айбар. Обратите внимание, что если Айбар не выберет ни одного числа, то сумма будет равна чётному числу $0$.
Формат входного файла
В первой строке входных данных записано число $n$ $(1 <= n <= 10^5)$ — количество чисел. В следующей строке записаны $n$ целых чисел, имеющихся у Айбара. Все эти числа не превышают по абсолютному значению $10^9$.
Формат выходного файла
Выведите максимально возможную чётную сумму, которую можно получить, используя каждое из данных чисел не более одного раза.
Примеры:
Вход
3
1 2 3
Ответ
6
Вход
4
1 3 5 -3
Ответ
8
( Aibar Kuanyshbay )
комментарий/решение олимпиада
Задача №3. 

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Дается два целых натуральных числа $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
( Aibar Kuanyshbay )
комментарий/решение(6) олимпиада
Задача №4. 

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

В ресторане есть $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
( Aibar Kuanyshbay )
комментарий/решение(5) олимпиада
Задача №5. 

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Вам дано целое число $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$ - четно.
( Aibar Kuanyshbay )
комментарий/решение(5) олимпиада
Задача №6. 

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Вам дана последовательность $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$
( Aibar Kuanyshbay )
комментарий/решение(9) олимпиада
Задача №7. 

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Дан массив $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
( Aibar Kuanyshbay )
комментарий/решение(1) олимпиада
Задача №8. 

Задача D. Разделение массива

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

У Тимы есть три младших брата: Батыр, Димаш и Есмахан. Тима решил дать им массив $a$ из $n$ целых чисел, чтобы развлечь их. Он хочет разделить массив на три непустых частей и раздать своим братьям, чтобы каждое число было ровно в одной части. Все числа одной части должны идти подряд в массиве. Пусть $A$ - сумма чисел в первой части, $B$ - сумма чисел во второй, $C$ - сумма в третьей. Чтобы братья не ругались, Тима хочет минимизировать max(A, B, C) - min(A, B, C). Найдите минимальное значение max(A, B, C) - min(A, B, C).
Формат входного файла
В первой строке дано одно целое число $n$ $(3 <= n <= 3 * 10^5)$. Во второй строке дано $n$ целых чисел $a_1$, $a_2$, $\dots$, $a_n$ $(0 <= a_i <= 10^5)$.
Формат выходного файла
Выведите одно целое число — ответ на задачу.
Система оценки
Это задача состоит из 4 подзадач и 20 тестов, каждый тест оценивается в 5 баллов:
  1. $n <= 10^2$. Тесты 1 -- 4
  2. $n <= 5 * 10^3$. Тесты 5 -- 8
  3. $a_i <= 1$. Тесты 9 -- 12
  4. $n <= 3 * 10^5$. Тесты 13 -- 20
Пример:
Вход
7
4 1 2 3 1 3 2
Ответ
1
Замечание
Один из вариантов разделении в примере: 4 1 | 2 3 1 | 3 2 Также можно разделить 4 1 | 2 3 | 1 3 2 ( Aibar Kuanyshbay )
комментарий/решение(3) олимпиада
Задача №9. 

Задача B. Радостные числа

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Натуральное число считается радостным, если оно оканчивается на $25$ и является полным квадратом. Число считается полным квадратом, если является квадратом какого-то целого числа. Например, 25,225,625 радостные, а 125,49, 325 - нет. Вам дано число $k$. Найдите $k$-е радостное число.
Формат входного файла
В единственной строке задано одно целое число $k$ ($1 <= k <= 10^8$).
Формат выходного файла
Выведите одно целое число — $k$-е радостное число.
Система оценки
Это задача состоит из 4 подзадач и 10 тестов, каждый тест оценивается в 10 баллов:
  1. $1 <= k <= 10$. Тесты 1 -- 4
  2. $1 <= k <= 100$. Тесты 5 -- 6
  3. $1 <= k <= 5000$. Тесты 7 -- 8
  4. $1 <= k <= 10^8$. Тесты 9 -- 10
Пример:
Вход
2
Ответ
225
( Aibar Kuanyshbay )
комментарий/решение(7) олимпиада