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

Задачи

Страница: << 26 27 28 29 30 31 32 >> [Всего задач: 277]

Задача 76260

Тема:

[

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

]

Сложность: 3+

(Московская олимпиада по программированию) Дан неубывающий массив положительных целых чисел a[1]≤a[2]≤...≤a[n]. Найти наименьшее целое положительное число, не представимое в виде суммы нескольких элементов этого массива (каждый элемент массива может быть использован не более одного раза). Число действий порядка n.

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

Задача 98849

[Домино ]

Темы:	[	Обход графа в ширину	]
Темы:	[	Прочие задачи на сообразительность	]

Сложность: 3+

Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до M включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).

Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны.

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

Задание

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

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

В первой строке входного файла DOMINO.DAT содержится одно целое число M (0≤M?100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число N, равное количеству костяшек, удаленных из полного набора. Каждая i-я из последующих N строк содержит по два числа A_i и B_i. Это количества точек на половинках i-й удалённой костяшки.

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

Единственная строка выходного файла DOMINO.SOL должна содержать одно целое число L - минимальное количество цепочек.

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

DOMINO.DAT	DOMINO.SOL
7 2 7 5 3 4	2

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

Решение

Задача 102927

[Кроссворд ]

Тема:

[

Задачи на полный перебор

]

Сложность: 3+

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

Входные данные
Первая строка входного файла содержит целое число N – количество слов в наборе (1 ≤ N ≤ 9). В каждой из N последующих строк содержится по одному слову (некоторые из них могут повторяться). Слово представляет собой последовательность не более чем из 20 русских и/или английских букв.

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

Пример входного файла
СБОРЫ
СОН
ПОТОП
АНТОН

Пример выходного файла
П
СБОРЫ
О Т
АНТОН
П

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

Задача 102952

[Поезда ]

Тема:

[

Прочие задачи на сообразительность

]

Сложность: 3+

Метрополитен города Глупова состоит из единственной одноколейной линии. В нулевой момент времени с начальной и конечной станций этой линии навстречу друг другу начинают двигаться два поезда. Их движение подчиняется следующим правилам.
    Отъезжая со станции, поезд сначала разгоняется, потом некоторое (возможно нулевое) время движется с максимальной скоростью, затем замедляется и, в конце концов, останавливается на очередной станции.
    Поезда останавливаются на всех промежуточных станциях метрополитена.
    На каждой из станций поезда стоят одно и тоже фиксированное время.
    Поезда разгоняются и замедляются с одинаковым, постоянным ускорением.
    Поезда имеют одинаковую максимальную скорость.
    Поезда всегда разгоняются до максимальной скорости, если это не мешает остановиться на следующей станции. Иначе они разгоняются, пока это возможно, а затем сразу же начинают тормозить.

Требуется определить, где и когда поезда столкнутся. «Где» определяется расстоянием от начальной станции до места столкновения, «когда» – временем, когда произойдет столкновение.

Входные данные
В первой строке входного файла содержится целое число N (2 ≤ N ≤ 100) – количество станций на линии. Во второй строке записано N-1 вещественное число – расстояние от начальной станции до второй, от начальной до третьей, ..., от начальной до конечной станции. В третьей строке файла записаны три вещественных числа A, V, S – ускорение, максимальная скорость и время пребывания поезда на станции соответственно.

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

Пример входного файла
3
0.25 2.25
1 1 1

Пример выходного файла
0.38 2.50

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

Задача 98721

[Плитки]

Тема:

[

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

]

Сложность: 3+

У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1 * 1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:

(буквой К обозначена красная плитка, С — синяя, З — зеленая).
После этого Петя заполняет следующую таблицу:

	Красный	Синий	Зеленый
Красный	Y	Y	Y
Синий	Y	N	Y
Зеленый	Y	Y	N

В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали — если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.
Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.
Петя хочет узнать, сколько различных полосок имеет определенную диаграмму смежности. Помогите ему.
(Заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска

не совпадает с полоской, приведенной в начале условия.)

Формат входных данных
Первая строка входного файла содержит число N (1 <= N <= 100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.
Формат выходных данных
Выведите в выходной файл количество полосок длины N, имеющих приведенную во входном файле диаграмму смежности.

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

Страница: << 26 27 28 29 30 31 32 >> [Всего задач: 277]