---> 21 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 5 >> Отображать по:
Максимальное время работы на одном тесте: 2 секунды

Рассмотрим таблицу размера MxN, в клетках которой стоят целые неотрицательные числа. Скажем, что таблица является симпатичной, если для всех i сумма чисел ее i-ой строки не превышает Ri, и для всех j сумма чисел ее j-го столбца не превышает Cj.

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

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

Первая строка входных данных содержит числа M и N (1 <= M, N <= 20). Следующая строка содержит M целых неотрицательных чисел - R1, R2, ..., RM. Далее идет срока, содержащая N целых неотрицательных чисел C1, C2, ..., CN. Все вводимые ограничения не превышают 106. Следующие M строк содержит по N целых чисел, которые задают Z. Если на некотором месте в таблице Z отсутствует число, то на этом месте во входных данных стоит  -1.

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

Выведите найденную таблицу – M строк по N чисел. Если решения не существует, выведите единственное число -1.

Примеры
Входные данные
2 2
1 10
1 10
-1 -1
-1 1
Выходные данные
0 1 
1 1 
ограничение по времени на тест
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
#395
  
Темы: [Потоки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входного файла записано число досок N (0 <= N <= 1000). Далее для каждой доски записаны координаты кочек - концов доски (-231 <= Xi,Yi <= 231). Затем записаны координаты начальной и конечной точек (точки различны и доски, их соединяющей нет). Все числа во входном файле целые.

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

Вывести максимально количество коров, которых можно переправить

Примеры
Входные данные
8
0 0 1 0     
1 0 2 1    
1 0 2 -1
2 1 3 0     
2 -1 3 0  
1 0 4 0
3 0 4 0     
0 0 3 0    
0 0 
4 0
Выходные данные
2
#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 2 3 4 5 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест