Алгоритмы теории множеств нередко применяются в программировании. В этой статье я хочу поговорить о генерации подмножеств множества. Множество — это набор элементов. Все элементы множества различны, то есть один элемент не может встретиться в множестве дважды. Программно реализовать множество можно разными способами: в виде класса, в виде массива с функциями для операций над ним и т.д. В языке Pascal имеется готовая реализация и синтаксис для работы со множествами.

Генерация подмножеств множества может пригодиться, допустим, в логике игры, когда из набора персонажей необходимо выбрать случайную их группу. Допустим, имеется множество M = {1, 2, 3}. Все подмножества множества M (их совокупность называют булеаном) следующие:

{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}

И снова всем привет! После вводной статьи самое время рассмотреть какую-нибудь задачку. Для первого раза возьмем простенькую, чтобы, так сказать, войти в курс дела.

Итак, задача о ящике. Условие задачи взято из системы Cats сайта ДВГУ. Оно на английском языке, я кратко опишу суть. Имеется шесть досок определенного размера (ширина и высота). Необходимо определить, можно ли из этих досок собрать ящик. Входной файл box.in содержит шесть строк, каждая описывает размер доски и состоит из двух чисел w и h — ширины и высоты. Выходной файл box.out должен содержать слово POSSIBLE, если возможно из данных шести досок собрать ящик, либо IMPOSSIBLE, если это невозможно. Ограничение по времени выполнения: 2 секунды, по памяти: 64 Mb. 1 ≤ w, h ≤ 10000.

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

Захотелось мне однажды увидеть единую и наглядную картину об электропитании серверов на работе, а также получать оперативные уведомления в случае его перебоев. В силу своей симпатии к системам на базе Linux решил двигаться в этом направлении. Дома я уже имел удачный опыт использования Apcupsd — демона для контроля ИБП фирмы APC, но здесь меня ждала несколько иная задача.

Дело в том, что данный демон не предусматривает работу с несколькими ИБП, а на работе у меня их три, и не хотелось каждый мониторить разным сервером. Решил поближе познакомиться с устройством этого демона.

ACM/ICPC (или просто ICPC) — крупнейшая студенческая командная олимпиада по программированию. Это мероприятие приравнивается к чемпионату мира по программированию. Данная статья открывает новую одноименную категорию на сайте, где мы будем разбирать интересные олимпиадные задачи.

Начну с небольшого экскурса в историю и правила проведения чемпионата. Четвертьфинальные и полуфинальные этапы чемпионата проходят независимо в своих регионах, победители которых проходят в следующий этап. Лучшие команды из каждого региона по итогам полуфинала собираются вместе в одном из городов мира и выясняют отношения в финале. Чемпионат командный, в каждой команде три участника. В распоряжении команды один ПК, некоторое количество времени (обычно 5 часов) и ряд поставленных задач (как правило, 5-10 задач). Каждая задача имеет условие, формат входных и выходных данных, ограничение по времени и по памяти. Решением задачи является программа, написанная на одном из доступных правилами языков программирования (обычно пишут на C). Программы-решения проверяются в автоматическом режиме. Система автоматической проверки выполняет несколько тестов, подавая проверяемой программе входные данные и анализируя выходные согласно условию задачи. Если программа на выходе дает неправильный ответ, превышает лимит допустимой оперативной памяти, выполняется дольше положенного времени (не компилируется, выпадает в runtime error, ну и так далее), то тест не пройден. Задача считается решенной, если программа удачно проходит все тесты, предложенные системой. Вариантов “почти решенная”, “наполовину решенная”, как вы понимаете, нет. При подсчете баллов учитывается количество решенных задач, время и количество попыток, затраченных на их решение.