Темы --> Информатика --> Алгоритмы --> Динамическое программирование
    Рекуррентные последовательности(10 задач)
    Динамическое программирование: один параметр(49 задач)
    Динамическое программирование: два параметра(183 задач)
    Динамическое программирование в играх(9 задач)
    Динамическое программирование на графах(25 задач)
    Динамическое программирование по профилю(20 задач)
    Динамика по подмножествам(13 задач)
---> 18 задач <---
Источники --> Личные олимпиады --> Открытая олимпиада школьников
    2002(9 задач)
    2003(10 задач)
    2004(13 задач)
    2005(12 задач)
    2006(12 задач)
    2007(11 задач)
    2008-2009(19 задач)
    2009-2010(23 задач)
    2010-2011(19 задач)
    2011-2012(8 задач)
    2012-2013(21 задач)
    2013-2014(8 задач)
    2014-2015(8 задач)
Страница: << 1 2 3 4 Отображать по:
#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
#3337
Забор
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На одну Очень Известную Планету упал метеорит. Метеорит в атмосфере распался на \(N\) кусков, каждый из которых упал в свою точку.

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

Конечно, ученые хотят огородить как можно больше кусков, но как всегда, все упирается в деньги. Главный бухгалтер решил составить такую таблицу: для каждого \(K\) от 1 до \(N\) определить, какой минимальной длины нужно построить забор, чтобы внутри него оказалось не менее \(K\) кусков метеорита. Помогите ему.

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

В первой строке входного файла записано единственное целое число \(N\). В каждой из следующих \(N\) строк записано по паре целых чисел, по модулю не превосходящих \(1\,000\) - координаты точек, куда упали куски метеорита. Никакие два куска не упали в одну и ту же точку.

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

Выведите \(N\) чисел, \(i\)-е (\(1 \le i \le N\)) должно быть равно минимальной длине забора, внутри которого окажется не менее \(K\) кусков метеорита. Выведенный ответ будет сравниваться с правильным с точностью до \(10^{-6}\).

Примечания

Тесты состоят из четырёх групп.

  1. Тесты 1--2, из условия, оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N \le 16\). Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le N \le 30\). Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Offline-группа. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Тесты объединяются в подгруппы, каждая из которых оценивается в 10 баллов, баллы за каждую подгруппу начисляются только при прохождении всех тестов подгруппы. Подгруппы соответствуют ограничениям \(N \le 40\), \(N \le 60\), \(N \le 80\), \(N \le 100\).

Примеры
Входные данные
4
0 0
0 1
1 0
1 1
Выходные данные
0.000000000
2.000000000
3.414213562
4.000000000
Входные данные
3
1 1
0 0
2 0
Выходные данные
0.000000000
2.828427125
4.828427125
#112091
Шустрая черепашка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Пафнутий и его друзья — большие любители разнообразных настольных игр. Особенно им нравятся игры, требующие как можно быстрее производить в уме непростые вычисления, поэтому абсолютным хитом их вечерних посиделок в аудиториях НУОП (Неизвестного университета олимпиадного программирования) стала игра «Шустрая черепашка». В комплект игры входят:

* Клетчатое поле из \(N\) рядов по \(M\) клеток. Каждая клетка поля либо свободна, либо блокирована для перемещения.

* Q игровых карточек. Каждая карточка содержит описание множества стартовых клеток A, множества дополнительно блокируемых клеток B и множества конечных клеток C. Множества A, B и C непусты, попарно не пересекаются и состоят из свободных клеток.

* Маленькая фишка в форме черепашки.

Правила игры очень просты. Игроки последовательно разыгрывают игровые карточки. Как только открывается очередная карточка, игрокам необходимо вычислить, сколько существует хороших троек клеток (\(a_i b_j c_k)\), где \(a_i \in A\), \(b_j \in B\), \(c_k \in C\). Тройка клеток называется хорошей, если можно провести черепашку из стартовой клетки ai в конечную клетку \(c_k\), не посещая при этом клетку \(b_j\). На перемещение черепашки наложено три условия:

1. Черепашка имеет право перемещаться только вниз и вправо в пределах поля.

2. Находиться на блокированных клетках запрещено

3. Клетка \(b_j\) также блокируется для перемещения

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

Формат входного файла

Первая строка входного файла содержит два целых числа \(N\) и \(M\) (1 ≤ \(N\), \(M\) ≤ 150) — количество строк и столбцов игрового поля.

Следующие \(N\) строк по \(M\) символов описывают игровое поле в порядке следования сверху вниз, слева направо. Символ ‘.’ соответствует свободной клетке, а ‘#’ — занятой. Строки нумеруются от 1 до \(N\), столбцы — от 1 до \(M\)

Следующая строка содержит целое число \(Q\) (1 ≤ \(Q\) ≤ 100 000) — количество игровых карточек.

Далее следуют \(Q\) блоков, описывающих карточки. Каждый блок состоит из трех строк, описывающих множества \(A\), \(B\) и \(C\) соответственно. Первое число описания определяет размер соответствующего множества, после чего перечисляются его клетки. Каждая клетка задается двумя числами — номером строки и номером столбца. Все клетки в описании различны. Смотрите комментарии к примеру для лучшего понимания формата входных данных.

Гарантируется, что все множества непусты, все клетки всех множеств являются свободными и никакая клетка не принадлежит более чем одному множеству из какой-то карточки.

Формат выходного файла

В выходной файл выведите ровно \(Q\) чисел по одному на строке — правильные ответы на карточки в порядке их следования во входном файле.

Комментарии

В приведенном примере игровой комплект содержит две карточки

Во всех тройках первой карточки черепашка стартует в верхнем левом углу и финиширует в правом нижнем. Несложно видеть, что это возможно сделать, только если из трех элементов множества \(B\) блокируется первая клетка второй строки, то есть хорошей тройкой является \((1, 1) - (2, 1) - (5, 6)\).

На второй карточке хорошими являются тройки: \((1, 2) - (3, 1) - (5, 6)\), \((2, 1) - (3, 1) - (5, 6)\), \((2, 1) - (3, 3) - (5, 1)\).

Система оценивания

Тесты к этой задаче состоят из четырех групп

0. Тест 1. Тест из условия, оценивается в ноль баллов.

1. Тесты 2–18. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы.

2. Тесты 19–32. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.

3. В тестах этой группы дополнительные ограничения отсутствуют, однако гарантируется, что \(N\) и \(Q\)total будут равномерно возрастать с номером теста. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура, причем только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.

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