Каталог по темам

Задачи

Страница: << 19 20 21 22 23 24 25 >> [Всего задач: 277]

Задача 98690

[Праздники]

Тема:

[

Прочие задачи на аккуратную реализацию

]

Сложность: 3
Классы: 8,9,10,11

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

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

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

Формат входных данных

Во входном файле a.in записано единственное число K (1 £ K £ 50).

Формат выходных данных

В выходной файл a.out требуется записать единственное число - наибольшее количество нерабочих дней, идущих подряд.

Примеры

a.in	a.out
2	4
10	16

Прислать комментарий

Решение

Задача 98691

[Раскраска плиток]

Тема:

[

Прочие задачи на аккуратную реализацию

]

Сложность: 3
Классы: 8,9,10,11

Максимальное время работы на одном тесте: 1 секунда

После того, как к удивлению тетушки Полли, ее забор был покрашен, она поручила Тому Сойеру обновить краску на плитках, которыми был вымощен их квадратный двор. Двор был покрыт N´ N одинаковыми квадратными плитками, каждая из которых когда-то давно была покрашена в один из K цветов (K < N). Краска на плитках потускнела и Тому Сойеру поручили их покрасить, на этот раз в один любой цвет (из тех же К цветов). Покрасить нужно все плитки, в том числе и те, которые уже были покрашены в этот цвет раньше.

Окунув кисть в ведро с краской один раз, можно перекрасить один горизонтальный или вертикальный ряд плиток. Чтобы разнообразить свою работу, Том придумал, что ряд плиток можно красить только цветом, которым на данный момент уже покрашены (старой или новой краской) по крайней мере две плитки выбранного ряда (вертикального или горизонтального). За один раз Том собирается красить допустимым цветом весь ряд целиком, независимо от того, были ли уже перекрашены какие-либо его плитки ранее. Помогите Тому определить, какое минимальное число раз ему придется обмакнуть кисть, чтобы перекрасить все плитки, следуя придуманным правилам, и в какой цвет окажутся окрашены все плитки.

Формат входных данных

В первой строке входного файла b.in записаны через пробел два числа: N - количество плиток в одном ряду (1 < N ≤ 200) и K (1 ≤ K < N). В каждой из следующих N строк записаны N натуральных чисел, обозначающих номера цветов красок, в которые когда-то были выкрашены соответствующие плитки данного горизонтального ряда. Номера цветов - натуральные числа в диапазоне от 1 до K.

Формат выходных данных

В выходной файл b.out выведите два числа: L - какое минимальное число раз придется окунать кисть в ведро с краской, и номер краски С, в которую в результате окажутся перекрашены все плитки двора. Если таких красок может быть несколько, то выведите номер любой из них.

Если перекрасить все плитки, следуя придуманным Томом правилам, нельзя, выведите два раза число 0.

Примеры

b.in	b.out
3 2 1 2 1 2 1 1 1 2 2	4 1
2 1 1 1 1 1	2 1

Прислать комментарий

Решение

Задача 98692

[Маскарад]

Тема:

[

Динамическое программирование (прочее)

]

Сложность: 3
Классы: 8,9,10,11

Максимальное время работы на одном тесте: 1 секунда

Максимальный объем используемой памяти: 64 мегабайта

По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит: "Мы с радостью продадим Вам метр ткани за P_i бурлей, однако если Вы купите не менее R_i метров, то получите прекрасную скидку - каждый купленный метр обойдется Вам всего в Q_i бурлей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:

1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;

2) магазин номер i готов продать ему не более F_i метров ткани.

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

Формат входных данных

В первой строке входного файла c.in записаны два целых числа N и L (1 £ N £ 100, 0 £ L £ 100). В каждой из последующих N строк находится описание магазина номер i - 4 целых числа P_i, R_i, Q_i, F_i (1 £ Q_i £ P_i £ 1000, 1 £ R_i £ 100, 0 £ F_i £ 100).

Формат выходных данных

Первая строка выходного файла c.out должна содержать единственное число - минимальное необходимое количество бурлей.

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

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

Примеры

c.in	c.out
2 14 7 9 6 10 7 8 6 10	88 10 4
1 20 1 1 1 1	-1

Прислать комментарий

Решение

Задача 98719

[Подпалиндром]

Тема:

[

Динамическое программирование: классические задачи

]

Сложность: 3

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.
Формат входных данных
Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.
Формат выходных данных
В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.

Прислать комментарий Решение

Задача 98720

[Паровозики]

Тема:

[

Динамическое программирование: классические задачи

]

Сложность: 3

N локомотивов, имеющих номера от 1 до N и установленных на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения локомотивы разобьются на несколько групп, движущихся с разной скоростью.
Написать программу, определяющую, сколько начальных расстановок s из N! Возможных дадут в результате p групп движущихся локомотивов.
Формат входных данных
Два числа — 0 < N < 17 и 0 < p < N + 1.
Формат выходных данных
Одно число — s.

Прислать комментарий Решение

Страница: << 19 20 21 22 23 24 25 >> [Всего задач: 277]