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

Задачи

Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 56]

Задача 98801

[Без тройных повторений]

Тема:

[

Перебор с отсечениями

]

Сложность: 3

Найти последовательность из 50 нулей и единиц, в которой никакой отрезок не повторяется три раза подряд. Напечатать НЕТ, если такой последовательности не существует. Например, в искомой последовательности нигде не должны встречаться такие отрезки, как 000, или 101010, или 101101101.

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

Решение

Задача 98810

[Рюкзак]

Тема:

[

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

]

Сложность: 3

Из заданных n предметов выбрать такие , чтобы их суммарный вес был менее 30 кг, а стоимость - наибольшей. Напечатать суммарную стоимость выбранных предметов. Точнее- заданы два массива положительных чисел А[1:n] и В[1:n]. Выбрать такие попарно различные числа i₁, i₂,... i_k, чтобы сумма

А[i₁] + A[i₂] +...+ A[i_k] < 30, а сумма

B[i₁] + B[i₂] +...+ B[i_{_k}] = max была максимальной. Напечатать только величину max

Замечание. Можно предполагать , что предметы уже расположены в порядке возрастания или убывания веса А[i], стоимости В[i], цены В[i] / A[i] или какого-либо иного признака.

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

Решение

Задача 98847

[Спички ]

Тема:

[

Площадь

]

Сложность: 3

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

Задание

Напишите программу MATCHES, которая по количеству квадратов N, которые необходимо составить, находит минимальное необходимое для этого количество спичек.

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

Единственная строка входного файла MATCHES.DAT содержит одно целое число N (1≤N≤10⁹).

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

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

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

MATCHES.DAT	MATCHES.SOL
4	12

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

Решение

Задача 98790

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

Тема:

[

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

]

Сложность: 3

Напечатать все представления натурального числа 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

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

Решение

Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 56]