Районная олимпиада по информатике. 2018-2019 учебный год. 8-11 классы
Задача A. Крутой подарок
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
У Темирлана недавно был день рождения. Из его друзей самый оригинальный подарок решил сделать его друг, Айсултан. Айсултан знает, что Темирлан любит крутые числа. Число называется крутым, если оно является квадратом целого числа. Например, $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 подзадачи.
- $0 \le a_i \le 1$ для всех $1 \le i \le n$.
- $n = 2$, $-1000 \le a_i \le 1000$.
- Ограничения из условия.
комментарий/решение(8) Проверить мое решение
Задача B. Делимость
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
ОМА решил придумать свой признак делимости на 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)$
комментарий/решение(10) Проверить мое решение
Задача C. Сумма квадратов
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Даны два массива целых чисел длинны $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
комментарий/решение(10) Проверить мое решение
Задача D. Уравнитель
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
У Жарасхана есть массив $a$ из $N$ чисел,к каждому числу массива Жарасхан должен применить лишь одну операцию. Есть три типа операции:
- Добавить к числу один.
- Отнять от числа один.
- Добавить к числу ноль.
Формат входного файла
В первой строке входных данных дано одно целое число $N$ - размер массива.
Во второй строке входных данных даны элементы массива $ a_{i} $.
Формат выходного файла
Выведите одно целое число — максимальное количество одинаковых чисел в массиве после применения операций.
Система оценки
Данная задача имеет 4 подзадачи:
- $1 \le N \le 2$. Оценивается в $10$ баллов.
- $1 \le N \le 10^2$ и $1 \le a_{i} \le 10$. Оценивается в $20$ баллов.
- $1 \le N \le 10^5$ и $1 \le a_{i} \le 2$. Оценивается в $20$ баллов.
- $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
комментарий/решение(9) Проверить мое решение
Задача E. 80236 Докажи, что математик
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
После неудачного выступления на 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
комментарий/решение(9) Проверить мое решение
Задача F. Формат времени
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Вам даны два момента времени, причем гарантируется что они оба находятся в течении одних суток и первый из них находится строго раньше второго. По данной информации определите, использовался ли для их записи 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
комментарий/решение(3) Проверить мое решение
Задача G. Депозит
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
У Жарасхана есть депозит в банке дураков. Сумма денег может быть отрицательной. Каждый день депозит пополняется на заранее известный процент. А также, Жарасхан может частично изымать деньги из этого депозита в любой момент когда ему будут нужны деньги. Но система банка работает таким образом, что можно изымать только определенный процент от денег в депозите. У Жарасхана есть история операций по депозиту за каждый день в виде процентов. Изначально у Жарасхана есть $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 подзадач:
- $n = 1$. Оценивается в $13$ баллов.
- $0 \le a_i \le 2$. Оценивается в $5$ баллов.
- $1 \le n \le 15$. Оценивается в $40$ баллов.
- Ограничения из условий. Оценивается в $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$. Соответственно на второй день имеется минимально возможная сумма и на последнем максимальная.
Во втором тестовом примере, так как сумма только возрастает изначальная сумма является минимальной.
комментарий/решение(10) Проверить мое решение
Задача H. Возрастающие подмассивы
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Вам дан массив $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 \ баллов. \\$
комментарий/решение(3) Проверить мое решение