Разбор [C] и [C-B`]
algo_easyВсем привет, это НЕофициальный разбор от @algo_easy. @algo_easy - всё в одном месте.
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников
[C] 1: Петя и кубики
Алгоритмы: реализация
Решение: Давайте для каждой цифры проверим, есть ли она в строке. Делается это с помощью двух for. Если цифры нету, то выводим ответ. Также есть другое решение: ответ это (45 - сумма цифр в s). Упражнение остается читателю.
[C] 2: Гламур
Алгоритмы: реализация
Решение: Давайте разберем 2 случая:
- N – четное. Тогда скажем, что каждая модель получит по 1 платью, следовательно нам хватит n платьев.
- N – нечетное. Тогда мы не можем купить купить по 1 платью каждой, так как мы можем покупать только четное число платьев. Значит нам нужно купить каждой как минимум по 2 платья. Значит ответ – 2n.
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников
[C] 3: Забыли пароль?
Алгоритмы: реализация, перебор
Решение: Давайте переберем все возможные пароли, их очевидно 10^4. Теперь для каждого пароля давайте поймем подходит он или нет и если подходит, то прибавим 1 к ответу. Тогда для каждой имеющейся цифры она должна быть равна ‘o’ или ‘?’. Если же цифры нет, то она должна быть равно ‘x’ или ‘?’.
[C] 4: Hogwarts Legacy 2
Алгоритмы: реализация, моделирование
Решение: Давайте будем поддерживать массив длины n + 1, где на каждом шаге будем поддерживать количество имеющейся у нас энергии. Изначально оно равно 0. Тогда при ‘cast’ будем вычитать 1 к прошлому результату. При ‘drink’ прибавлять b к прошлому значению. При ‘save’ будем просто брать прошлое значение. При ‘load’ будем идти назад до первого встреченного ‘save’ или начала игры и брать то значение. Так, в конце у нас будет правильный ответ.
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников
[C] 5: Кубы палиндромы
Алгоритмы: реализация, перебор
Решение: Заметим, что кубов чисел до 10^18 будет 10^6(корень третьей степени из 10^18), поэтому просто переберем все кубы чисел до n. Далее с помощью to_string можно легко перевести число в строку, также можно с помощью reverse перевернуть эту строку и получить вторую и сравнить первую строку со второй. Если они равны, то это число является кубом и палиндромом, а значит прибавим 1 к ответу.
[C] 6: Скрытый смысл
Алгоритмы: реализация, перебор
Решение: Давайте переберем 10! перестановок имеющихся у нас букв. Можно написать рекурсию, можно написать с помощью do while + next_permutation(), за подробностями в @algo_forum. Это будет не очень много(~10^6 перестановок). Тогда буква будет означать цифру, на номере которой она стоит. Тогда остается проверить, что в числах первые буквы не равны нулю и уравнение решено правильно. Это делается тривиально, так как мы знаем цифру для каждой буквы.
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников
[C-B'] 1: Операции над точкой
Алгоритмы: реализация
Решение: Заметим, что задача решается независимо для каждой координаты. Пусть у нас есть ненулевое количество ‘N’ и ‘S’(смотрим вторую координату). Тогда очевидно, что мы можем как-то расставить числа на этих позициях так, чтобы в сумме было ноль, то есть по этой координате мы вернемся в ноль. Если же ‘N’ и ‘S’ обеих нулевое количество, то мы по этой координате никуда не сдвинемся и так. Если же одной буквы ноль, а другой не ноль, то у нас будут только отрицательные/положительные слагаемые, а значит мы не сможем вернуться в ноль. Значит нам нужно посчитать количество ‘N’ и ‘S’ и в зависимости от этих трёх случаев проверить можем ли мы вернуться в ноль по второй координате. Аналогично проверяем ‘W’ и ‘E’ и выводим ответ.
[C-B'] 2: Долгое обсуждение
Алгоритмы: теория чисел, остатки
Решение: Предположим, что a mod k = x. Тогда b mod k = k – x, потому что a+b mod k = 0. Также c mod k = k – x (из a + с) и c mod k = k – (k – x) = x (из b + с). Тогда можно заметить, что x mod k = (k – x) mod k. Теперь также разберем 2 случая:
- K – нечетное. Из нашего предположения видно, что x может быть только 0, так как при других x у нас оно не выполнится, так как четность x и k-x разная. Следовательно ответ равен количеству чисел до n таких, что они делятся на k. Это считается формулой (n/k)^3 (округление вниз).
- K – четное. Заметим, что в этом случае подходят только x = 0 или x = k / 2. Тогда x должно делиться на k/2. Где x = 0 троек чисел (n / k) ^ 3 из пункта 1. Для x = k / 2: надо сначала проверить, что k / 2 <= n, в противном случае нету таких x. Дальше заметим, что x может быть вида k / 2, k / 2 + k, ...k / 2 + x * k. Таких x у нас (n - k / 2) / k + 1, плюс один, потому что считаем k / 2 тоже. Соответственно надо прибавить ((n - k / 2) / k + 1) ^ 3.
P.S: в решении все деления на какое-то число округляются вниз
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников
[C-B'] 3: Регулярка
Алгоритмы: реализация
Решение: Давайте для начала поймем можем ли мы получить строку длиной <= k и строку длиной >= k. Пусть n1 – количество букв, а n2 – количество ‘*’ и ‘?’. Тогда если мы удалим все буквы перед ‘*’ и ‘?’, то это будет строка минимальной длины и её длина будет равна n1 – n2, тогда n1-n2 должно быть <= k. Если у нас есть ‘*’, то длина нашей строки сверху не ограничена, так как мы можем поставить бесконечно много ‘a’ на месте ‘*’('a' - символ перед любой '*'). Если же ‘*’ нет, то мы не будем удалять буквы перед ‘?’ и получим строку длиной n1, значит n1 должно быть >= k, так как в противном случае мы получили строку максимальной длины, которая <k.
Теперь можно несложно восстановить строку, считаем, что изначально n1 символов - то есть только буквы. Если длина строки меньше, то на месте ‘*’ поставим столько ‘a’, сколько нужно, а на месте вопросов оставляем буквы. А если больше, то будем удалять символы перед ‘?’ и ‘*’ по порядку.
[C-B'] 4: Трафареты
Алгоритмы: реализация + идея
Решение: Заметим, что порядок выполнения операций 2 и 3 не важен, а также, что все операции 1 имеет смысл выполнять только до выполнения операций типов 2 и 3. Первый факт очевидный, так как у нас все строки и столбцы, которые мы перемещаем будут состоять только из ‘.’, а второй доказывается так: мы можем сделать все повороты до всех операций и потом так поменять операции на остальных позициях, что результат не поменяется(порисуйте картинки, более строгий пруф можно спросить в @algo_forum). Также заметим, что операцию первого типа нет смысла выполнять более 4 раз, потому что после 4 раз таблица переворачивается в саму себя.
Тогда проверим, что какой-то из 4 прокрутов A с какими-то операциями 2 и 3 = B с какими-то операциями 2 и 3. Перебираем кол-во переворотов на 90 градусов(их <=4 по выше сказанному). Для удобства давайте будем удалять первую строку из A и B (отдельно) пока можем, аналогично с первыми столбцами. Это интуитивно понятно, что мы хотим нашу картинку(в A и B) сдвинуть в какой-то из углов(например, в нашем решении влево вверх), чтобы проверить равенство. Тогда если трафареты равны, то такие A и B должны быть также равны.
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников
[C-B'] 5-Слишком много нот
Алгоритмы: реализация, конструктив
Решение: Давайте найдем первую такую позицию, что a[i] > a[i+1]. Тогда нам однозначно выгодно удалить элементы равные a[i], так как тогда на её позиции будет число меньше(a[i + 1]), то есть массив станет лексикографически меньше и минимальным. Если же такого элемента нет, то массив отсортирован, а значит нам имеет смысл удалить последний элемент, так как если мы удалим любой другой, то массив станет точно больше(или >=, так как элементы сдвигаются влево), а так станет точно меньше.
[C-B'] 6: Хорошие были времена...
Алгоритмы: конструктив
Решение: Давайте выпишем все наборы, из которых может получиться 10:
(2, 2, 2, 2, 2)
(2, 2, 2, 4)
(2, 4, 4)
(2, 2, 3, 3)
(4, 3, 3)
Теперь, можно подумать, что нам всегда выгодно покупать билеты только в каком-то порядке способов, поэтому можно просто перебрать порядок способов, в котором будем покупать билеты и взять максимум из этих способов. Почему? В таких задачах надо понимать на интуитивном уровне "жадность", она здесь очевидно существует, а значит есть какой-то оптимальный порядок действий. Этого уже хватает на OK, но если подумать чуть дальше, то можно заметить, что один из оптимальных порядков будет такой: (4, 3, 3), (2, 2, 3, 3), (2, 4, 4), (2, 2, 2, 4), (2, 2, 2, 2, 2).
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников