Задания для олимпиады [Завершена]

Олимпиада завершена, более ответы не принимаются. В скором времени опубликуем итоги.
Всем спасибо за участие!

Пришло время для заданий олимпиады!
Решать задачи можно на любом из языков высокого уровня (предпочтительней: python, C#, Pascal, Java). Для каждого задания нужно написать программу-решение, которую необходимо отправить на почту neltsker@gmail.com. Задания принимаются до 22:00 этого же дня, только с почтовых адресов, указанных при регистрации. Прислать необходимо архив с именем участника, в теме письма указать: «Олимпиада», в архиве файлы с решением подписанные «Задача N». Задания различаются по сложности,
количество баллов за верное решение указано возле каждого задания . Удачи!

Задание 1 (1 балл):
Учитывая целое число n, вернуть true, если оно является степенью двойки. В противном случае вернуть false.

Задание 2 (1 балл):
Ввести слово с клавиатуры. Определить, верно ли, что оно начинается и оканчивается на одну и ту же букву.

Задание 3 ( 2 балла):
Исключительно на C#!
Сложить: a=0,00000000001 и b=0,00000000001, где a — это число от 1 до 10 вводимое пользователем, а b — это случайное число от 1 до 10 с двумя знаками после запятой
Пояснение: числа а и b имеют 10 нулей после запятой и 11 символ это число введенное пользователем(a) или сгенерированное(b)

Задание 4 (1 балл):
Введите значения a и b, сложите их и переведите в двоичную систему счисления.

Задание 5 (2 балла):
Дан набор целых чисел, который может содержать дубликаты. Ваша задача – вывести все возможные подмножества.
Пример: nums = [2,2,3], решение:
[
[2],
[3],
[2,2,3]
[2,3]
[2,2]
[] //это тоже верно.
]

Задание 6 (4 балла):
На кольцевом маршруте есть n заправок, где количество газа на i-ой станции равно gas[i]. У вас есть машина с неограниченным бензобаком, и проезд от станции i до станции i+1 стоит i количества бензина. Вы начинаете свой путь с пустым баком на одной из заправок.
Имея 2 массива целых чисел, верните индекс начальной заправки, если вы можете проехать по кругу один раз по часовой стрелке, в противном случае верните -1(или Exception, на ваш вкус и цвет).
Пример 1: gas = [1,2,3,4,5], cost = [3,4,5,1,2].
Допустим, Вы стартуете с станции 3 (индекс 3). Вам дают 4 единицы газа. Топлива в вашем бензобаке = 0 + 4 = 4.
Отправляйтесь на станцию 4. Ваше топливо в бензобаке = 4 — 1 + 5 = 8.
Отправляйтесь на станцию 0. Ваше топливо в бензобаке = 8 — 2 + 1 = 7
Отправляйтесь на станцию 1. Ваше топливо в бензобаке = 7 — 3 + 2 = 6.
Отправляйтесь на станцию 2. Ваше топливо в бензобаке = 6 — 4 + 3 = 5.
Поездка на станцию 3. Стоимость 5. У вас достаточно бензина, чтобы вернуться на станцию 3.
Поэтому ответ 3 будет верным к задаче.
Пример 2: gas = [2,3,4], cost = [3,4,3]
Вы не можете начать со станции 0 или 1, так как не хватает бензина, чтобы добраться до следующей станции.
Начнем со станции 2 и заправимся 4 единицами газа. Топливо в бензобаке = 0 + 4 = 4
Отправляйтесь на станцию 0. Топливо в бензобаке = 4 — 3 + 2 = 3
Поездка на станцию 1. Топливо в бензобаке = 3 — 3 + 3 = 3
Вы не можете вернуться на станцию 2, так как для этого требуется 4 единицы газа, а у вас есть только 3.
Следовательно, вы не можете объехать трассу один раз, где бы вы ни стартовали.

Задание 7 (5 баллов):
Вам необходимо обновить определение лексикографического порядка, введя новый порядок алфавита.
В новом порядке алфавита первой буквой будет буква Y1, второй -Y2,…, 26-й -Y26.
Теперь вам нужно отсортировать N слов S1, S2, …, Sn, используя лексикографический порядок с новым алфавитом.
Формат входных данных:
В первой строке вводится строка Y (| Y| = 26, Y — это перестановка строки abcd…xyz) — описание нового порядка алфавита.
Во второй строке вводится одно целое число N (1 ≤ N ≤ 5 * 10⁴) — число строк, которые вы хотите отсортировать. Затем, в следующих N строках вводится по одной строке S_i (1 < | S_i| < 10).
Выведите те же N строк, отсортированные в лексикографическом порядке с новым алфавитом.
Вам нужно считывать входные данные из стандартного потока ввода и выводить ответ в стандартный поток
вывода.

Пример данных:

Задание 8 (4 балла):
Вы решили сыграть с вашим другом в игру. Перед вами на столе лежит N карточек (N -нечетное), на карточке 1 написано число А₁, на карточке 2 — А₂. . ., на карточке N — A_N. Вы хотите, чтобы все номера на карточках были попарно различны. Для того, чтобы добиться этого, вы можете несколько (возможно, 0) раз указать вашему другу на 3 различных карточки, которые лежат на столе. Затем ваш друг заберет себе ровно две карточки среди тех 3, на которые вы ему указали — карточку с максимальным и минимальным числом.
Вам стало интересно, какое максимальное число карточек может остаться на столе, чтобы все числа, написанные на них, были попарно различны, после нескольких (возможно, 0) описанных операций.
Обратите внимание, что так как N — нечетное, то вы всегда можете оставить на столе ровно 1 карточку.
Формат входных данных:
В первой строке вводится одно целое число N (3 ≤ N ≤ 10⁵) — количество карт на столе. Гарантируется, что N-
нечетное.
Во второй вводятся N целых чисел А_1, А₂, А₃, …, A_N (1 ≤ A_i ≤ 10⁵) — номера, написанные на картах.
Формат выходных данных:
Выведите одно число — ответ на задачу, то есть максимальное количество карт, которое вы можете оставить на столе, при условии, что числа написанные на карточках должны быть различными.

Примеры данных:
Ввод: Вывод:
5 3
1 2 5 5 5

Задание 9 (5 баллов):
Ваш друг Владимир загадал массив А, состоящий из N элементов А_1, А₂, А₃,…, A_n. Вам нужно найти сумму всех элементов массива А, то есть А₁ + А₂ + А₃ + . . . + A_n. Владимир обещал рассказать вам Q фактов про массив. i-й факт про массив — сумма чисел на отрезке [l_i , r_i], то есть А₁ + A_{l i+1} +… + A _ri
Определите, сможете ли вы найти сумму всех элементов массива А, после того, как Владимир расскажет
вам все Q фактов про массив.
Формат входных данных
В первой строке вводятся два целых числа N, Q ( 1 ≤ N,Q ≤ 2 * 10⁵) — длина массива и число фактов, которые обещал рассказать Владимир.
В следующих Q строках вводятся по 2 числа l_i , r_i (1 ≤ l_i ≤ r_i ≤ N) — описания фактов.
Формат выходных данных:
Выведите ответ на задачу -«Yes», если вы сможете найти сумму всех элементов массива А, и «No» иначе.

Пример:
ввод:
4 3
1 2
2 3
3 4
вывод: Yes

Задание 10 (4 балла):
Вам дана строка S, состоящая только из символов «X» и «.»
Вы хотите заменить в ней не более К символов «.» на символы «X«.
Вам нужно найти наибольшее количество символов «X«, стоящих подряд, которое может встретиться после того, как вы замените не более К символов.

Формат входных данных:
В первой строке вводится одна строка S (1 ≤ |S| ≤ 2 • 10⁵, строка S состоит только из символов
«X» и «.«)
Во второй строке вводится одно целое число К (0 ≤ K ≤ 2 • 10⁵ ) — количество замен, которое вы
можете сделать.
Формат выходных данных:
Выведите одно число — максимальное количество символов, стоящих подряд, которое можно
получить в результате описанной выше замены.

Пример:
Ввод: X…X..XX 3
Вывод: 6

Задание 11 (4 балла):
Две группы студентов решали контрольную, состоящую из N задач. Известно, что первая группа
решила суммарно А задач, а вторая группа — В задач, при этом каждый студент решил хотя бы одну
задачу. Вам нужно определить, могло ли быть в первой группе студентов больше, чем во второй. Напишите
программу, позволяющую узнать ответ на этот вопрос.
Формат входных данных:
Вводятся три целых числа, каждое в своей строке — A, B, N (0 ≤ A, B ≤ 10⁴ , 1 ≤ N ≤ 10⁴ ).
Формат выходных данных:
Выведите «Да», если в первой группе могло быть больше людей, чем во второй. В любом другом
случае выведите «Нет».

Пример 1: Пример 2:
ввод: 60 30 4 ввод: 30 30 1
вывод: Да вывод: Нет

Задание 12 (5 баллов):
Вам даны три неизвестных числа, обозначенных а, b, с, а также все попарные сравнения этих чисел
друг с другом. Напишите программу, которая выведет эти числа в порядке возрастания (не убывания).

Формат входных данных:
Вводятся три строки. В первой записан результат сравнения между собой чисел а и b. Во второй
строке — результат сравнения а и с. В третьей строке — результат сравнения b и с. Результат
сравнения выражается соответствующим знаком — символом «<«, «>» или «=».
Формат выходных данных
Выведите символы а, b, с без разделителей в порядке возрастания соответствующих
чисел, каждое следующее число должно быть не меньше предыдущего. Если возможных вариантов
ответа несколько, выведите их все в лексикографическом порядке (порядок, использующийся для
сравнения строк в словаре).

Пример 1: Пример 2:
ввод: > > > ввод: = > >
вывод: cba вывод: cab cba

Задание 13 (4 балла):
Вам дано длинное натуральное число N. Вы получаете из него число X повторяющимися операциями деления на 10, пока деление возможно нацело. Напишите программу, вычисляющую количество нулей в десятичной записи числа Х.
На вход программе подается одно натуральное число N ( 1 ≤ N ≤ 10¹² ).
Выведите одно число — количество нулей в десятичной записи числа Х.

Пример:
ввод: 100500
вывод: 2

Задание 14 (6 баллов):
Вы загадали натуральное число п и решили заполнить квадратную таблицу размером п × п
буквами по «диагональному правилу» — клетки, находящиеся на двух самых длинных диагоналях,
должны содержать символ «а». Пустые клетки, соседние с «а»-клетками, нужно заполнить символом
«b», и так далее по алфавиту. Когда придет время заполнять соседей «z»-клеток, в них нужно записать
символ «а». Напишите программу, которая строит и выводит получившуюся таблицу.

Входные данные содержат одно целое число п (1 ≤ n ≤ 100) — высоту и ширину таблицы.
Выведите п строк по п символов — таблицу, заполненную по диагональному правилу.

Пример:
ввод: 5 вывод: abcba
babab
cbabc
babab
abcba

Задача 15 (6 баллов):
Перестановкой размера п называется массив [a₁, а₂, …, a_n] различных чисел от 1 до п . Алексей
называет красотой перестановки [a₁, а₂, …, a_n] число ( a₁ + а₂ × 2 + … + a_n × n), то есть
∑ _i=1^n Он хочет посчитать количество перестановок, красота которых делится на k.
Даны числа п и k, найдите количество перестановок размера п, красота которых делится на k .

Входные данные содержат два целых числа: n и k (1 ≤ n ≤ 10, 2 ≤ k ≤ 1000).
Выведите одно целое число: количество перестановок размера п, красота которых делится на k .

Пример:
ввод: 3 2 вывод: 2

Задание 16 (8 баллов):
На Марсе в сутках h часов, а в каждом часе т минут, причём т обязательно чётное. Вам дано расписание товарных поездов, которые отправляются ежедневно: i-й поезд отправляется в h_i часов, m_i минут. Дважды в час вам нужно проводить дорожные работы, каждая из который длится k минут. Было принято решение, что между моментами начала соседних работ должно проходить ровно m/2 — минут.
График работ возможно настроить: можно выбрать момент времени t (0 ≤ t ≤ m/2 ), когда
нужно закончить делать первую работу за час.
Поезд считается неудобным, если время его отправления совпадает с периодом проведения
дорожных работ. Если поезд отправляется одновременно с началом или концом работ, он не
считается неудобным. Вы хотите минимизировать число неудобных поездов, планируя график
проведения работ. Напишите программу, вычисляющую такое время t для конца работ, чтобы
количество неудобных поездов было минимальным. Таких t может быть несколько, среди них нужно
выбрать минимальное.

Первая строка содержит четыре целых числа n, h, m, k (1 ≤ n ≤ 10⁵, 1 ≤ h ≤ 10⁹, 2 ≤ m ≤ 10⁹, 1 ≤ k ≤ m/2 ) — число поездов, количество часов и минут на Марсе, а также время, которое
тратится на дорожные работы. Гарантируется, что число минут т чётное.
В следующих п строках вводится по два целых числа h_i и m_i (0 < hi < h, 0 < m; < m) — время
отправления i-го поезда, часы и минуты соответственно. Гарантируется, что все поезда отправляются
в разное время.
Выведите два числа: минимальное количество неудобных поездов и t — время окончания самой
ранней дорожной работы дня в минутах. Во второй строке через пробел выведите номера неудобных
поездов (нумерация с единицы).
Обратите внимание, что момент времени t может быть выбран так, что дорожные работы
начинаются в один час, а заканчиваются в следующий. Эта работа будет считаться выполненной в тот
час, когда она закончилась.

Пример:
ввод: 2 24 60 16 вывод:
16 0 1 0
17 15 2

Задание 17 (6 баллов):
Вам дана перестановка [p₁, p₂, …, p_n], все элементы в ней различны и являются числами от 1 до п.
Назовём группой такой упорядоченный набор индексов i₁ < i₂ < … < i_k , для которого Pi₁ , > Pi₂ >… > Pi_k .
Напишите программу, считающую количество групп размера k. В качестве ответа выведите это
число по модулю 10⁹ + 7.

Первая строка входных данных содержит два целых числа п и k (1 ≤ n ≤ 10⁵ , 2 ≤ k ≤ 10).
Следующая строка содержит перестановку — n попарно различных чисел p₁, p₂, …, p_n (1 ≤ p_i ≤ n, 1 ≤ i ≤ n).
Выведите одно число — количество групп размера k по модулю 10⁹ + 7.

Пример:
ввод: 4 3 вывод:
4 3 2 1 4