Каталог по источникам

Задачи

Страница: << 36 37 38 39 40 41 42 >> [Всего задач: 272]

Задача 98790

[Разложение на слагаемые]

Тема:

[

Генерация объектов любым методом

]

Сложность: 3

Напечатать все представления натурального числа N суммой натуральных чисел. Перестановка слагаемых нового способа не даёт.

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

Решение

Задача 102939

[SOS ]

Тема:

[

Вычислительная геометрия (прочее)

]

Сложность: 3

В океане в точке с координатами (X, Y) потерпел крушение корабль. Недалеко от места катастрофы находится остров, имеющий форму N-угольника (не обязательно выпуклого). Спасшиеся после кораблекрушения пассажиры оказались в спасательной шлюпке, которая может двигаться относительно воды в любом направлении со скоростью, не превосходящей V. В процессе движения шлюпка может менять как направление, так и величину своей скорости.

В океане имеется постоянное течение, вектор скорости которого – (VT_x, VT_y). Тем самым, вектор скорости шлюпки относительно земли определяется как сумма вектора скорости течения (VT_x, VTy) и вектора скорости шлюпки относительно воды (V_x, V_y).

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

Входные данные
Входной файл содержит (в указанном порядке) следующие данные: координаты (X, Y) места крушения, количество вершин острова N (3 ≤ N ≤ 50), координаты вершин острова, заданные в порядке обхода острова по часовой стрелке (2N чисел), максимальную скорость спасательной шлюпки V (V > 0) и вектор скорости течения (VT_x, VT_y). Все числа во входном файле, кроме N, являются вещественными и разделяются пробелами и/или символами перевода строки.

Выходные данные
Выведите в выходной файл искомое время не менее чем с 6 верными значащими цифрами. Если шлюпка до острова доплыть не сможет, выходной файл должен содержать сообщение «добраться невозможно».

Пример входного файла
4 3
3
0 0 0 3 3 0
2 1 1

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

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

Задача 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», если кроссворд, удовлетворяющий условию задачи, составить невозможно.

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

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

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

Страница: << 36 37 38 39 40 41 42 >> [Всего задач: 272]