Темы --> Информатика --> Алгоритмы --> Жадный алгоритм
---> 70 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Региональное отделение одного крупного банка заказало два несгораемых шкафа для хранения личных дел своих клиентов. Каждый шкаф имеет несколько ящиков различной высоты, при просмотре снизу вверх ящики в первом шкафу имеют высоту a1, a2, ..., am, а ящики во втором шкафу высоту b1, b2, ..., bn.

Шкафы были установлены в узкой нише в стене лицевой стороной друг к другу, поэтому оказалось, что выдвинуть одновременно два ящика, находящиеся напротив друг друга, невозможно. Сотрудники банка постоянно обращаются к личным делам клиентов, поэтому им удобнее держать ящики открытыми в течение рабочего дня. Поскольку пока клиентов у банка немного, использовать все ящики не обязательно. Решено было использовать такое множество ящиков, чтобы их все можно было выдвинуть одновременно и они не мешали друг другу. Чтобы максимально систематизировать работу, необходимо использовать как можно больше ящиков.

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

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

Первая строка входного файла содержит два целых числа: m и n — количество ящиков в первом и во втором шкафу, соответственно (1 ≤ m, n ≤ 100000). Вторая строка содержит m целых чисел: a1, a2, ..., am высоты ящиков в первом шкафу. Третья строка содержит n целых чисел: b1, b2, ..., bn — высоты ящиков во втором шкафу. Высоты ящиков положительные и не превышают 109.

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

На первой строке входного файла выведите два числа k и l количество ящиков, которые следует использовать в первом и втором шкафу, соответственно. Сумму k + l вам следует максимизировать. На второй строке выведите k целых чисел номера ящиков в первом шкафу, которые следует использовать. На третьей строке выведите l целых чисел номера ящиков во втором шкафу, которые следует использовать. Если оптимальных решений несколько, выведите любое.

Примеры
Входные данные
5 5
1 2 3 4 5
6 4 3 2 1
Выходные данные
4 3
1 2 3 4 
3 4 5 
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

В новом учебном году на занятия в компьютерные классы Дворца Творчества Юных пришли учащиеся, которые были разбиты на N групп. В i-й группе оказалось Xi человек. Тут же перед директором встала серьезная проблема: как распределить группы по аудиториям. Во дворце имеется M N аудиторий, в j-й аудитории имеется Yj компьютеров. Для занятий необходимо, чтобы у каждого учащегося был компьютер и еще один компьютер был у преподавателя. Переносить компьютеры из одной аудитории в другую запрещается. Помогите директору!

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

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

На первой строке входного файла расположены числа N и M (1 N M 1000). На второй строке расположено N чисел — X1 , …, XN(1 Xi 1000 для всех 1 i N). На третьей строке расположено M чисел   Y1, ..., YM (1 ≤ Yi 1000 для всех 1 i ≤ M).

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

Выведите на первой строке число P - количество групп, которые удастся распределить по аудиториям. На второй строке выведите распределение групп по аудиториям – N чисел, i-е число должно соответствовать номеру аудитории, в которой должна заниматься i-я группа. (Нумерация как групп, так и аудиторий, начинается с 1). Если i-я группа осталась без аудитории, i-е число должно быть равно 0. Если допустимых распределений несколько, выведите любое из них.

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

Дано верное равенство вида a1+a2+…+aN=b1+b2+…bM, где a1,a2,…,aN,,b1,b2,…,bM – некоторые действительные (не обязательно целые) числа. Требуется «округлить» это равенство, т.е. получить новое верное равенство c1+c2+…+cN=d1+d2+…+dM, где c1,c2,…,cN,d1,d2,…,dM — целые числа, и при этом c1 получено округлением числа a1 до целого вверх или вниз (так, например, число 1.7 разрешается округлить как до 1, так и до 2), c2 получено округлением a2, …, cN – округлением aN, d1округлением b1, …, dM – округлением bM. Если какое-то из чисел в исходном равенстве было целым, оно должно остаться без изменений.

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

Во входном файле задано сначала число N, затем N чисел a1, a2, …, aN, затем число M, затем числа b1, b2, …, bM. Каждое число задается на отдельной строке. M и N – натуральные числа, не превышающие 1000. Остальные числа — вещественные, каждое из них по модулю не превышает 1000 и содержит не более 6 цифр после десятичной точки. При этом a1+a2+…+aN=b1+b2+…bM.

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

Если «округлить» равенство можно, то в выходной файл выведите сначала числа c1,c2,…,cN, а затем числа d1,d2,…,dM. Все числа должны быть целыми и выведены без десятичной точки. Числа должны разделяться пробелами или переводами строки. Если решений несколько, выведите любое из них.

Если округлить исходное равенство до верного целочисленного равенства невозможно, выведите одно число 0.

Комментарии к примерам тестов

1. Обратите внимание, что число –3 может округляться только в –3, в то время как 0.15 можно округлить как до 0, так и до 1, 2.7 – до 2 или до 3, –0.15 – до –1 или до 0. Приведенное решение не является единственным: так же верным является, например, такое округление: 1+(–3)+2=0

2. Приведенное решение 1+3=1+2+1 не является единственным. Верными ответами также являются 2+2=1+2+1 и 2+3=1+2+2.

3. Здесь верными являются как ответ 1=1, так и 0=0.

Примеры
Входные данные
3
0.15
-3.000
2.7
1
-0.15
Выходные данные
1
-3
2
0
Входные данные
2
1.7
2.5
3
1
2.000
1.20
Выходные данные
2
2
1
2
1
Входные данные
1
0.5
1
0.5
Выходные данные
0
0
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В стране Флатландия решили построить легкоатлетический манеж с M одинаковыми прямолинейными беговыми дорожками. Они будут покрыты полосами из синтетического материала пружинкин. На складе имеются N полос пружинкина, длины которых равны 1, 2, …, N метров соответственно (i-я полоса имеет длину i метров).

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

Требуется написать программу, которая определяет, можно ли покрыть всем имеющимся материалом M дорожек, и если это возможно, то распределяет полосы пружинкина по дорожкам.

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

Во входном файле содержатся два целых числа, разделенных пробелом: M — количество дорожек и N — количество полос пружинкина (1 ≤ M ≤ 1000, 1 ≤ N ≤ 30000).

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

В случае, если распределить имеющиеся полосы пружинкина на M дорожек одинаковой длины невозможно, то в выходной файл выведите слово «NO».

В противном случае, в первую строку выведите слово «YES». В последующих M строках дайте описание использованных полос для каждой дорожки в следующем формате: сначала целое число t — количество полос на дорожке, затем t целых чисел — длины полос, которые составят эту дорожку. Если решений несколько, можно вывести любое из них.

Примеры входных и выходных данных

Ввод

Вывод

2 4

YES

2 1 4

2 3 2

3 4

NO

ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Около прямолинейного забора, состоящего из N одинаковых бетонных плит, проводится конкурс граффити, в котором участвуют M граффити-художников. Художники должны разрисовать все плиты своими произведениями за наименьшее возможное время.

Плиты пронумерованы числами от 1 до N, граффити-художники имеют номера от 1 до M. Первоначально i-й граффити-художник находится около плиты с заданным номером pi. Каждому художнику требуется b минут на разрисовывание любой плиты. Каждую плиту должен разрисовать ровно один граффити-художник.

В начале работы, а также после разрисовывания любой плиты граффити-художник может перейти к любой неразрисованной плите. Время перемещения граффити-художника от любой плиты к соседней с ней одинаково и равно a минут. Таким образом, чтобы перейти от плиты с номером i к плите с номером j художнику требуется a×|ij| минут.

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

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

В первой строке входного файла указаны числа N — количество плит в заборе и M — количество граффити-художников (1 ≤ N, M ≤ 100000). Во второй строке заданы два целых числа: a — количество минут, которое требуется для перехода от любой плиты к соседней, и b — количество минут, которое требуется граффити-художнику на разрисовывание одной плиты (1 ≤ a, b ≤ 106). В третьей строке заданы M чисел p1, p2, …, pM — начальные положения граффити-художников (1 ≤ piN).

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

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

В последующих M строках выведите описание действий художников. В i-й из этих строк должно содержаться описание действий i-го художника: количество плит, которые должен разрисовать этот художник, и номера этих плит в очередности их разрисовывания. Если оптимальных решений несколько, можно вывести любое из них.

Примечание

Решения, корректно работающие при  2, будут оцениваться из 40 баллов.

Примеры
Входные данные
10 2
19 56
9 2
Выходные данные
375
5 10 9 8 7 6 
5 1 2 3 4 5 

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