Решения всех недавно опубликованных задач ВСОШ

[Irval]

Задача 1: Путешествие поездом
Класс, в котором учится Дима, отправляется в путешествие! И, конечно же, ребята поедут поездом, в плацкартном вагоне, причём не в обычном, а в инновационном — в нём целых 11 плацкартных «купе»! Получив свой билет, Дима задумался, как можно быстро определять тех, кто едет в конкретном плацкартном «купе», а также на боковых местах, расположенных строго напротив этого «купе».

Помогие Диме определить по номеру «купе» расположенные в нём места, а также боковые места, расположенные строго напротив него (для лучшего понимания внимательно изучите рисунок).

Входные данные
В первой строке входных данных содержится целое число K (1 ≤ K ≤ 11) — номер «купе», интересующий Диму.

Выходные данные
Выведите шесть целых чисел в порядке возрастания — места, расположенные в соответствующем «купе» и строго напротив него.

Система оценки
В этой задаче 10 тестов, не считая теста из условия. За каждый пройденный тест будет начисляться 10 баллов.

Примеры

Ввод	Вывод
2	5 6 7 8 63 64

Файл с решением задачи на C++:

Пожалуйста, авторизуйтесь для просмотра ссылки.

.
Сложность алгоритма - O(1).
Время решения: 7 минут.
Идея алгоритма:

Исходя из здравого смысла, несложно понять, что первый номер в купе будет равняться 4 * K - 3, причем последний номер - 4 * K.
Если считать номера боковых мест от единицы, то на K-ом месте будут пассажиры с номерами K * 2 - 1 и K * 2. Поскольку их нумерация начинается с последнего места в вагоне, то мы должны превратить формулу первого места в 66 - (K * 2 - 1) = 67 - K*2 = 65 - (K - 1)*2.

 

[Irval]

Задача 2: Пирожки
Рядом с домом Пети расположена пекарня, в которой пекут вкусные пирожки с ягодами. Пете очень нравятся три вида пирожков: с брусникой, с черникой и с вишней. Пирожок с брусникой стоит A рублей, пирожок с черникой стоит B рублей, пирожок с вишней стоит C рублей.

Каждый день, проходя мимо пекарни, Петя покупает пирожок одного из этих трёх видов. При этом он соблюдает следующие правила:

• если в некоторый день он купил пирожок с брусникой, то на следующий день он купит пирожок с черникой;
• если в некоторый день он купил пирожок с черникой, то на следующий день он купит пирожок с вишней;
• если в некоторый день он купил пирожок с вишней, то на следующий день он купит пирожок с брусникой.

Например, если сегодня Петя купит пирожок с брусникой, то завтра он купит пирожок с черникой, послезавтра — пирожок с вишней, на следующий за послезавтра день — пирожок с брусникой, и так далее.

Зная, какой пирожок Петя купит сегодня, определите, сколько денег Петя потратит на пирожки в течение N дней, начиная с сегодняшнего.

Входные данные
В первой строке входных данных содержится целое число A (1 ≤ A ≤ 10^6) — цена пирожка с брусникой.

Во второй строке содержится целое число B (1 ≤ B ≤ 10^6) — цена пирожка с черникой.

В третьей строке содержится целое число C (1 ≤ C ≤ 10^6) — цена пирожка с вишней.

В четвёртой строке содержится целое число N (2 ≤ N ≤ 2×10^9) — количество дней, за которые нужно посчитать расходы Пети на пирожки.

В пятой строке содержится число 1, 2 или 3, указывающее, какой пирожок Петя купит сегодня. Число 1 соответствует пирожку с брусникой, число 2 — пирожку с черникой, число 3 — пирожку с вишней.

Выходные данные
Выведите единственное целое число — сумму, которую Петя потратит на пирожки.

Обратите внимание, что для больших значений N ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Система оценки
Решение, правильно работающее только для случаев, когда n ≤ 3, будет оцениваться в 9 баллов.

Решение, правильно работающее только для случаев, когда n ≤ 1000, будет оцениваться в 72 балла.

Примеры

Ввод	Вывод	Пояснение
14 12 11 7 1	88	Во всех примерах цены пирожков и количество дней, в течение которых нужно посчитать расходы Пети на пирожки, одни и те же. В первом примере первой покупкой Пети будет пирожок с брусникой. Значит, покупки Пети за семь дней могут быть описаны последовательностью брусника, черника, вишня, брусника, черника, вишня, брусника. Сумма, потраченная на покупки, составит 14 + 12 + 11 + 14 + 12 + 11 + 14 = 88 рублей.
14 12 11 7 2	86	Во втором примере первой покупкой Пети будет пирожок с черникой. Соответственно, покупки Пети за семь дней могут быть описаны последовательностью черника, вишня, брусника, черника, вишня, брусника, черника. Сумма, потраченная на покупки, составит 12 + 11 + 14 + 12 + 11 + 14 + 12 = 86 рублей.
14 12 11 7 3	85	В третьем примере первой покупкой Пети будет пирожок с вишней. Следовательно, покупки Пети за семь дней могут быть описаны последовательностью вишня, брусника, черника, вишня, брусника, черника, вишня. Сумма, потраченная на покупки, составит 11 + 14 + 12 + 11 + 14 + 12 + 11 = 85 рублей.

Файл с решением задачи на C++:

Пожалуйста, авторизуйтесь для просмотра ссылки.

.
Сложность алгоритма - O(1).
Время решения: 11 минут.
Идея алгоритма:

Если считать покупку всех трех пирожков - цикличным действием, то логично предположить, что количество полных завершений этого цикла равняется K / 3 (причем деление целочисленное с округлением вниз). Количество остальных покупок пирожков, выбивающихся из "цикла" равняется K % 3. Далее достаточно запустить цикл от 0 до AddDays-1 включительно, где, исходя из определенного дня, мы будем добавлять к итоговой сумме стоимость соответствующего пирожка.

 

[Irval]

Задача 3: Игра
На уроке информатики учитель предложил Васе сыграть в следующую игру.

На доске записаны по порядку все целые числа от 1 до N. За один ход можно стереть либо все числа, стоящие на чётных позициях, либо все числа, стоящие на нечётных позициях. После этого оставшиеся числа перенумеровываются заново слева направо; нумерация начинается с единицы.

Игра продолжается, пока на доске есть хотя бы два числа.

Вася выиграет, если после окончания игры единственным оставшимся на доске числом будет число X. Выведите последовательность ходов, которая приведёт к победе Васи. Гарантируется, что Вася всегда может победить.

Входные данные
В первой строке содержится целое число N (2 ≤ N ≤ 10^9) — начальное количество чисел на доске.

Во второй строке содержится целое число X (1 ≤ X ≤ N) — число, которое должно остаться в конце игры.

Выходные данные
Выведите последовательность целых чисел, состоящую из чисел 1 и 2 — ходов Васи. Число 1 означает, что Вася стирает все числа на нечётных позициях, число 2 — на чётных.

Каждый ход Васи выводите на отдельной строке.

Система оценки
В этой задаче 20 тестов, не считая тестов из условия. За каждый пройденный тест будет начисляться 5 баллов.

На тесты наложены следующие ограничения:

Номера тестов	Дополнительные ограничения
1 – 2	Тесты из условия
3 – 10	N ≤ 1000
11	X = 1
12 – 14	X = N
15 – 22	без дополнительных ограничений

Примеры

Ввод	Вывод	Пояснение
10 5	2 2 1	На доске записаны числа: 1 2 3 4 5 6 7 8 9 10 Первым ходом Вася стирает все числа на чётных позициях, на доске остаются числа: 1 3 5 7 9 Затем позиции оставшихся чисел перенумеровываются — то есть оставшиеся после первого хода Васи числа получат номера от 1 до 5. Вторым ходом Вася снова удаляет все числа на чётных позициях, на доске остаются числа: 1 5 9 Третьим ходом Вася удаляет все числа на нечётных позициях, и на доске останется только число 5, которое и было нужно.
6 6	1 2 1	Во втором примере выписаны числа 1 2 3 4 5 6 Вася стирает числа на нечётных позициях, остаются 2 4 6 Вася стирает число 4, которое стоит на чётной позиции. Остаются 2 6 Вася стирает число 2, которое стоит на нечётной позиции. Осталось число 6.

Файл с решением задачи на C++:

Пожалуйста, авторизуйтесь для просмотра ссылки.

.
Сложность алгоритма - O(logN).
Время решения: 10...20 минут.
Идея алгоритма:

В решении данной задачи достаточно понять простую вещь - мы всегда удаляем элементы, стоящие на позициях, противоположных по четности нашему X. В противном случае, в одном из шагов может быть удалено исходное число, а следовательно, задача будет провалена.
Решение с использованием массивов и честным пересчетом позиции не будет набирать полный балл, из-за Time-Limit. Предлагаю воспользоваться оптимизацией, связанной с представлением массива только исходя из X и N. Нам не нужно знать все его элементы, если важна только четность их позиции и положение X относительно начала.
При каждой итерации мы делим N и X на 2, но если мы удаляем четные числа, а N%2 == 1 (аналогично для X), то мы привляем 1 к значению N(X), что означает удаление меньшего количества внутренних элементов, из-за чего длина(индекс) будет сдвигаться на +1.

 

[Misery]

Молодец Ирвал, ты абсолютно точно умнее некоторых участников данной олимпиады. Накидайте парню лукосов.

 

[Irval]

Задача 4: Марсоход
Учёные рассматривают участок поверхности Марса, который можно представить в виде последовательности точек с высотами H1, H2, ..., HN. Высота между двумя соседними точками меняется равномерно.

Для исследований необходимо собрать информацию с любого отрезка участка поверхности, длина которого равна K. Для этого запланировано выбрать некоторую точку L, высадить туда марсоход и отправить его последовательно по точкам HL, HL+1, ..., HL+K.

Марсоход работает от аккумулятора. На перемещение на одну единицу вверх марсоход тратит одну единицу энергии. При перемещении на одну единицу вниз марсоход накапливает одну единицу энергии. На горизонтальное перемещение энергия не тратится. Изначально у марсохода достаточно энергии, чтобы изучить любой отрезок интересующего учёных участка, а максимальный возможный запас аккумулятора не ограничен.

Учёные хотят, чтобы для дальнейших исследований у марсохода осталось как можно больше энергии. Поэтому среди всех возможных вариантов им нужно найти такое L, чтобы итоговый запас аккумулятора после исследований оказался максимально возможным. Если таких L несколько, для определённости берется минимальное из возможных.

Помогите учёным найти номер стартовой точки L.

Входные данные
В первой строке входных данных содержится целое число N (2 ≤ N ≤ 250.000) — количество точек на интересующем учёных участке поверхности Марса.

Во второй строке содержится целое число K (1 ≤ K < N) — длина отрезка, который должен пройти марсоход.

В следующих N строках вводятся целые числа H1, H2, ..., HN (1 ≤ Hi ≤ 109) — высоты точек.

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

Файл с решением задачи на C++:

Пожалуйста, авторизуйтесь для просмотра ссылки.

.
Сложность алгоритма - O(N).
Время решения: 14 минут.
Идея алгоритма:

Изменение заряда марсохода всегда будет равняться MasH[I+k] - MasH. Поэтому нам достаточно пробежаться в цикле по всем вершинам от 0 до N - K - 1 включительно (вопреки ошибкам выхода за границы памяти) и сравнить разность MasH[I+k] и MasH с уже существующим минимальным проигрышем в энергии.

 

[CoffeMan]

Молодец Ирвал, ты абсолютно точно умнее некоторых участников данной олимпиады. Накидайте парню лукосов.

потому что участники олимпиады пришли проебланить уроки и "что-то" написать со слов самого участника

 

[Irval]

Задача 5: Древнее имя
Катя очень любит историю, поэтому ей подарили книгу про древние индейские имена. В книге утверждается, что коэффициент древности имени равен количеству таких пар букв имени, что первая буква пары стоит в имени раньше второй, и при этом первая буква пары и в алфавите стоит раньше второй.

Катя так восхитилась данным способом, что сразу же захотела подсчитать древность своего любимого индейского имени.

Входные данные
В первой строке входных данных содержится целое число N (1 ≤ N ≤ 10^5) — длина любимого индейского имени Кати.

Во второй строке содержится последовательность из N строчных букв английского алфавита — любимое индейское имя Кати.

Выходные данные
Выведите единственное целое число — коэффициент древности имени.

Единственная задача, которая оказалась не совсем тривиальной.
Файл с решением задачи на C++:

Пожалуйста, авторизуйтесь для просмотра ссылки.

.
Сложность алгоритма - O(53N). В худшем случае - 5 * 10^6 операций, что должно заходить на C++.
Время решения: 15 минут.
Идея алгоритма:

Алгоритм основан на префиксных суммах и предподсчете элементов массива, если Вы не знаете этих тем - настоятельно советую ознакомиться перед решением задачи. Для каждой подстроки, включающей символы от 0 до i-го, я предлагаю создать массив предподсчета, где для каждого элемента от 0 до 25 включительно (именно столько букв в английском алфавите) будет храниться количество ('a' + i)-го символа в строке.
Далее, проходимся по каждому символу исходной строки. Приплюсовываем к итоговому количеству count количество символов после i-го в полной строке. А после, вычитаем из этого количество символов после i-го в строке длиной i. Это и можно считать реализацией наших префиксных сумм.

 

[alexandyr]

это типа kickstart'a от гугла?

 

[Irval]

Добавил разбор алгоритма решения к каждой задаче.