---> 17 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

K участникам сборов для решения было предложено K задач. Участники решили разделить задачи между собой, решить каждому по одной задаче, а затем обменяться решениями (они не учли, что система ejudge способна отследить данный факт J). Известно ориентировочное время, за которое каждый из участников сборов может решить каждую из предложенных задач.

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

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

Во входном файле сначала записано число K (0 < K < 101) и далее K2 неотрицательных целых чисел, не превосходящие 20000, описывающих матрицу K x K, времен решения каждым из участников каждой из задач.

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

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

input.txt output.txt
2

1 2

2 4

4
#588
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача F ]
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Даны кубики с 6 буквами написанными на них и слово. Требуется составить слово из кубиков.

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

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

Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики.

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

В первой строке вводится число $N$ (1 <= $N$ <= 100) - количество кубиков в наборе у Пети. Во второй строке задано имя Петиной сестры - слово, состоящие только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.

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

В первой строке выведите "YES" если выложить имя Петиной сестры данными кубиками можно, "NO" в противном случае.

В случае положительного ответа, во второй строке выведите $M$ различных чисел из диапазона 1…$N$, где $M$ - количество букв в имени Петиной сестры. $i$-е число должно быть номером кубика, который следует положить на $i$-е место при составлении имени Петиной сестры. Кубики нумеруются с 1, в том порядке, в котором они заданы во входных данных. Если решений несколько, выведите любое. Разделяйте числа пробелами.

Примеры
Входные данные
2
AB
AAAAAB
AAAAAA
Выходные данные
YES
2 1 
Входные данные
3
ANNY
AAAAAA
NNNNNN
YYYYYY
Выходные данные
NO
ограничение по времени на тест
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
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Петя занимается разведением дракончиков. У него есть $M$ зеленых дракончиков и $K$ желтых. У Пети есть $N$ двухместных аквариумов для дракончиков и $M+K–2N$ одноместных.

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

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

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

Вводятся числа $M, K, N$ ($M ≥ 1, K ≥ 1, N ≥ 0, N ≤ M, N ≤ K, M + K ≤ 200$). Будем считать, что зеленые дракончики пронумерованы числами от $1$ до $M$, а желтые – числами от $M+1$ до $M+K$.

Далее идет число $T$ ($0 ≤ T ≤ MK$) – количество пар дракончиков, про которых известно, что они не переносят друг друга. Далее идет $T$ пар чисел, описывающих номера не переносящих друг друга дракончиков (первое число каждой пары описывает зеленого дракончика, второе – желтого). Далее идет число $Q$ ($0 ≤ Q ≤ M + K$)– количество дракончиков, не переносящих одиночества. Далее идет $Q$ чисел, задающих номера этих драконов.

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

В случае если разместить дракончиков по аквариумам требуемым образом нельзя, выведите единственное слово NO. В противном случае первая строка должна содержать YES. В следующие $N$ строк выведите $N$ пар чисел, задающих номера дракончиков, которых нужно поместить в двухместные аквариумы.

Примеры
Входные данные
2 1 1
1
1 3
1
1
Выходные данные
NO
Входные данные
2 2 1
1
1 3
1
2
Выходные данные
YES
2 4
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В секретном 240 отделе ИПФ РАН $N$ сотрудников и $N$ компьютеров. В отделе вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого сотрудника будут определены ровно $K$ компьютеров, к которым этот сотрудник будет иметь допуск (т.е. за которыми этот сотрудник будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно $K$ сотрудников.

Информация о том, какой сотрудник к какому компьютеру будет иметь допуск, будет известна лишь непосредственно перед вступлением новых требований в силу. Таким образом, чтобы не прерывать работу отдела, сотрудники должны будут быстро решить, кто за каким компьютером будет работать. Для этого им необходимо заранее написать программу, которая по любому распределению допусков сотрудников найдёт рассадку сотрудников по компьютерам, удовлетворяющую этим допускам.

Обратите внимание, что значение $K$ тоже будет известно лишь в последний момент. Из общих соображений секретности известно лишь, что $K$ будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений $K$.

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

В первой строке входного файла записаны натуральные числа $N$ и $K$ ($1\leq N \leq 500$). Далее следуют $KN$ строк, в каждой из которых записаны два натуральных числа — номер сотрудника и номер компьютера, к которому этот сотрудник имеет допуск.

Гарантируется, что каждый сотрудник имеет допуск ровно к $K$ компьютерам, что к каждому компьютеру ровно $K$ сотрудников имеют допуск, и что $K$ равно либо 1, либо 2, либо 4.

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

В выходной файл выведите $N$ строк, в каждой по два числа — номер сотрудника и номер компьютера, за которым он должен работать. Строки можно выводить в произвольном порядке.

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

Примеры
Входные данные
3 1
2 3
3 1
1 2

Выходные данные
3 1
1 2
2 3

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

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


Страница: 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест