Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 156 157 158 159 160 161 162 >> Отображать по:
#1679
Министры его величества
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Его Величество Король Бубей Второй пожелал назначить новый кабинет министров (информация о том, что случилось со старым – строго засекречена). К составу кабинета министров есть следующие пожелания:

1) министров должно быть как можно меньше (так ими легче управлять, да и на зарплате можно сэкономить);

2) для каждой области (строительство, финансы и т.д.) должен быть хотя бы один министр, который в ней разбирается.

На рассмотрение Его Величества поступило \(N\) кандидатур. Определите, сколько и каких людей должны получить министерские посты, с учетом пожеланий.

Входные данные

сначала вводится число \(N\) (натуральное, не превышает 10) – количество кандидатов в списке, затем вводится число \(K\) (натуральное, не превышает 20 – общее количество областей, в которых министры должны разбираться). Затем идет \(N\) строк следующего формата: в начале строки вводится число \(P_i\) (натуральное, не превышает \(K\)) – количество областей, в которых разбирается \(i\)-й кандидат, потом вводятся номера этих областей (натуральные числа, не превышают \(K\)).

Выходные данные

сначала выведите количество министров, которое планируется назначить, исходя из требований задачи, затем перечислите номера подходящих кандидатов, в порядке возрастания. Если решений несколько, то выберите из них то, в котором участвуют кандидаты, идущие раньше по списку. Гарантируется, что решение существует (то есть можно получить такой набор кандидатов, что в каждой области будет разбираться хотя бы один из них)

Примеры
Входные данные
3 2
2 1 2
2 1 2
2 1 2
Выходные данные
1
1
Входные данные
4 3
1 1
1 2 
1 3
2 1 2
Выходные данные
2
3 4
#1680
Королевское путешествие
  

Его Величество Король Бубей Второй пожелал объехать свои владения. При этом к маршруту есть следующие пожелания:

1) маршрут должен занимать наименьшее возможное время (королевское время – вещь очень ценная и его надо беречь);

2) маршрут должен включать все населенные пункты ровно по одному разу (если король пропустит какой-то населенный пункт, то его жители будут возмущены королевским невниманием и перестанут платить налоги; если король посетит какой-то населенный пункт больше одного раза, то жители остальных населенных пунктов также возмутятся)

3) маршрут должен начинаться и заканчиваться в столице государства (объехав свои владения, король должен сразу приступить к делам). Столица входит в маршрут ровно 2 раза: как пункт отбытия и как пункт назначения, она не может являться промежуточным населенным пунктом маршрута.

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

Входные данные

сначала вводится число \(N\) (натуральное, не превышает 10) – количество населенных пунктов королевства. Затем следует \(N\) строк по \(N\) чисел в каждой – время пути между населенными пунктами (время – целое неотрицательное число, не превышает 500; если время = 0, то это означает, что пути между какими-то населенными пунктами нет). Населенный пункт №1 является столицей государства.

Выходные данные

выведите наименьшее суммарное время, которое Его Величество потратит на объезд своих владений, или число -1, если построить маршрут с заданными свойствами невозможно.

Примеры
Входные данные
1
0
Выходные данные
0
Входные данные
2
0 1
1 0
Выходные данные
2
Входные данные
2
0 85 
85 0
Выходные данные
170
#1681
Статуи на мосту
  

В столице королевства Бубея Второго построен новый мост, который решено украсить статуями работы лучших мастеров. Для украшения моста были выбраны N мастеров, каждый из которых создал по одной статуе. К сожалению, мастера сделали статуи разного веса, поэтому если эти произведения искусства распределить между левой и правой сторонами моста произвольным образом, то возникает риск, что одна из сторон «перетянет» и мост опрокинется. С другой стороны, проект уже утвержден Его Величеством и необходимо обязательно использовать все статуи. Определите оптимальное распределение статуй между левой и правой сторонами моста.

Входные данные

сначала вводится число \(N\) (натуральное, не превышает 12), затем вводятся \(N\) чисел (натуральные, не превышают 1000) – веса статуй.

Выходные данные

выведите единственное число – наименьшую возможную разницу в суммарном весе статуй на левой и правой сторонах моста. На каждой стороне может стоять любое количество статуй.

Примеры
Входные данные
3
1 2 3
Выходные данные
0
Входные данные
5
1 2 3 3 10
Выходные данные
1
#1682
Во дворце заговор
  
Темы: [Перебор]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Секретная Служба Его Величества Бубея Второго разоблачила заговор среди придворных. Теперь необходимо уволить всех явных заговорщиков и подозрительных придворных. Придворный считается «явным заговорщиком» - если существуют явные доказательства его причастности к заговору. Придворный считается «подозрительным», если он был назначен на свою должность кем-то из «явных заговорщиков» или других «подозрительных» придворных. Определите, сколько людей сохранит свои должности при дворе Его Величества.

Входные данные

сначала вводится число \(N\) (натуральное, не превышает 1000) – общее количество придворных. Затем вводится \(N\) чисел \(a_i\) (целые, неотрицательное, не превышают \(N\)) – номер придворного, благодаря которому придворный \(i\) получил свою должность. Если \(a_i\)=0, то это означает, что этот придворный назначен на свою должность самим Королем. Затем вводится число \(K\) (натуральное, не превышает \(N\)) – общее количество явных заговорщиков. Затем вводится \(K\) чисел (натуральные, не превышают \(N\)) – номера заговорщиков. Гарантируется, что данные корректны (например, что придворный не мог назначить на должность сам себя, или, что двое придворных не могли назначить друг друга одновременно).

Выходные данные

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

Примеры
Входные данные
3 0 0 1
1 3
Выходные данные
2
Входные данные
5 0 0 1 1 2
1 1
Выходные данные
2
Входные данные
4 0 1 2 3
1 2
Выходные данные
1
#1683
Распределение заказов
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В компанию по обслуживанию компьютеров поступило \(N\) заявок от клиентов. В компании есть \(S\) сотрудников разной квалификации. Руководитель компании знает, какие из заявок каждый сотрудник способен выполнить (возможно, каждый сотрудник может выполнить несколько заявок, также верно, что одну и ту же заявку способны выполнить несколько сотрудников). Каждый сотрудник в какой-то момент времени может выполнять не более одной заявки. Для выполнения каждой заявки достаточно ровно одного сотрудника.

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

Входные данные

Cначала вводятся числа \(N\) и \(S\) (натуральные, не превышают 100), затем вводится \(S\) строк по \(N\) чисел в каждой – сведения о квалификации сотрудников. Если в \(j\)-й позиции \(i\)-й строки находится 0, то \(i\)-й сотрудник не способен выполнить данную заявку, если 1 – то способен.

Выходные данные

Выведите единственное число – максимальное количество заявок, которое можно начать выполнять.

Примеры
Входные данные
2 2
1 1 
1 1
Выходные данные
2
Входные данные
3 3
1 0 0
0 1 0
0 0 1
Выходные данные
3
Страница: << 156 157 158 159 160 161 162 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест