2-й этап Республиканской олимпиады по информатике 2018, 10-11 класс, *ДЕНЬ 1*
Казахстан, Декабрь, 6, 2018

Задача A. Формат времени
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

Вам даны два момента времени, причем гарантируется что они оба находятся в течении одних суток и первый из них находится строго раньше второго. По данной информации определите,
использовался ли для их записи 12 часовой или 24 часовой формат.
Напомним, что в 12 часовом формате часы записываются целыми числами с 1 до 12, в то время,
как в 24 часовом нумерация начинается с 0 до 23 включительно. Для лучшего понимания ознакомьтесь с тестовыми примерами.

Формат входных данных
В первой и второй строках находятся первых и второй момент времени соответственно.
Времена заданы в формате HH:MM (00 ⩽ HH ⩽ 23, 00 ⩽ MM ⩽ 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

Страница 1 из 3

2-й этап Республиканской олимпиады по информатике 2018, 10-11 класс, *ДЕНЬ 1*
Казахстан, Декабрь, 6, 2018

Задача B. Уравнитель
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

У Жарасхана есть массив a из N чисел,к каждому числу массива Жарасхан должен применить
лишь одну операцию. Есть три типа операции:
1. Добавить к числу один.
2. Отнять от числа один.
3. Добавить к числу ноль.
К каждому элементу массива нужно применить одну из трех операции так, чтобы после применения операций ко всем элементам массива, количество одинаковых чисел в массиве стало максимальным. Помогите Жарасхану с этой непростой задачей.

Формат входных данных
В первой строке входных данных дано одно целое число N - размер массива. Во второй строке
входных данных даны элементы массива ai .

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

Система оценки
Данная задача имеет 4 подзадачи:
1. 1 ⩽ N ⩽ 2. Оценивается в 10 баллов.
2. 1 ⩽ N ⩽ 102 и 1 ⩽ ai ⩽ 10. Оценивается в 20 баллов.
3. 1 ⩽ N ⩽ 105 и 1 ⩽ ai ⩽ 2. Оценивается в 20 баллов.
4. 1 ⩽ N ⩽ 105 и 1 ⩽ ai ⩽ 105 . Оценивается в 50 баллов.

Примеры
стандартный ввод
7
3 1 4 1 5 9 2
10
1 2 3 4 5 6 7 8 9 10

стандартный вывод
4
3

Замечание
В первом тесте можно изменить массив в такой вид: 2,2,3,2,6,9,2

Страница 2 из 3

2-й этап Республиканской олимпиады по информатике 2018, 10-11 класс, *ДЕНЬ 1*
Казахстан, Декабрь, 6, 2018

Задача C. Возрастающие подмассивы
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

Вам дан массив a длины n и q запросов. В каждом запросе вам даются два числа
l, r (1 ⩽ l ⩽ r ⩽ n), нужно разбить подмассив al , al+1 , . . . , ar на минимальное количество возрастающих подмассивов. Выведите это количество для каждого запроса.

Формат входных данных
Первая строка содержит два числа n, q - размер массива и количество запросов. Во второй строке
находятся n чисел - массив a (1 ⩽ ai ⩽ 105 ). Следующие q строк содержат два числа l, r - описания
запросов.

Формат выходных данных
Выведите q строк - ответы на запросы.

Пример
стандартный ввод
4
3
1
1
4

3
1 4 2
4
3
4

стандартный вывод
3
2
1

Замечание
Подмассив al , al+1 , . . . , ar является возрастающим если для всех l ⩽ i ⩽ r − 1 выполняется
условие ai < ai+1 .

Ответы на запросы в первом примере:
[3, 1, 4, 2] - [3], [1, 4], [2]
[3, 1, 4] - [3], [1, 4]
[4] - [4]
Подзадачи:
1 ⩽ n, q ⩽ 1000 − 40 .
1 ⩽ n, q ⩽ 105 − 60 .

Страница 3 из 3

2-й этап Республиканской олимпиады по информатике 2018, 8-9 класс, *ДЕНЬ 1*
Казахстан, Декабрь, 6, 2018

Задача A. 80236. Докажи, что математик!
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

После неудачного выступления на ACM ICPC 2018-2019, NEERC - Northern Eurasia Finals, команда Хранители335 решила подтянуть свои знания математики, ибо на этом контесте они не решили
элементарную задачу по теории чисел. Сегодня один из членов команды придумал задачу, где надо
просто определить является ли площадь треугольника целочисленной. Ваша задача состоит в том,
чтобы помочь этим ребятам.

Формат входных данных
В первой строке записаны три целых числа a, b и c (1 ⩽ a, b, c ⩽ 5000) - длины сторон загаданного
треугольника.

Формат выходных данных
Выведите единственное число — площадь треугольника если она является целочисленной. В
остальных случаях выведите -1.

Примеры
стандартный ввод

стандартный вывод

3 4 5

6

5 8 5

12

3 3 3

-1

Страница 1 из 3

2-й этап Республиканской олимпиады по информатике 2018, 8-9 класс, *ДЕНЬ 1*
Казахстан, Декабрь, 6, 2018

Задача B. Формат времени
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

Вам даны два момента времени, причем гарантируется что они оба находятся в течении одних суток и первый из них находится строго раньше второго. По данной информации определите,
использовался ли для их записи 12 часовой или 24 часовой формат.
Напомним, что в 12 часовом формате часы записываются целыми числами с 1 до 12, в то время,
как в 24 часовом нумерация начинается с 0 до 23 включительно. Для лучшего понимания ознакомьтесь с тестовыми примерами.

Формат входных данных
В первой и второй строках находятся первых и второй момент времени соответственно.
Времена заданы в формате HH:MM (00 ⩽ HH ⩽ 23, 00 ⩽ MM ⩽ 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

Страница 2 из 3

2-й этап Республиканской олимпиады по информатике 2018, 8-9 класс, *ДЕНЬ 1*
Казахстан, Декабрь, 6, 2018

Задача C. Уравнитель
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

У Жарасхана есть массив a из N чисел,к каждому числу массива Жарасхан должен применить
лишь одну операцию. Есть три типа операции:
1. Добавить к числу один.
2. Отнять от числа один.
3. Добавить к числу ноль.
К каждому элементу массива нужно применить одну из трех операции так, чтобы после применения операций ко всем элементам массива, количество одинаковых чисел в массиве стало максимальным. Помогите Жарасхану с этой непростой задачей.

Формат входных данных
В первой строке входных данных дано одно целое число N - размер массива. Во второй строке
входных данных даны элементы массива ai .

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

Система оценки
Данная задача имеет 4 подзадачи:
1. 1 ⩽ N ⩽ 2. Оценивается в 10 баллов.
2. 1 ⩽ N ⩽ 102 и 1 ⩽ ai ⩽ 10. Оценивается в 20 баллов.
3. 1 ⩽ N ⩽ 105 и 1 ⩽ ai ⩽ 2. Оценивается в 20 баллов.
4. 1 ⩽ N ⩽ 105 и 1 ⩽ ai ⩽ 105 . Оценивается в 50 баллов.

Примеры
стандартный ввод
7
3 1 4 1 5 9 2
10
1 2 3 4 5 6 7 8 9 10

стандартный вывод
4
3

Замечание
В первом тесте можно изменить массив в такой вид: 2,2,3,2,6,9,2

Страница 3 из 3

2-й этап Республиканской олимпиады по информатике 2018, 10-11 класс, *ДЕНЬ 2*
Казахстан, Декабрь, 7, 2018

Задача A. Делится?
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

ОМА решил придумать свой признак делимости на 8. ОМА будет считать что число делится на
8 если существует перестановка цифр числа такая что новое число было без лидирующих нулей и
число делится на 8. Вам надо сказать делится ли число на 8 по правилам ОМЫ.

Формат входных данных
В первой строке дано цело число n (1 ⩽ n ⩽ 103 ) - длинна числа.
Во второй строка дана строка состоящая из цифр 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 ⩽ 100)
Subtask 2: (n ⩽ 1000)

Страница 1 из 3

2-й этап Республиканской олимпиады по информатике 2018, 10-11 класс, *ДЕНЬ 2*
Казахстан, Декабрь, 7, 2018

Задача B. Депозит
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

У Жарасхана есть депозит в банке дураков. Сумма денег может быть отрицательной. Каждый
день депозит пополняется на заранее известный процент. А также, Жарасхан может частично изымать деньги из этого депозита в любой момент когда ему будут нужны деньги. Но система банка
работает таким образом, что можно изымать только определенный процент от денег в депозите.
У Жарасхана есть история операций по депозиту за каждый день в виде процентов. Изначально
у Жарасхана есть s денег на депозите. Если Жарасхан изымал деньги то процент отрицательный,
если банк пополнял то положительный соответственно.
Жарасхану стало интересно, на какой день у него была максимально возможная сумма и на
какой минимальная.
Так как Жарасхан очень занят работой, он попросил вас найти те самые дни.

Формат входных данных
В первой строке входного файла заданы два целых числа n (1 ⩽ n ⩽ 25) - количество дней
в истории, s (−100 ⩽ s ⩽ 100) - изначальная сумма у Жарасхана на депозите. Во второй строке
входного файла заданы n чисел ai (−2 ⩽ ai ⩽ 2) - коэффициент процента на i-й день. Каждое ai
задано с не более двумя знаками после запятой.

Формат выходных данных
Выведите два целых числа - день в котором у Жарасхана была максимально возможная сумма
и день в котором у Жарасхана была минимально возможная сумма на депозите. Если соответствующих дней несколько - выведите самый ранний.

Система оценки
Данная задача состоит из 4 подзадач:
1. n = 1. Оценивается в 13 баллов.
2. 0 ⩽ ai ⩽ 2. Оценивается в 5 баллов.
3. 1 ⩽ n ⩽ 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. Соответственно на второй
день имеется минимально возможная сумма и на последнем максимальная.
Во втором тестовом примере, так как сумма только возрастает изначальная сумма является
минимальной.

Страница 2 из 3

2-й этап Республиканской олимпиады по информатике 2018, 10-11 класс, *ДЕНЬ 2*
Казахстан, Декабрь, 7, 2018

Задача C. Сумма квадратов
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

Даны два массива целых чисел длинны n. Даются q запросов. Каждый запрос состоит из чисел
l и r, после каждого запроса требуется вывести чему равна сумма квадратов разностей чисел a[i] и
b[i] где i= l, l+1,.., r.

Формат входных данных
Первая строка содержит числа n, q, (1 ⩽ n, q ⩽ 100000)
Вторая строка содержит массив n целых чисел(массив a)
Вторая строка содержит массив n целых чисел(массив b)
(−100000 ⩽ a[i], b[i] ⩽ 100000), i = 1, 2, ... , n
Следующие q строк содержат числа l, r, (1 ⩽ l ⩽ r ⩽ n)
Система оценки:
Для 40% тестов - (1 ⩽ n, q ⩽ 100)
Для 60% тестов - (1 ⩽ n, q ⩽ 100000)

Формат выходных данных
В каждой строке выведите ответы на запросы

Пример
стандартный ввод
3
1
1
2

1
0 5
2 3
3

стандартный вывод
8

Страница 3 из 3

2-й этап Республиканской олимпиады по информатике 2018, 8-9 класс, *ДЕНЬ 2*
Казахстан, Декабрь, 7, 2018

Задача A. Крутой подарок
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

У Темирлана недавно был день рождения. Из его друзей самый оригинальный подарок решил
сделать его друг, Айсултан. Айсултан знает, что Темирлан любит крутые числа. Число называется
крутым, если оно является квадратом целого числа. Например, 0, 9, 121 — крутые числа; а 50, 3,
12 — не крутые числа.
В распоряжении Айсултана есть последовательность из n целых чисел — a1 , a2 , a3 , ..., an . Чтобы
сообразить подарок, Айсултан берет два числа из этой последовательности aj и ai таких, что j < i
и если число aj ∗ ai является крутым, то он подарит произведение этих двух чисел Темирлану.
Помогите понять Айсултану, сколькими способами он может это сделать. Формально, найдите
количество пар чисел (aj , ai ) таких, что j < i и произведение aj ∗ ai является крутым числом.

Формат входных данных
Первая строка входных данных содержит одно число n — размер последовательности Айсултана
(1 ⩽ n ⩽ 103 ).
Вторая строка входных данных содержит n целых чисел a1 , a2 , a3 , ..., an через пробел — последовательность Айсултана (−1000 ⩽ ai ⩽ 1000).

Формат выходных данных
В единственной строке выведите одно число — ответ на задачу.

Примеры
стандартный ввод

стандартный вывод

4
1 0 1 1

6

2
-8 -2

1

3
1 16 4

3

1
0

0

Замечание
Данная задача содержит 3 подзадачи.
1. 0 ⩽ ai ⩽ 1 для всех 1 ⩽ i ⩽ n.
2. n = 2, −1000 ⩽ ai ⩽ 1000.
3. Ограничения из условия.
В первом примере всего существует 6 пар чисел и все они являются квадратами числа 0 или 1.
Во втором примере единственная пара при произведении дает 16, что является квадратом целого
числа.
В третьем примере все три пары (1, 16), (1, 4), (16, 4) в произедении дают квадрат целого числа.
В четвертом примере нет пар.

Страница 1 из 3

2-й этап Республиканской олимпиады по информатике 2018, 8-9 класс, *ДЕНЬ 2*
Казахстан, Декабрь, 7, 2018

Задача B. Делится?
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

ОМА решил придумать свой признак делимости на 8. ОМА будет считать что число делится на
8 если существует перестановка цифр числа такая что новое число было без лидирующих нулей и
число делится на 8. Вам надо сказать делится ли число на 8 по правилам ОМЫ.

Формат входных данных
В первой строке дано цело число n (1 ⩽ n ⩽ 103 ) - длинна числа.
Во второй строка дана строка состоящая из цифр 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 ⩽ 100)
Subtask 2: (n ⩽ 1000)

Страница 2 из 3

2-й этап Республиканской олимпиады по информатике 2018, 8-9 класс, *ДЕНЬ 2*
Казахстан, Декабрь, 7, 2018

Задача C. Депозит
Имя входного файла:
Имя выходного файла:
Ограничение по времени:
Ограничение по памяти:

стандартный ввод
стандартный вывод
1 секунда
256 мегабайт

У Жарасхана есть депозит в банке дураков. Сумма денег может быть отрицательной. Каждый
день депозит пополняется на заранее известный процент. А также, Жарасхан может частично изымать деньги из этого депозита в любой момент когда ему будут нужны деньги. Но система банка
работает таким образом, что можно изымать только определенный процент от денег в депозите.
У Жарасхана есть история операций по депозиту за каждый день в виде процентов. Изначально
у Жарасхана есть s денег на депозите. Если Жарасхан изымал деньги то процент отрицательный,
если банк пополнял то положительный соответственно.
Жарасхану стало интересно, на какой день у него была максимально возможная сумма и на
какой минимальная.
Так как Жарасхан очень занят работой, он попросил вас найти те самые дни.

Формат входных данных
В первой строке входного файла заданы два целых числа n (1 ⩽ n ⩽ 25) - количество дней
в истории, s (−100 ⩽ s ⩽ 100) - изначальная сумма у Жарасхана на депозите. Во второй строке
входного файла заданы n чисел ai (−2 ⩽ ai ⩽ 2) - коэффициент процента на i-й день. Каждое ai
задано с не более двумя знаками после запятой.

Формат выходных данных
Выведите два целых числа - день в котором у Жарасхана была максимально возможная сумма
и день в котором у Жарасхана была минимально возможная сумма на депозите. Если соответствующих дней несколько - выведите самый ранний.

Система оценки
Данная задача состоит из 4 подзадач:
1. n = 1. Оценивается в 13 баллов.
2. 0 ⩽ ai ⩽ 2. Оценивается в 5 баллов.
3. 1 ⩽ n ⩽ 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. Соответственно на второй
день имеется минимально возможная сумма и на последнем максимальная.
Во втором тестовом примере, так как сумма только возрастает изначальная сумма является
минимальной.

Страница 3 из 3