Задача A
Условие:
Есть дом, в котором расположены 10 000 квартир, пронумерованных от 1 до 10 000. Назовем номер квартиры скучным, если ее номер состоит из одинаковых цифр. Примерами скучных квартир являются 11,2,777,9999 и так далее. Наш герой очень наглый и он любит звонить в домофоны всех скучных квартир до тех пор, пока кто-то не ответит, в следующем порядке: сначала он обзванивает квартиры, состоящие из цифр 1, в возрастающем порядке (1,11,111,1111); затем он обзванивает квартиры, состоящие из цифр 2, в возрастающем порядке (2,22,222,2222); и так далее. Житель скучной квартиры xx ответил на звонок. После этого наш герой перестал обзванивать кого-либо еще. Наш герой хочет знать, как много цифр он суммарно нажал. Ваша задача — помочь посчитать ему суммарное количество нажатых клавиш. Например, если житель квартиры 22 ответил, то наш герой звонил в квартиры с номерами 1,11,111,1111,2,22. Таким образом, суммарное количество нажатий равно 1+2+3+4+1+2=13. Вам нужно ответить на tt независимых наборов тестовых данных.
Решение:
Исходя из условия, нетрудно понять, что из одной цифры можно сделать 4 номера и суммарно в них будет 10 цифр. Значит, для начала нужно посчитать, сколько можно сделать номеров, состоящих из цифр, меньших чем те, которые используются в числе x. Далее, нужно посчитать количество номеров квартир состоящих из цифр числа x и не больших, чем оно само.
Задача B
Условие:
Есть книжная полка, на которой может уместиться n книг. i-я позиция на книжной полке ai=1, если на этой позиции находится книга, и ai=0 иначе. Гарантируется, что есть как минимум одна книга на книжной полке. За один ход вы можете выбрать какой-то непрерывный отрезок [l;r], состоящий из книг (то есть для каждого i от l до r должно выполняться условие ai=1), и: Сдвинуть его вправо на 1: переместить книгу с индекса i в i+1 для всех l≤i≤r. Этот ход можно свершить только тогда, когда r+1≤n и на позиции r+1 нет книги. Сдвинуть его влево на 1: переместить книгу с индекса i в i−1 для всех l≤i≤r. Этот ход можно свершить только тогда, когда l−1≥1 и на позиции l−1 нет книги. Ваша задача — найти минимальное количество ходов, необходимое, чтобы собрать все книги на полке в непрерывный (последовательный) отрезок (т.е. отрезок без промежутков). Например, в a=[0,0,1,0,1] есть промежуток между книгами (a4=0 при a3=1 и a5=1), в a=[1,1,0] нет промежутков между книгами и в a=[0,0,0] тоже нет промежутков между книгами. Вам нужно ответить на t независимых наборов тестовых данных.
Решение:
Решение этой задачи немногим сложнее, чем в задаче A. Нам нужно лишь сдвинуть книги самым оптимальным способом, то есть друг к другу. Из этого вытекает логический вывод, что нужно лишь посчитать количество пустых расстояний между книгами (количество нулей между крайними единицами, которое надо найти при помощи цикла). Так как за один ход мы можем сдвинуть книги лишь на одно такое расстояние, то найденного нами значения кол-ва нулей будет достаточно, чтобы ответить на вопрос, поставленный в этой задаче.
Задача C
Условие:
В аквариуме есть n пираний с размерами a1,a2,…,an. Пираньи пронумерованы слева направо в том порядке, в котором они живут в аквариуме. Ученые из Берляндского государственного университета хотят узнать, есть ли в аквариуме доминирующая пиранья. Пиранья называется доминирующей, если она может съесть всех пираний в аквариуме (за исключением самой себя, конечно же). Другие пираньи не будут делать ничего, пока доминирующая пиранья будет есть их. Поскольку аквариум довольно узкий и длинный, пиранья может есть только одну из соседних пираний за один ход. Пиранья может делать сколько угодно ходов (конечно же, до тех пор, пока она может). Более детально: Пиранья i может съесть пиранью i−1, если пиранья i−1 существует и ai−1<ai. Пиранья i может съесть пиранью i+1, если пиранья i+1 существует и ai+1<ai. Когда пиранья ii съедает какую-либо пиранью, ее размер увеличивается на единицу (ai становится равным ai+1). Ваша задача — найти любую доминирующую пиранью в аквариуме или определить, что таких пираний нет. Обратите внимание, что вам нужно найти любую (ровно одну) доминирующую пиранью, вам не нужно находить всех подходящих пираний. Например, если a=[5,3,4,4,5], то третья пиранья может быть доминирующей. Рассмотрим последовательность ее передвижений: Пиранья съедает вторую пиранью, и a становится равным [5,5,4,5] (подчеркнутая пиранья — наш кандидат). Пиранья съедает третью пиранью, и a становится равным [5,6,5]. Пиранья съедает первую пиранью, и a становится равным [7,5]. Пиранья съедает вторую пиранью, и a становится равным [8]. Вам нужно ответить на t независимых наборов тестовых данных.
Решение:
Разумеется, самым главным и наиболее подходящим претендентом на доминирующую пиранью, является рыба с самым наибольшим показателем ai. Однако таких пираний может быть несколько. Для начала нужно найти их количество. Если оно равно кол-ву рыб в аквариуме, значит каждый сосед каждой рыбы не может быть съеден. В противном случае, ответ найдётся всегда, им будет являться любая рыба с максимальным показателем, имеющая хотя бы одного более мелкого соседа, так как после его съедения эта пиранья станет фаворитом среди остальных и ей будет «по зубам» любой конкурент, нужно лишь пробежавшись по массиву найти первую попавшуюся рыбку, удовлетворяющую всем вышеперечисленным условиям.
