Версия для печати
Убрать все задачи

---

Предложенный выше алгоритм перемножения многочленов требует порядка n² действий для перемножения двух многочленов степени n. Придумать более эффективный (для больших n) алгоритм, которому достаточно порядка n^{log 4/log 3} действий.

   Решение

Страница: << 33 34 35 36 37 38 39 >> [Всего задач: 277]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 102929  [Максимальный M-угольник ]

Тема:   [ Задачи на полный перебор ]

Сложность: 4-

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

Входные данные
В первой строке входного файла через пробел записаны два целых числа M и N (3 ≤ M ≤ N ≤ 10). Во второй строке перечислены N точек, каждая из которых задана парой своих координат. Координаты являются вещественными числами и разделяются пробелом.

Выходные данные
В первую строку выходного файла нужно вывести площадь искомого M-угольника, а во вторую – номера точек, являющихся вершинами этого M-угольника (в порядке обхода по или против часовой стрелки). Номера точек разделяются пробелом. Если вариантов решений несколько, то достаточно выдать любой из них. Если же ни один M-угольник с указанными свойствами построить невозможно, то выходной файл должен содержать единственное число 0.

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

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

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

Решение

---

Задача 102937  [Шагающий многоугольник ]

Темы:   [ Многоугольники ] [ Движения ]

Сложность: 4-

На плоскости заданы выпуклый многоугольник M и точка P(x, y). За один ход разрешается центрально-симметрично отразить многоугольник относительно середины любой из его сторон. Требуется найти последовательность ходов, в результате которой точка P оказалась бы накрытой этим многоугольником. 

Входные данные
Во входном файле записано количество вершин многоугольника N (3 ≤ N ≤ 20) и координаты точки x и y. Далее перечислены координаты вершин многоугольника в порядке обхода по часовой стрелке. Все координаты – целые числа, не превосходящие по абсолютной величине 10⁵.

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

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

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

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

Решение

---

Задача 102945  [Кошки-Мышки ]

Тема:   [ Комбинаторика (прочее) ]

Сложность: 4-

Игровое поле для игры «Кошки-мышки» представляет собой совокупность кружков, некоторые из которых соединены линиями. Первый игрок играет за «кошек», второй – за «мышек». В процессе игры кошки и мышки располагаются в кружках игрового поля. Ходы совершаются игроками по очереди. За один ход игрок может передвинуть некоторые из своих фигур (кошек или мышек) по линиям, ведущим из тех кружков, где они в данный момент находятся. Первыми ходят кошки.  В случае если кошка окажется в одном кружке с мышкой, мышка считается съеденной. Цель первого игрока – съесть максимальное число мышек и сделать это как можно быстрее, цель второго – помешать первому игроку.

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

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

Выходные данные
Запишите в выходной файл максимальное количество мышек, съедаемых кошками, минимальное число ходов, необходимых для этого, и все возможные положения кошек после первого хода, обеспечивающие достижение цели за указанное число ходов.

Пример входного файла
8 9
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 8
8 6
1 5
2 3 7

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

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

Решение

---

Задача 76245

Тема:   [ Многочлены ]

Сложность: 4

(В. Баур, Ф.Штрассен) Дана программа вычисления значения некоторого многочлена P(x₁,..., x_n), содержащая только команды присваивания. Их правые части — выражения, содержащие сложение, умножение, константы, переменные x₁,..., x_n и ранее встречавшиеся (в левой части) переменные. Доказать, что существует программа того же типа, вычисляющая все n производных P/x₁,...,P/x_n, причём общее число арифметических операций не более чем в C раз превосходит число арифметических операций в исходной программе. Константа C не зависит от n.

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

Решение

---

Задача 76247

Тема:   [ Многочлены ]

Сложность: 4

Предложенный выше алгоритм перемножения многочленов требует порядка n² действий для перемножения двух многочленов степени n. Придумать более эффективный (для больших n) алгоритм, которому достаточно порядка n^{log 4/log 3} действий.

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

Решение

---

Страница: << 33 34 35 36 37 38 39 >> [Всего задач: 277]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями