Районная олимпиада по информатике. 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 подзадачи.
  1. $0 \le a_i \le 1$ для всех $1 \le i \le n$.
  2. $n = 2$, $-1000 \le a_i \le 1000$.
  3. Ограничения из условия.
В первом примере всего существует 6 пар чисел и все они являются квадратами числа 0 или 1. Во втором примере единственная пара при произведении дает 16, что является квадратом целого числа. В третьем примере все три пары (1, 16), (1, 4), (16, 4) в произедении дают квадрат целого числа. В четвертом примере нет пар.

комментарий/решение(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$ чисел,к каждому числу массива Жарасхан должен применить лишь одну операцию. Есть три типа операции:
  1. Добавить к числу один.
  2. Отнять от числа один.
  3. Добавить к числу ноль.
К каждому элементу массива нужно применить одну из трех операции так, чтобы после применения операций ко всем элементам массива, количество одинаковых чисел в массиве стало максимальным. Помогите Жарасхану с этой непростой задачей.
Формат входного файла
В первой строке входных данных дано одно целое число $N$ - размер массива. Во второй строке входных данных даны элементы массива $ a_{i} $.
Формат выходного файла
Выведите одно целое число — максимальное количество одинаковых чисел в массиве после применения операций.
Система оценки
Данная задача имеет 4 подзадачи:
  1. $1 \le N \le 2$. Оценивается в $10$ баллов.
  2. $1 \le N \le 10^2$ и $1 \le a_{i} \le 10$. Оценивается в $20$ баллов.
  3. $1 \le N \le 10^5$ и $1 \le a_{i} \le 2$. Оценивается в $20$ баллов.
  4. $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 подзадач:
  1. $n = 1$. Оценивается в $13$ баллов.
  2. $0 \le a_i \le 2$. Оценивается в $5$ баллов.
  3. $1 \le n \le 15$. Оценивается в $40$ баллов.
  4. Ограничения из условий. Оценивается в $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) Проверить мое решение