Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Friendship Editing#90288

У Фермера Джона есть \(N\) коров, помеченных числами от \(1\) до \(N\) (\(2\le N\le 16\)). Отношение дружбы между этими коровами может быть смоделировано ненаправленным графом с \(M\) (\(0\le M\le N(N-1)/2\)) ребрами. Две коровы являются друзьями, если и только если между ними есть ребро в этом графе.

За одну операцию Вы можете добавить или удалить одно ребро в этом графе. Посчитайте минимальное количество операций, которое требуется выполнить, чтобы обеспечить следующее свойство в этом графе: Если коровы \(a\) и \(b\) - друзья, тогда для любой другой коровы \(c\) по крайней мере одна из коров \(a\) и \(b\) является другом коровы \(c\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\) и \(M\).

Каждая из следующих \(M\) строк содержит пару чисел \(a\) и \(b\) (\(1\le a<b\le N\)). Никакая пара друзей не повторится.

ФОРМАТ ВЫВОДА (на экран / stdout):

Количество ребер, которые требуется удалить или добавить.

—Войти и решать

Cow Decathlon#89920

Problem 2: Cow Decathlon [Lewin Gan]
N коров Фермера Джона (1 <= N <= 20), последовательно пронумерованных от 1 до 20 готовятся к десятиборью, в котором имеется N различных событий (из чего следует, что его правильнее было называть N-борьем, в отличие десятиборья, в котором традиционно ровно 10 событий).
Корова I имеет уровень мастерства S_ij (1 <= s_ij <= 1000), когда соревнуется в событии j. Каждая корова должна соревноваться в одном и только одном событии и каждом событии должна участвовать некоторая корова.
Общий счёт для всех коров - это сумма их уровней мастерства для тех соревнований, в которых они соревнуются. Однако жюри может также добавить бонусные баллы, если оно особенно впечатлено.
Всего имеется B бонусов (1<=B<=20), которые может дать жюри. Бонус I описывается 3 числами: - если коровы получат не менее чем P_i баллов(1 <= P_i <= 40,000) за первые K_i событий (включая другие бонусы, полученные на этих событиях), то они получат дополнительные A_i баллов (1 <= A_i <= 1000).
Например, рассмотрим N=3 коров со следующими уровнями мастерства:
E V E N T | 1 | 2 | 3 --+---+---+-- C 1 | 5 | 1 | 7 --+---+---+-- O 2 | 2 | 2 | 4 --+---+---+-- W 3 | 4 | 2 | 1
Например, корова 1 заработает 7 баллов команде, если она поучаствует в событии 3.
Предположим, что судьи дадут один бонус (B=1), такой что если коровы заработают не менее 7 баллов в первых двух событиях, то они получат дополнительные 6 баллов. Следовательно, оптимально будет назначить корову 1 событию 1, корову 2 событию 3 и корову 3 событию 2. За первые два события корова 1 получит 5 баллов и корова 3 получит 2 балла, что в сумме даст 7 и удовлетворяет бонусу 1. Поэтому, общее количество заработанных баллов будет 5+2+4+6=17.
Помогите распределиться коровам по событиям так, чтобы максимизировать их общий счёт.
PROBLEM NAME: dec
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа: N, B
* Строки 2..B+1: Строка i+1 содержит информацию о бонусе i задаваемом тремя разделёнными пробелами целыми числами: K_i, P_i, A_i.
* Строки B+2..B+N+1: Строки B+1+j содержат информацию о том, как корова i выполняет каждое из событий, с помощью N разделённых пробелами целых чисел: s_j1...s_jN.

Формат выходных данных
* Строка 1: Максимальное количество баллов, которые коровы могут получить, включая бонусы.

Примечание
Корова 1 выполнит событие 1, корова 3 выполнит событие 2, и корова 2 выполнит событие 3.

Динамика по подмножествам

—Войти и решать

Cows in a Skyscraper#89836

Коровы любят соревноваться в беге по лестницам небоскребов. А вниз потом едут на лифте.
Лифт имеет максимальную вместимость W (1 <= W <= 100,000,000) фунтов, а корова номер i весит C_i (1 <= C_i <= W) фунтов.
Помогите Бесси определить минимальное количество спусков лифта, чтобы переместить вниз все N (1 <= N <= 18) коров.
Сумма весов коров в каждом спуске не должна превышать W.
PROBLEM NAME: skyscraper
Формат входных данных
* Строка 1: N W разделенные одним пробелом
* Строки 2..1+N: Строка i+1 содержит целое число C_i, вес коровы i.
Формат выходных данных
* Строка 1: Минимальное целое, R, указывающее количество требуемых спусков.
* Строки 2..1+R: Каждая строка описывает множество коров, которые были в лифте во время каждого из R спусков. Каждая строка начинается с количества коров в текущем спуске, а затем номера коров через пробел.
Примечание
Мы можем поместить в лифт корову 3 и любую из оставшихся коров. Но все другие коровы не помещаются даже по две. В решении представленном выше, в первом спуске участвуют коровы 1 и 3, Во втором - корова 2, в третьем - корова 4. Существует несколько правильных решений для данного ввода.

битмаски Динамика по подмножествам Задача о рюкзаке

—Войти и решать

Театр#55412

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

Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.

Театральная сцена представляет собой прямоугольник W на L метров, внутри которого расположено N ламп подсветки.

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

Олег может перемещаться по сцене с максимальной скоростью V₁ метров в секунду, а Сергей − V₂ метров в секунду. Мастера могут находиться на сцене только в перерывах между действиями. Во время действия они могут переместиться в любую точку в пределах той части кулис, в которой они оказались перед началом действия.

Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий M и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей − в правой. Изначально включены лампы, необходимые для первого действия.

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

Входные данные
На первой строке входного файла находится пять чисел − W,L,V₁,V₂ и N (1≤W,L≤50, 1≤V₁,V₂≤20, 1 ≤ N ≤ 15)− размеры сцены, максимальные скорости мастеров и число ламп подсветки соответственно.

Далее идут N строк с координатами ламп подсветки в метрах x_i,y_i (0<x_i<L, 0<y_i<W).

Следующая строка содержит число M(1≤M≤10000) − число действий в спектакле. Далее идут M строк, каждая из которых содержит число ламп подсветки, которые должны быть включены в соответствующем действии, и номера ламп подсветки. Все числа во входном файле целые.

Выходные данные
В выходной файл выведите единственное число − минимальное суммарное время перерывов между действиями в секундах с точностью 10^-5.

Динамика по подмножествам

✓ 1✗ 0—Войти и решать