Продолжаю находить для вас переоценённые задачи и разбирать их. На этот раз задача из раздела "Рекурсия, перебор". Читаем условие, обращаем внимание на ограничения во входных данных.
Выглядит сложно. Сразу не очень понятно, как можно перебрать соединения. Например можно перебрать подмножество, затем перебрать все способы поделить его на две группы и запустить рекурсия для них, а потом все полученные варианты соединить последовательно (сложить) или параллельно (заиспользовать формулу из условия задачи). Идея не очень хорошая.
А можно попробовать двигаться в другую сторону. Поддерживать множество всех ёмкостей, которые мы уже умеем получать, и пытаться попарно их соединять друг с другом двумя способами (последовательно и параллельно), получая новые варианты. В этом случае важно, чтобы полученная комбинация не содержала один конденсатор два раза, поэтому вместе с ёмкостью схемы, которую мы уже умеем получать, надо хранить и множество конденсаторов, которые в ней использованы.
Так как при этом надо уметь находить пересечение и объединение множеств, удобно воспользоваться битовыми операциями (& и |), а множество хранить в целом числе, отмечая биты единичками, если соответствующий ему конденсатор использован.
Например, если в схеме использованы конденсаторы 1, 3 и 4, то ей будет соответствовать число 13 = 1101 (в двоичной системе счисления). Такое представление называется битовой маской.
Начнём писать и постепенно разбираться детальнее. Здесь я хочу использовать pair, поэтому снова сделаю подстановку:
Определим погрешность, с которой можно находить ответ, и считаем входные данные. Обращу внимание на то, как заполняется маска. Здесь тоже использую битовую операция - сдвиг влево - которая сдвигает число (в данном случае 1) на i битов влево. Арифметически это соответствует умножению на 2 в i степени, но в нашем случае важно лишь то, что это маска с одной единицей на i-ой позиции:
Итак, начало положено. Теперь в векторе уже лежат схемы (из одного конденсатора каждая), будем идти по этому вектору и, для начала, проверять, вдруг схема уже подходит, тогда выводим YES и завершаем программу:
Если схема не подходит, то надо попробовать соединить её со всеми предыдущими двумя способами. Для этого вторым указателем тоже пойдём по нашему вектору и если множество конденсаторов, в рассматриваемой паре схем не пересекается, то добавляем две новых схемы в конец вектора:
Пересечение двум множеств (битовых масок) нахожу с помощью операции &, потому что её результатом является число, в котором единицы равны только те биты, которые равны единице в обоих операндах (в наших терминах - присутствуют в обоих множествах). Поэтому, если результат этой операции равен 0, значит множества не пересекаются.
Аналогично, используется битовое ИЛИ для объединения множеств и результирующих схемах.
Если мы прошли по всему вектору (который по ходу работы программы будет дополняться новыми схемами) и не нашли решения, то выводим отрицательный ответ:
Замечу, что получившиеся схемы в векторе могут повторяться, это отрицательно сказывается на времени работы программы. Но с такими сильными ограничениями на входные данные, программа всё равно работает очень быстро.
Чтобы избежать повторения, можно было бы завести set, в который так же как и в вектор складывать пары, но перед этим делать проверку: если в нём уже есть такая пара, то не добавлять её ни в set, ни в вектор. Но в таком решении я бы обязательно обратил внимание, что складывать double в set - не очень хорошая идея (потому что из-за погрешности числа могут считаться разными) и порекомендовал использовать тип Rational, который мы написали ранее. Однако, на таких входных данных все три решения получают Accepted.
Предыдущий выпуск: Задача 533. Треугольники - 3
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.