Автор: | Фольклор | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Найти количество способов замостить домино 1 × 2 поле n × m.
Во входном файле содержатся числа n и m.
В выходной файл выведите ответ.
1 ≤ n ≤ 16;
1 ≤ m ≤ 10;
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Входной файл: | input.txt | Ограничение времени: | 2 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 512 Мб |
Коммивояжёр возвращается в систему Альфы Центавра! Население системы с нетерпением ждёт его прибытия — каждый хочет приобрести что-нибудь с далёких планет!
Как обычно, коммивояжёр хочет минимизировать транспортные расходы. Он выбирает начальную планету, прилетает туда на межгалактическом корабле, после чего посещает все остальные планеты системы в порядке, минимизирующем суммарную стоимость посещения, и на другом межгалактическом корабле улетает обратно. Естественно, коммивояжёр не хочет летать ни на какую планету дважды.
Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!
В системе Альфы Центавра n планет. Это число записано в первой строке входного файла. Следующие n строк содержат по n чисел каждая: j-ое число на i-ой из этих строк — стоимость перемещения aij от i-ой планеты до j-ой. Числа в каждой строке разделены пробелами. aij = -1 означает, что из планеты i нельзя на прямую добраться до планеты j.
Выходной файл должен содержать единственное целое число — длину оптимального пути. Если не существует пути проходящего через все планеты, вывести -1.
1 ≤ n ≤ 19, aij ≤ 108
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | И. Блинов, А. Кленин | Ограничение времени: | 10 сек | |
Входной файл: | input.txt | Ограничение памяти: | 512 Мб | |
Выходной файл: | output.txt |
Юная программистка Маша уговорила своего друга Васю сходить с ней в торговый центр и помочь в выборе новой шляпы. Торговый центр состоит из N бутиков, каждый из которых продаёт шляпы определённого бренда. Бренды обозначены малыми латинскими буквами. Один и тот же бренд может встречаться в нескольких бутиках. Бутики расположены в один ряд и пронумерованы от 1 до N.
Маша выбирает шляпу в несколько заходов. Заход номер i состоит из посещения отрезка бутиков с номерами от Li до Ri (1 ≤ Li ≤ Ri ≤ N). Маше нравится процесс выбора, поэтому она хочет сделать как можно больше заходов. Однако, чтобы не слишком сильно испытывать терпение Васи, она решила делать заходы по следующим правилам:
Например, для ряда из 5 бутиков с брендами caabb
возможна такая последовательность заходов:
(1, 5), (1, 4), (2, 5), (3, 4), (2, 4), (3, 5), (4, 4), (4, 5), (5, 5).
Требуется написать программу, определяющую по данному набору бутиков максимальное количество заходов, которые могут сделать Маша с Васей.
В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче
в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text
").
За тесты c 1 по 20 начисляется по 2 балла, за остальные (с 21 по 40) по 3 балла.
Первая строка входного файла содержит целое число T — количество тестов. Далее идут T описаний тестов, по две строки на описание.
Первая строка каждого теста содержит целое число N — количество бутиков. Вторая строка каждого теста состоит из N малых латинских букв и задаёт последовательность брендов в бутиках.
Выходной файл должен содержать T ответов на тесты.
Каждый ответ состоит из одной строки, содержащей целое число — максимальное количество заходов для соответствующего теста.
В случае, если ответ на тест найти не удалось, выведите для этого теста одну строку с числом 0.
Буквы брендов находятся в диапазоне от 'a
' до 't
'.
1 ≤ N ≤ 1000
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Входной файл: | input.txt | Ограничение времени: | 1 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 64 Мб |
Дан набор ai из N чисел. Необходимо расположить числа в последовательности a1, a2, …, aN один за другим так, чтобы максимизировать следующую целевую функцию: (a1*a2 + a2*a3 + … + aN−1*aN)
Входной файл содержит N, за которым следует N чисел ai.
В выходном файле единственное число - максимальное значение целевой функции.
2 ≤ N ≤ 16
1 ≤ ai ≤ 106
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | А. Щуров | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Талантливый художник Казимир создал профиль в социальной сети для художников. Он публикует там свои картины. Каждая картина Казимира представляет собой квадрат цвета ci. Картины в профиле этой социальной сети размещаются в три столбца и произвольное количество строк в указанном порядке (числа обозначают последовательные номера картин):
6 | 5 | 4 |
3 | 2 | 1 |
Когда Казимир публикует очередную картину, она располагается в левом верхнем углу, а все предыдущие картины сдвигаются вправо, при необходимости переходя на новую строку:
7 | 6 | 5 |
4 | 3 | 2 |
1 |
Казимир хочет, чтобы картины в его профиле были расположены супрематично, то есть чтобы всякая картина соседствовала с ровно одной картиной такого же цвета. Например, профиль (К, З и С обозначают красный, зеленый и синий квадраты соответственно)
К | С | З |
З | С | С |
К | К | С |
не является супрематичным, потому что, красный квадрат в левом верхнем углу имеет ноль красных соседей, синий квадрат в центре имеет двух синих соседей и т.д. Но после публикации еще одного красного квадрата профиль станет супрематичным:
К | К | С |
З | З | С |
С | К | К |
С |
В профиле у Казимира уже опубликованы некоторые его картины. Помогите Казимиру определить минимальное количество и последовательность картин, которые необходимо опубликовать, чтобы его профиль стал супрематичным.
В первой строке входного файла содержится единственное число N — количество уже опубликованных картин. В следующих строках находятся N целых чисел ci — цвета картин (1 — красный, 2 — зеленый, 3 — синий). Картины во входном файле расположены в порядке, описанном в условии.
Выходной файл в должен содержать единственное целое число M — минимальное количество картин, которые нужно опубликовать Казимиру. Далее должны следовать M целых чисел pi — цвета картин в том порядке, в котором Казимир должен их публиковать. Если существует несколько вариантов ответа, выведите любой из них.
1 ≤ ci, pi ≤ 3
1 ≤ N ≤ 100
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Автор: | С. Пак | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Армия галактического альянса состоит из 2 N дивизионов боевых дроидов. Верховное командование приняло решение сократить количество дивизионов вдвое, объединив их попарно. Объединение двух дивизионов происходит следующим образом: каждый из дивизион разбивается на одинаковое количество Ki отрядов дроидов, после чего отряды сливаются и формируют Ki увеличенных отрядов, составляющих новый объединенный дивизион.
Программное обеспечение дроидов поддерживает разбиение дивизиона дроидов только на равные по количеству отряды. Например, дивизион из 6 дроидов может быть разбит на 1 отряд из 6 дроидов, 2 отряда из 3 дроидов, 3 отряда из 2 дроидов или 6 отрядов из 1 дроида.
Считается, что после объединения двух дивизионов, максимальную эффективность в бою имеет объединенный дивизион с наибольшим количеством отрядов. Например, максимально эффективный способ объединить два дивизиона, состоящие из из 6 и 4 дроидов — это разбить каждый на два отряда по 3 и 2 дроида, соответственно. Затем сформировать два увеличенных отряда по 5 дроидов. Новый объединенный дивизион будет состоять из 10 дроидов, состоящих в 2 отрядах.
Рассмотрим армию, состоящую из 4 дивизионов: 4 9 3 6. Возможные варианты разбиения дивизионов на равные по численности отряды: 1 дивизион: 1 по 4, 2 по 2, 4 по 1. 2 дивизион: 1 по 9, 3 по 3, 9 по 1. 3 дивизион: 1 по 3, 3 по 1. 4 дивизион: 1 по 6, 2 по 3, 6 по 1.
Соответственно, оптимальным решением будет объединение дивизионом 1 и 4 с разбиением на 2 отряда каждого, а также дивизионов 2 и 3 с разбиением на 3 отряда каждого. Общее количество отрядов в армии после объединения — 5.
Требуется данные 2 N дивизионов дроидов попарно объединить таким образом, чтобы общее количество отрядов в армии было максимальным.
Входной файл содержит целое положительно число N, за которым следуют 2 N целых положительных чисел Di — количество дроидов в i-ом дивизионе.
Выходной файл должен содержать одно целое число — максимально возможное количество отрядов в армии после реформы.
1 ≤ N ≤ 10; 1 ≤ Di ≤ 109
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Автор: | И. Туфанов | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Школьник Вася приготовил доклад по географии, затратив минимальное количество усилий. Доклад у него получился вообще без текста и содержит лишь n картинок, скачанных из интернета. Тем не менее, Вася хочет представить свою работу в наилучшем свете. Для этого он пытается расположить картинки в таком порядке, чтобы доклад занял как можно больше страниц.
Текстовый процессор, который использует Вася, работает следующим образом. Каждая страница имеет высоту k сантиметров. Картинки располагаются одна за другой, начиная с первой страницы. Если очередная картинка не входит на текущую страницу целиком, то текстовый процессор переходит на следующую страницу.
Зная высоту каждой картинки в сантиметрах hi, определите порядок следования картинок, при котором полученный документ будет иметь наибольшее количество страниц.
В тестовом примере имеется 4 картинки с высотами 6 см, 4 см, 6 см и 4 см. Высота страницы составляет 10 см. Одно из оптимальных решений — расположить картинки в следующем порядке: 4, 4, 6, 6. Тогда первые две картинки окажутся на первой странице, а оставшиеся две картинки займут по одной странице каждая. Таким образом, весь доклад займёт 3 страницы.
Входной файл содержит два целых числа — n k, за которыми следуют n целых чисел — h1… hn.
Выходной файл должен содержать n целых чисел — высоты картинок в оптимальном порядке. Если имеется несколько оптимальных ответов, выведите любой из них.
1 ≤ n ≤ 15;
1 ≤ k ≤ 108;
1 ≤ hi ≤ k;
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|