Темы --> Информатика --> Алгоритмы --> Динамическое программирование
    Рекуррентные последовательности(10 задач)
    Динамическое программирование: один параметр(49 задач)
    Динамическое программирование: два параметра(183 задач)
    Динамическое программирование в играх(9 задач)
    Динамическое программирование на графах(25 задач)
    Динамическое программирование по профилю(20 задач)
    Динамика по подмножествам(13 задач)
---> 18 задач <---
Источники --> Личные олимпиады --> Открытая олимпиада школьников
    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 3 4 >> Отображать по:
#1032
Узор
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Существует несколько форм паркетных плиток:

Квадратики одной паркетной плитки могут быть окрашены по-разному. Может существовать несколько типов плиток одинаковой формы, но окрашенных по-разному. Плитки разных типов могут иметь разную стоимость. Количество плиток каждого типа не ограничено. Плитки разрешается как угодно поворачивать (на углы, кратные 90 градусам). Не разрешается разламывать плитки, а также класть их лицевой стороной вниз.

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

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

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

В первой строке входного файла записаны три числа: N, M (размеры комнаты) и K (количество доступных видов плитки). 1≤N≤8, 1≤M≤8, 1≤K≤10. Далее идет описание желаемой раскраски пола. Описание представляет собой N строчек по M чисел в каждой, где 0 обозначает белый цвет, 1 — черный, 2 — то, что квадрат уже выложен плиткой. В последних K строчках находятся описания доступных типов плитки в следующем формате:

<форма> <стоимость> <окраска>

<Форма> — это число от 1 до 4, описывающее форму плитки (см. рисунок выше)

<Стоимость> — это натуральное число, не превосходящее 10000, задающее стоимость одной плитки такого типа

<Окраска> — это от одного до трех чисел 0 или 1. Количество чисел совпадает с количеством квадратиков, из которых состоит плитка. Числа задают цвета квадратиков плитки в том порядке, в каком квадратики пронумерованы на рисунке.

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

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

Примеры
Входные данные
4 3 3
2 2 2
2 0 0
2 1 2
2 2 2
2 10 0 0
1 5 1
4 6 0 0 1
Выходные данные
15
#1044
Лотерея
  

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо \(M\)-значного числа в системе счисления с основанием \(K\) (то есть, по сути, каждый участник называет \(M\) цифр, каждая из которых лежит в диапазоне от 0 до \(K-1\)). Ведущие нули в числах допускаются.

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также \(M\)-значное число в \(K\)-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере \(A_1\) рублей. Те, у кого совпали первые две цифры числа — получают \(A_2\) рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают \(A_3\) рублей. И так далее. Угадавшие все число полностью получают \(A_m\) рублей. При этом если игрок угадал \(t\) первых цифр, то он получает \(A_t\) рублей, но не получает призы за угадывание \(t-1\), \(t-2\) и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

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

В первой строке задаются числа \(N\) (количество телезрителей, сделавших свои ставки, \(1\le N\le 100000\)), \(M\) (длина чисел \(1\le M\le 10\)) \(K\) (основание системы счисления \(2\le K\le 10\)). В следующей строке записаны \(M\) чисел \(A_1\), \(A_2\), ..., \(A_M\), задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (\(1\le A_1\le A_2\le ... \le A_M\le 100000\)). В каждой из следующих \(N\) строк записано по одному \(M\)-значному \(K\)-ичному числу. Числа идут в порядке неубывания.

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

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

Примеры
Входные данные
10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111
Выходные данные
011
6
Входные данные
1 1 10
100
0
Выходные данные
1
0
#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
#1093
Иностранные языки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Папа Васи очень заботится об образовании сына. Особое значение он придает иностранным языкам. Недавно они приступили к изучению английского. Чтобы ускорить процесс, папа разговаривает с Васей исключительно на нем. Разумеется, это создает некоторые трудности при общении. Каждый раз, когда Вася что-нибудь скажет, папе приходится долго гадать, что именно он имел в виду.

Папа знает словарный запас сына. Считается, что Вася мог иметь в виду словарное слово P, если оно входит как подпоследовательность в слово T (то, что он сказал). Другими словами, если существует такая возрастающая последовательность индексов i1 < i2 < ... < im (где m — длина P), что P[j] = T[ij] для всех j = 1..m.

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

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

В первой строке входного файла содержится единственное число K.

В следующих K строках идут слова из словаря, по одному на каждой строке. На последней (K + 2)-й строке входного файла содержится слово, сказанное Васей, длиной не более 100 000. Все слова в словаре непустые.

Все слова состоят из строчных латинских букв. Гарантируется, что суммарная длина слов из словаря не превышает 1 000 000 символов.

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

В выходной файл выведите K строк. В i-й строке должно быть записано ‘YES’, если Вася мог иметь в виду слово номер i из словаря, и ‘NO’ в противном случае.

Примеры
Входные данные
4
hi
hello
bye
oh
ahhinellation
Выходные данные
YES
YES
NO
NO
Входные данные
5
want
drink
ink
ant
in
iwanttosleep
Выходные данные
YES
NO
NO
YES
YES
#1106
SMS
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

SMS-сообщения на мобильном телефоне марки MOBILO набираются только заглавными английскими буквами. Для набора буквы нужно нажать кнопку, на которой эта буква написана, при этом если эта буква написана первой, то кнопку нужно нажать один раз, если второй – то два раза и т.д. Устройство клавиатуры телефона приведено на рисунке.

Таким образом, чтобы набрать слово SMS, нужно нажать следующие кнопки:

<PQRS> <PQRS> <PQRS> <PQRS> <MNO> <PQRS> <PQRS> <PQRS> <PQRS>

Для набора двух букв, которые находятся на одной кнопке, при наборе нужно сделать паузу между их вводом. Например, чтобы набрать BA, нужно два раза нажать кнопку <ABC>, затем сделать паузу и затем нажать кнопку <ABC> еще раз.

Если на кнопке написано три буквы, то как только эта кнопка нажата три раза подряд, последняя из написанных на ней букв сразу же добавляется в сообщение, а дальнейшие нажатия на эту кнопку воспринимаются как ввод следующей буквы. То же самое, если на кнопке написано 4 буквы. Таким образом, 4-х кратное нажатие на кнопку <ABC>, затем пауза, и затем нажатие на эту кнопку еще раз приведет к вводу текста CAA.

К сожалению, в силу произошедшего глюка, телефон стал иногда игнорировать паузы при вводе, а, иногда, наоборот, вести себя так, как будто была пауза тогда, когда паузы не было. Например, при вводе слова MOSCOW могло в итоге (как один из вариантов) получиться слово OMSCMNW.

Вы получили SMS-сообщение, набранное на этом телефоне. Известно, что изначально оно состояло из N символов. Напишите программу, которая определит количество вариантов исходных сообщений, которые при вводе могли превратиться в то, что вы получили (если вариантов окажется 0, то это будет означать, что у телефона сломалось что-то еще).

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

Сначала записана длина исходного сообщения N (1≤N≤80). Вторая строка содержит полученное SMS-сообщение – последовательность не более чем из 80 заглавных латинских букв.

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

Выведите одно число – количество вариантов исходного сообщения.

Примеры
Входные данные
4
MAMA
Выходные данные
1
Входные данные
2
WWW
Выходные данные
2
Входные данные
10
MAMA
Выходные данные
0
Страница: << 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест