1 Ответ
Задание 1. Освещение комнаты
У Антона в комнате поменяли люстру, и теперь ему нужно купить новую лампочку. Обычная лампочка дешевле, но потребляет больше электричества. Энергосберегающая стоит дороже изначально, зато экономит электричество. Антон решил найти экономическую выгоду энергосберегающих лампочек.
Обычная лампочка стоит a рублей и потребляет x ватт в час. Энергосберегающая лампочка стоит b рублей и потребляет y ватт в час. Стоимость электроэнергии составляет p копеек за 1 ватт в час.
Через сколько часов энергосберегающая лампочка начнёт окупаться и становиться экономически выгодной, то есть стоимость её покупки и использования станет не больше, чем у обычной?
Программа получает на вход 5 целых неотрицательных чисел a, x, b, y и p, записанных в отдельных строках, — цена обычной лампочки, энергопотребление обычной лампочки, цена энергосберегающей лампочки, энергопотребление энергосберегающей лампочки и цена 1 ватта электроэнергии соответственно. Все числа не превосходят 109. Гарантируется, что a<b и x>y.
Задание 2. Инопланетные часы. Сутки на планете другой звёздной системы длятся h часов, а час длится m минут. Цифровое табло робота на поверхности этой планеты показывает время x часов y минут. Через сколько минут цифровое табло будет показывать время, для которого сумма чисел, обозначающих часы и минуты, будет равна текущей сумме чисел на часах?
Программа получает на вход четыре целых неотрицательных числа h, m, x и y, записанных в отдельных строках, — длительность суток в часах, длительность часа в минутах, часы и минуты, которые отображаются на цифровом табло робота (0⩽x<h, 0⩽y<m).
Все числа не превосходят 108. Гарантируется, что h<m.
Программа должна вывести одно целое число — через сколько минут цифровое табло будет показывать время, когда сумма значений часов и минут будет равна сумме чисел в записи текущего времени.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long в C++, тип long в Java и C#).
Задание 3. Чернильная история. В бесконечной клетчатой тетради школьник оставил n клякс. Координаты каждой клетки задаются парой целых чисел (x, y), где x — номер столбца (считая слева), а y — номер строки (считая снизу).
Изначально i-я клякса находится в клетке (xi, yi).
Как только школьник отворачивается, все кляксы одновременно начинают движение, и за 1 секунду каждая может сделать одно из следующих действий:
остаться в своей текущей клетке;
переместиться в одну из 8 соседних клеток (по горизонтали, вертикали или диагонали).
За какое наименьшее число секунд все кляксы смогут собраться в одной клетке?
Первая строка содержит одно целое число n (1⩽n⩽200000) — количество клякс.
Далее идут 2n строк. В каждой паре строк в первой строке находится целое число xixi, во второй — yi (−109⩽xi, yi⩽109). xi и yi — начальные координаты i-й кляксы.
Выведите одно целое число — минимальное время в секундах, за которое все кляксы смогут собраться в одной клетке.
Задание 4. Врата кибернетиков
В городе кибернетиков стоят энергетические ворота, работающие на особой строке S длины nn, состоящей из символов «1» (синий свет) и «2» (красный свет). Для стабильной работы системы требуется, чтобы общее количество синих и красных символов было равным. Гарантируется, что строка S содержит ровно n2 символов «1» и n2 символов «2» (число nn чётное).
Однако ворота не откроются, если в строке встречается «резонансный дисбаланс» — две двойки («2») или две единицы («1») подряд. Такая комбинация приводит к сбою и блокировке системы.
Для устранения дисбаланса инженеры могут менять местами соседние символы в строке. При этом общее количество единиц и двоек должно остаться неизменным. Каждая такая перестановка считается одной операцией.
Требуется найти минимальное число операций обмена соседних символов, необходимое для того, чтобы избавиться от всех вхождений подстроки «2» и подстроки «1» в строке S.
В первой строке находится целое чётное число n (2⩽n⩽100000) — длина строки S.
Во второй строке находится строка S, состоящая из символов «1» и «2». Гарантируется, что количество символов «1» равно количеству символов «2».
Выведите одно целое число — минимальное количество операций.
Разбор первого примера:
Исходная строка: «21».
Проблема: подстрока «1» на позициях 2−3.
Оптимальное решение: обмен символов на позициях 2 и 3.
Результат: «21» ⟶ нет «1» и «2».
Количество операций: 1.
Разбор второго примера:
Исходная строка: «12221121».
Проблема: подстрока «222» на позициях 2−4 и подстрока «11» на позициях 5−6.
Оптимальное решение:
Обмен символов на позициях 1 и 2: «21221121».
Обмен символов на позициях 5 и 6: «21212121».
Результат: «21212121» ⟶ нет «1» и «2».
Количество операций: 2.
Задание 5. Древний свиток. В руки учёных-шифровальщиков попал древний свиток с длинной последовательностью из n цифр (от 0 до 9). Для расшифровки тайного послания они изучают отдельные фрагменты этой последовательности.
Потенциал фрагмента с позиции l по позицию rr определяется по следующему правилу: рассматриваются все возможные пары различных позиций i и j внутри этого отрезка (l⩽i, j⩽r, i≠j). Цифра на позиции ii становится цифрой десятков, а цифра на позиции j -цифрой единиц, образуя двузначное число. Потенциал отрезка — это сумма всех таких полученных чисел.
Вам нужно помочь учёным: для заданной последовательности цифр длиной n ответить на q запросов. В каждом запросе даны границы отрезка [l,r] и требуется вычислить его потенциал.
В первой строке находится одно целое число n (1⩽n⩽100000) — длина последовательности.
Во второй строке содержится строка ss длиной n, состоящая только из цифр (от 0 до 9).
В третьей строке находится одно целое число q (1⩽q⩽100000) — количество запросов.
Следующие 2⋅q строк описывают запросы. В каждом запросе:
на первой строке содержится число l;
на второй строке содержится число r.
Гарантируется, что 1⩽l⩽r⩽n. Позиции в последовательности нумеруются с 1.
Для каждого запроса в отдельной строке выведите одно целое число — потенциал отрезка [l,r].
Строка 789.
Первый запрос l=1, r=3. Все возможные пары (i,j):
(1,2) : 7,8⟶78
(1,3) : 7,9⟶79
(2,1) : 8,7⟶87
(2,3) : 8,9⟶89
(3,1) : 9,7⟶97
(3,2) : 9,8⟶98
Потенциал отрезка [1,3]: 78+79+87+89+97+98=528.
Второй запрос l=1, r=2. Все возможные пары (i,j):
(1,2) : 78
(2,1) : 87
Потенциал отрезка [1,2]: 78+87=165.
