Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование по профилю
---> 20 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 >> Отображать по:
#19
Треугольная реформа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Король Полигонии Трианг IV помешан на реформах. Чтобы войти в мировую историю, он решил провести территориальную реформу в своей стране. Страна Полигония имеет форму простого многоугольника, то есть ее граница не имеет самопересечений и самокасаний. В Полигонии большую роль играют внутренние диагонали — отрезки, соединяющие вершины государственной границы и полностью проходящие по территории страны, не касаясь границы. При этом форма Полигонии такова, что никакие две внутренние диагонали не лежат на одной прямой.

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

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

Формат входных данных

В первой строке входных данных задается число N (3 ≤ N ≤ 20) — количество вершин многоугольника, образующего границу Полигонии. В следующих N строках находятся по 2 целых числа, по абсолютной величине не превосходящих 10 000 — координаты вершин в порядке обхода многоугольника против часовой стрелки. Гарантируется, что никакие три последовательные вершины многоугольника не лежат на одной прямой, и он не имеет самопересечений и самокасаний. Также гарантируется, что никакие две диагонали, содержащиеся внутри многоугольника, не лежат на одной прямой.

Формат выходных данных

В первую строку  выведите наименьшее количество административных треугольников, на которое можно разбить Полигонию.

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

В каждую из следующих K строк выведите 4 целых числа — координаты начала и конца соответствующей диагонали разбиения, полностью лежащей внутри многоугольника и не проходящей по его границе.

Если искомых разбиений несколько, выведите любое из них.

Примеры

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

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

Рисунок к тесту

4
0 0
1 0
1 1
0 1

2
1
1 1 0 0

 1

10
-6 0
0 2
6 0
3 3
6 4
2 4
0 6
-2 4
-6 4
-3 3

4
3
2 4 -2 4
0 2 3 3
-3 3 0 2

 2
#75
Симпатичные узоры
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1 х 1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника N х M метров. Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2 х 2 метра, полностью покрытого плитками одного цвета. Для составления финансового плана директору Васе необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

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

Вводятся два положительных целых числа N и M (1 ≤ N · M ≤ 30).

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

Выведите единственное число –  количество различных симпатичных узоров, которые можно выложить во дворе размера N х M. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.

Примеры
Входные данные
1 2
Выходные данные
4
Входные данные
2 3
Выходные данные
50
#76
Симпатичные узоры возвращаются
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Со времен написания условия предыдущей задачи многое изменилось. Симпатичные узоры (о том, что это такое – см. задачу "Симпатичные узоры") стали очень популярны по всему миру, поэтому люди готовы содержать очень большой участок земли, лишь бы иметь на ней узор, не встречающийся больше нигде.

Теперь компания BrokenTiles является ведущим производителем симпатичных узоров в мире! Для составления плана исполнительному директору Васе по-прежнему необходимо знать, сколько клиентов могут рассчитывать на узор данных размеров.

Так как масштабы буквально мировые, N <= 10100. Однако Вася не любит большие числа, поэтому просит выдать ответ по модулю P.

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

В первой строке входных данных  содержатся три положительных целых числа, разделенные пробелом – N, M и P (1 <= N <= 10100, 1 <= M <= 5, 1 <= P <= 10 000).

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

Выведите  количество различных симпатичных узоров N x M по модулю P .

Примеры
Входные данные
2 2 5
Выходные данные
4
Входные данные
3 3 42
Выходные данные
28
#78
Прямоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан прямоугольник N x M, состоящий из квадратиков 1 x 1. Некоторые квадратики вырезали. Надо найти наименьшее количество прямоугольников, на которое можно разрезать оставшуюся фигуру.

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

В первой строке входных данных заданы числа N и M, (1 ≤  N, M ≤ 10). Далее следует N строк. В (i+1)-ой содержится M чисел; j-е число равно 1, если клетку на i-й строке и в j-м столбце вырезали из доски, 0 – если оставили.

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

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

Примеры
Входные данные
2 2 
0 0
1 0
Выходные данные
2
#587
Симпатичные узоры
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача E ]
Прямоугольное поле заполнено белыми и черными клетками, требуется определить количество вариантов замощения поля таким образом, чтобы на нем не встречалось ни одного белого или черного квадрата 2 на 2.

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер 1×1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника M×N метров.

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

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2×2 метра, полностью покрытого плитками одного цвета. На рисунке 1 показаны примеры различных симпатичных узоров, а на рисунке 2 - несимпатичных.

Для составления финансового плана директору необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

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

В первой строке входных данных содержатся два положительных целых числа, разделенных пробелом: \(M\) и \(N\) (1 <= \(M\)·\(N\) <= 30).

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

Выведите единственное число - количество различных симпатичных узоров, которые можно выложить во дворе размера \(M\)×\(N\) . Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.

Примеры
Входные данные
1 2
Выходные данные
4
Входные данные
4 1
Выходные данные
16
Страница: 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест