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 )
комментарий/решение(2) олимпиада
Задача №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 )
комментарий/решение(7) олимпиада
Задача №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 )
комментарий/решение(7) олимпиада
Задача №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 )
комментарий/решение(11) олимпиада
Задача №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 )
комментарий/решение(11) олимпиада
Задача №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 )
комментарий/решение(2) олимпиада
Задача №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 )
комментарий/решение(4) олимпиада
Задача №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 )
комментарий/решение(14) олимпиада
Задача №10. 

Задача B. AB

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

Вам даны две строки $s$ и $t$, которые состоят из букв 'a' и 'b'. В строке $s$ нет соседних одинаковых букв. Вы хотите выбрать наибольшее количество непересекающихся подпоследовательностей $t$, которые равны $s$. Подпоследовательность — это такая последовательность строки, которая может быть получена удалением нескольких (возможно ноль) элементов из этой строки. Найдите максимальное количество подпоследовательностей, которое вы сможете выбрать.
Формат входного файла
Первая строка входных данных содержит одну строку s ($1 <= |s| <= 4$). Гарантируется, что в строке $s$ нет соседних одинаковых букв. Вторая строка входных данных содержит одну строку t ($1 <= |t| <= 10^5$).
Формат выходного файла
Выведите одно целое число — максимальное количество подпоследовательностей, которое вы сможете выбрать.
Система оценки
Данная задача содержит $7$ подзадач, в которых выполняются следующие ограничения:
  1. Тесты из условия. Оценивается в $0$ баллов.
  2. $|s| = 1$. Оценивается в $11$ баллов.
  3. $|s| = 2$. Оценивается в $14$ баллов.
  4. $|s| = 3$. Оценивается в $20$ баллов.
  5. $|s| = 4$, $|t| <= 50$. Оценивается в $18$ баллов.
  6. $|s| = 4$, $|t| <= 300$. Оценивается в $12$ баллов.
  7. $|s| = 4$, $|t| <= 10^5$. Оценивается в $25$ баллов.
Примеры:
Вход 
ab
abbaba
Ответ
2
Вход 
  
aba
ababaa
Ответ
2
Замечание
Во втором примере можно выбрать две непересекающихся последовательности c индексами {1, 2, 5} и {3, 4, 6}. ( Aibar Kuanyshbay )
комментарий/решение(1) олимпиада