Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Динамическое программирование на таблицах
---> 6 задач <---
Источники --> Личные олимпиады --> Открытая олимпиада школьников
    2002(9 задач)
    2003(10 задач)
    2004(13 задач)
    2005(12 задач)
    2006(12 задач)
    2007(11 задач)
    2008-2009(19 задач)
    2009-2010(23 задач)
    2010-2011(19 задач)
    2011-2012(8 задач)
    2012-2013(21 задач)
    2013-2014(8 задач)
    2014-2015(8 задач)
Страница: 1 2 >> Отображать по:
#1017
Еловая аллея
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Заданы координаты клеток на прямой, в которые можно посадить ели. Для каждого сорта ели определены тени, отбрасываемые на восток и на запад. Ели не могут расти в тени других елей. Требуется высадить как можно больше елей и для каждой занятой клетки указать, какой сорт ели будет туда посажен.

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

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

Координатная ось направлена вдоль аллеи с запада на восток.

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

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

Во входном файле записано сначала натуральное число M — количество сортов елей (1M100). Затем идет M пар чисел Wi, Ei, описывающих максимальную длину тени в западном и восточном направлении в течение дня для каждого сорта ели (числа Wi, Ei — целые, из диапазона от 0 до 30000). Далее идет натуральное число N — количество клумб, в которых можно сажать ели (1N100). Далее идет N чисел, задающих координаты клумб (координаты — целые числа, по модулю не превышающие 30000). Клумбы перечислены с запада на восток (в порядке возрастания их координат).

Примечание

Если на клумбе с координатой X мы посадили ель, максимальная тень которой в восточном направлении равна E, то все клумбы с координатами от X+1 до X+E–1 попадают в тень от этой ели, а клумба с координатами X+E — уже нет. Аналогично для тени в западном направлении.

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

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

Примеры
Входные данные
3
10 1
2 2
1 10
10
0
1
3
5
7
9
11
13
15
16
Выходные данные
8
9 2
8 2
7 2
6 2
5 2
4 2
3 2
1 2
#1020
Левый лабиринт
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

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

  • Участнику запрещено ходить по черным клеткам.
  • Придя в какую-то клетку, участник может пойти либо прямо, либо налево, либо направо (если в соответствующем направлении клетка не покрашена в черный цвет): ходить назад, а также ходить по диагонали запрещается.
  • За все время пути участнику разрешается повернуть направо (то есть пойти из текущей клетки направо относительно того, откуда он пришел в данную клетку) не более K раз.
  • В начальной клетке участник может встать лицом в ту сторону, в какую ему захочется. С какой стороны участник прибежит в конечную клетку также не важно.

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

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

Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

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

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

Примеры
Входные данные
1 3 4
0 0 2 0
0 1 1 0
0 0 3 0
Выходные данные
6
Входные данные
0 5 5
0 1 0 0 0
0 1 0 1 0
0 0 3 1 0
1 0 1 1 0
2 0 0 0 0
Выходные данные
12
#1028
Поиск прямоугольников
  

0

2

2

2

2

0

2

2

2

2

1

1

2

2

2

1

1

0

0

0

На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.

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

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

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

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

В первой строке входного файла записаны целые числа N, M, K (1N200, 1M200, 1K255). Далее следует N строк по M чисел в каждой — содержимое таблицы. Все числа в таблице целые, находятся в диапазоне от 0 до K включительно.

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

В выходной файл необходимо выдать K строк. Каждая строка должна описывать соответствующий ее номеру прямоугольник четырьмя числами R C H W (R и C должны описывать координаты левого нижнего угла прямоугольника, а H и W — координаты правого верхнего угла). Числа должны разделяться пробелом.

Оси координат устроены следующим образом: начало координат находится в нижнем левом углу поля, а оси координат направлены вдоль сторон поля (ось Ox — вдоль нижней стороны, а ось Oy — вдоль левой стороны). Клетки поля имеют размер 1x1. Таким образом, координаты левого нижнего угла поля — (0,0), правого верхнего — (M,N). Заметьте, что вы должны вывести координаты углов прямоугольников (как точек) в этой системе координат, а не координаты угловых клеток, покрытых прямоугольниками.

Примеры
Входные данные
4 5 2
0 2 2 2 2
0 2 2 2 2
1 1 2 2 2
1 1 0 0 0
Выходные данные
0 0 2 2
1 1 5 4
#1090
Тарифы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

В первой строке входного файла записаны два числа: количество VIP-абонентов компании N (1≤N≤100) и количество тарифных планов K (1≤K≤100).

Далее записано N целых чисел Ai — сумма, которую i-ый абонент готов тратить на связь в месяц (0≤Ai≤100000).

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

Выведите в выходной файл K натуральных чисел — размеры абонентской платы в тарифных планах в порядке возрастания. Размер абонентской платы не должен быть меньше 1 и не может превышать 109.

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

Доходы компании вычисляются как сумма абонентской платы, внесенной всеми абонентами компании.

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

1. Мы не будем обслуживать абонента, который готов платить 1. Абонента, который готов платить 4, мы подключим к первому тарифному плану. Абонентов, готовых платить 5 — ко второму, готовых платить 8 и 9 — к третьему, и готового платить 80 — к четвертому. Итого суммарный доход компании составит 4 + 5*4 + 8*2 + 80 = 120

2. Подключаем каждого абонента к своему тарифу, 4-й тариф не используем. Суммарный доход — 1+2+30=33

3. Подключаем всех, кроме первого и третьего абонентов, к единственному тарифу. Суммарный доход — 4*4 = 16

4. Поскольку мы не имеем права делать тариф с нулевой абонентской платой, то 1-го и 3-го абонентов обслуживать не будем.

Примеры
Входные данные
9 4
9 1 5 5 5 5 4 8 80
Выходные данные
4 5 8 80
Входные данные
3 4
1 2 30
Выходные данные
1 2 30 31
Входные данные
6 1
0 4 3 5 13 6
Выходные данные
4
Входные данные
3 2
0 1 0
Выходные данные
1 2
#1390
Симпатичные прямоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.

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

abc
acb

симпатичными являются все части, состоящие из одного квадратика (их 6), а также части

bc и a

cb и a

Напишите программу, которая по информации о шедевре Васи определит его стоимость.

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

В первой строке содержатся два числа N и M (1 ≤ N, M ≤ 100). В следующих N строках идут строки, состоящие из M маленьких латинских символов. Символ в i-й строке j-м столбце определяет цвет соответствующего квадратика картины.

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

Выведите стоимость шедевра — количество частей, симметричных относительно своего центра.

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

Этот пример разобран в условии

Симпатичными являются шесть частей 1x1, одна часть 1x2 и сама картина.

Частичные ограничения

Первая группа состоит из тестов, в которых N, M ≤ 15. Данная группа оценивается в 30 баллов.

Вторая группа состоит из тестов, в которых N, M ≤ 50. Данная группа оценивается в 30 баллов.

Примеры
Входные данные
2 3
abc
acb
Выходные данные
8
Входные данные
3 2
ab
cc
ba
Выходные данные
8
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест