Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование по профилю
---> 6 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 2 >> Отображать по:
#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
#1032
Узор
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

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

Плитки паркета, которыми выкладывается пол комнаты, состоят из квадратиков 1x1, каждый из которых может быть либо белым, либо черным. В свою очередь, комната имеет размеры NxM. На плане комнаты указано, какой квадрат комнаты какого цвета должен быть.

Существует несколько форм паркетных плиток:

Квадратики одной паркетной плитки могут быть окрашены по-разному. Может существовать несколько типов плиток одинаковой формы, но окрашенных по-разному. Плитки разных типов могут иметь разную стоимость. Количество плиток каждого типа не ограничено. Плитки разрешается как угодно поворачивать (на углы, кратные 90 градусам). Не разрешается разламывать плитки, а также класть их лицевой стороной вниз.

Изначально, какая-то часть пола может уже быть выложена плиткой.

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

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

В первой строке входного файла записаны три числа: N, M (размеры комнаты) и K (количество доступных видов плитки). 1≤N≤8, 1≤M≤8, 1≤K≤10. Далее идет описание желаемой раскраски пола. Описание представляет собой N строчек по M чисел в каждой, где 0 обозначает белый цвет, 1 — черный, 2 — то, что квадрат уже выложен плиткой. В последних K строчках находятся описания доступных типов плитки в следующем формате:

<форма> <стоимость> <окраска>

<Форма> — это число от 1 до 4, описывающее форму плитки (см. рисунок выше)

<Стоимость> — это натуральное число, не превосходящее 10000, задающее стоимость одной плитки такого типа

<Окраска> — это от одного до трех чисел 0 или 1. Количество чисел совпадает с количеством квадратиков, из которых состоит плитка. Числа задают цвета квадратиков плитки в том порядке, в каком квадратики пронумерованы на рисунке.

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

В выходной файл выведите единственное число — минимальную стоимость укладки или –1, если требуемым образом уложить плитку невозможно.

Примеры
Входные данные
4 3 3
2 2 2
2 0 0
2 1 2
2 2 2
2 10 0 0
1 5 1
4 6 0 0 1
Выходные данные
15
#1938
ЕГЭ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

С целью упрощения ЕГЭ по литературе, было решено оставить в нем вопросы только с ответами «да» или «нет». Бланк ответов представляет клетчатое поле из \(N\) строк и \(M\) столбцов, в котором каждая клеточка соответствует своему вопросу. Ученику необходимо один раз перечеркнуть по диагонали те клеточки, которые, по его мнению, соответствуют вопросам с ответом «нет» (перечеркивать можно по любой из двух диагоналей). При этом во избежание ошибок при сканировании, никакие две диагонали не должны "сливаться", то есть иметь общий конец.

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

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

Вводится два натуральных числа – количество строк \(N\) и количество столбцов \(M\). Количество вопросов в варианте не превосходит 100, то есть \(1 ≤ N ∙ M ≤ 100\).

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

В первую строку выведите одно число — максимальное количество вопросов с ответом «нет», которое можно включить в вариант. В следующие N строк выведите по M символов – пример такого бланка с правильными ответами, верно распознаваемый компьютером. Никакие две диагонали не должны иметь общих концов. Руководствуйтесь следующими обозначениями: . (точка) — пустая клетка, соответствующая ответу «да»; / или \ — перечеркнутые по диагонали справа налево или слева направо клетки, соответствующие ответу «нет». Если существует несколько вариантов заполнения бланка, выведите любой.

Примеры
Входные данные
1 1
Выходные данные
1
/
Входные данные
2 1
Выходные данные
2
/
/
Входные данные
3 3
Выходные данные
6
///
../
\\.
#3184
Космические исследования
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Отделу космических исследований поступило задание сфотографировать из космоса \(n\) объектов в заданной области. Область имеет форму квадрата размером \(50\times 50\) километров. Если разделить ее на квадраты размером \(1\times 1\) километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов.

Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже.

Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером \(k\times k\) километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами \(x\) и \(y\) от \(1\) до \(k\) километров.

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

Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области.

Требуется написать программу, которая по заданному расположению объектов и размеру снимка \(k\) определит минимальное время, за которое можно сделать снимки всех объектов заданной области.

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

Первая строка входного файла содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 1000\), \(1 \le k \le 5\)).

Следующие \(n\) строк содержат по два целых числа: \(x_i\) и \(y_i\) — координаты объектов в заданной области (\(1 \le x_i, y_i \le 50\)).

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

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

Примечание

В первом примере возможна следующая последовательность действий: сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок, 9 раз сместиться на запад, сместиться на север, сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок. Всего требуется 30 перемещений участка съемки.

Во втором примере объекты расположены там же, но размер снимка больше, поэтому можно действовать так: сделать снимок, сместиться на север, сделать снимок, 8 раз сместиться на восток, сделать снимок, сместиться на север, сделать снимок. Всего требуется лишь 10 перемещений участка съемки.

В третьем примере перемещать участок съемки не требуется, можно просто сделать снимок.

Четвертый пример соответствует приведенному выше рисунку.

Правильные решения для тестов, в которых \(k = 1\), будут оцениваться в 30 баллов.

Правильные решения для тестов, в которых \(k \gt 1\) и \(1 \lt n \le 15\), будут оцениваться так же в 30 баллов.

Примеры
Входные данные
4 1
1 1
10 2
1 3
10 4
Выходные данные
30
Входные данные
4 2
1 1
10 2
1 3
10 4
Выходные данные
10
Входные данные
1 1
1 1
Выходные данные
0
Входные данные
3 3
3 3
3 6
6 3
Выходные данные
7
#3203
Вася и его друзья
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В новой игре "Closed Loops 7" игрокам предлагается клетчатая таблица \(N\) на \(M\) клеток. Ход состоит в том, что очередной игрок рисует цикл - замкнутую линию без самопересечений, идущую только по сторонам клеток. Каждый цикл можно нарисовать только один раз за всю игру (при этом, конечно, не запрещается рисовать циклы, пересекающиеся с уже нарисованными). Игроки ходят по очереди. Выигрывает тот, кто рисует последний возможный цикл. К примеру, если \(N=2\), \(M=1\), то циклов всего три и игрок, делающий третий ход, выигрывает.

Вася позвал \(K-1\) друзей поиграть с ним. Чтобы произвести впечатление, он непременно хочет выиграть. Для этого ему нужно узнать, каким по счету игроком он должен быть, чтобы гарантированно одержать победу. Вася наслышан о ваших успехах в программировании, и за помощью он обратился именно к вам.

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

Даны три целых числа: \(N, M\) - размеры таблицы (\(1 \le N \le 100, 1 \le M \le 8\)) и \(K\) - количество игроков (\(1 < K \le 10^9\)).

Выходные данные
Выведите одно число от 1 до \(K\) - каким по счету игроком должен быть Вася, чтобы выиграть.

Примечания

Тесты состоят из трёх групп. В этой задаче нет off-line групп.

  1. Тесты 1 и 2, из условия, оцениваются в 0 баллов.
  2. Тесты 3--15. \(N \cdot M \le 24\). Эта группа оценивается в 40 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 16--42. Полные ограничения, группа оценивается в 60 баллов. Баллы начисляются только при прохождении всех тестов группы.
Примеры
Входные данные
2 1 2
Выходные данные
1
Входные данные
1 8 8064
Выходные данные
36
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест