Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 378 379 380 381 382 383 384 >> Отображать по:
#3706
Immediate Delivery
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

Вася и Петя работают курьерами в фирме "Мгновенная доставка". Сегодня им надо доставить огромное количество посылок по всему городу.

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

Вася и Петя должны посетить все перекрестки, чтобы доставить посылки. Они хотят разделить все задание на две части так, чтобы минимизировать время последней доставки.

Офис компании "Мгновенная доставка" расположен на перекрестке номер 1.

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

В первой строке заданы целые числа n (1 ≤ n ≤ 18) и m - количество пунктов и дорог.

Следующие m строк описывают дороги. Каждая дорога задается тремя целыми числами: номерами перекрестков xi и yi, которые она соединяет, (1 ≤ x i, yi ≤ n) и временем ti, которое нужно, чтобы по проехать по ней (1 ≤ ti ≤ 1000). Между каждой парой перекрестков не более чем одна дорога. Никакая дорога не соединяет перекресток с самим собой.

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

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

Примечание
В примере выводить нужно только одно число. Здесь приведён пример разбиения, но его выводить не нужно.
Примеры
Входные данные
6 6
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10
Выходные данные
40
4 1 2 3 4 3
3 1 2 5 6
#3711
Большой, белый, очень прямоугольный
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Во входном файле записана сначала высота \((N)\), а затем ширина \((M)\) таблицы \(((1 \le N \le 5000)\), \((1 \le M \le 5000))\), а затем записано \((N)\) строк по \((M )\) чисел в каждой строке, где \(0\) означает, что соответствующая клетка таблицы выкрашена в белый цвет, а \(1\) – что в черный.

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

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

Примеры
Входные данные
5 6
1 0 0 0 1 0
0 0 0 0 1 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
Выходные данные
9
#3712
Логическое дерево
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Каждая вершина дерева имеет связанное с ней логическое значение (1 или 0). Кроме этого, каждая внутренняя вершина имеет связанную с ней логическую операцию („И“ или „ИЛИ“). Значение вершины с операцией „И“ — это логическое „И“ значений её детей. Аналогично, значение вершины с операцией „ИЛИ“ — это логическое „ИЛИ“ значений её детей. Значения всех листьев задаются во входном файле, поэтому значения всех вершин дерева могут быть найдены.

Наибольший интерес для нас представляет корень дерева. Мы хотим, чтобы он имел заданное логическое значение \(v\), которое может отличаться от текущего. К счастью, мы можем изменять логические операции некоторых внутренних вершин (заменить „И“ на „ИЛИ“ и наоборот).

Дано описание логического дерева и набор вершин, операции в которых могут быть изменены. Найдите наименьшее количество вершин, которые следует изменить, чтобы корень дерева принял заданное значение \(v\). Если это невозможно, то выведите строку «IMPOSSIBLE» (без кавычек).

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

В первой строке входного файла находятся два числа \(n\) и \(v\) (\(1 \le n \le 10\,000, 0 \le v \le 1\)) — количество вершин в дереве и требуемое значение в корне соответственно. Поскольку все вершины имеют ноль или двоих детей, то \(n\) нечётно. Следующие \(n\) строк описывают вершины дерева. Вершины нумеруются от \(1\) до \(n\).

Первые \((n-1)/2\) строк описывают внутренние вершины. Каждая из них содержит два числа — \(g\) и \(c\), которые принимают значение либо \(0\), либо \(1\). Если \(g=1\), то вершина представляет логическую операцию „И“, иначе она представляет логическую операцию „ИЛИ“. Если \(c=1\), то операция в вершине может быть изменена, иначе нет. Внутренняя вершина с номером \(i\) имеет детей \(2i\) и \(2i+1\).

Следующие \((n+1)/2\) строк описывают листья. Каждая строка содержит одно число \(0\) или \(1\) — значение листа.

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

В выходной файл выведите ответ на задачу.

Примеры
Входные данные
9 1
1 0
1 1
1 1
0 0
1
0
1
0
1
Выходные данные
1
Входные данные
5 0
1 1
0 0
1
1
0
Выходные данные
IMPOSSIBLE
#3717
Числа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дана последовательность чисел a1, a2, ..., an. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом.

Пример начальной последовательности:

1 50 51 50 1

удаляем четвертое число, штраф 50·(1 + 51) = 2600, получаем

1 50 51 1

удаляем третье число, штраф 51·(50 + 1) = 2601, получаем

1 50 1

удаляем второе число, штраф 50·(1 + 1) = 100.

Итого, штраф 5301.

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

В первой строке входного файла расположено одно число n (1 ≤ n ≤ 100) — количество чисел в последовательности.

Во второй строке находятся n целых чисел a1, a2, ... an; никакое из чисел по модулю не превосходит 100.

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

Выведите в выходной файл одно число — минимальный суммарный штраф.

Примеры
Входные данные
5
1 50 51 50 1
Выходные данные
5301
#3719
Дубы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Внутренние распорядки министерства позволяют срубать дуб только в двух случаях:

  • если и ближайший дуб слева, и ближайший дуб справа строго ниже, чем данный дуб;
  • если и ближайший дуб слева, и ближайший дуб справа строго выше, чем данный дуб.

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

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

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

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

Первая строка входного файла содержит целое число n — количество дубов, растущих на аллее (2 ≤ n ≤ 200). Вторая строка содержит n чисел — высоты дубов, приведенные слева направо. Высоты дубов — положительные целые числа, не превышающие 1 000.

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

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

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

Дубы нумеруются слева направо натуральными числами от 1 до n.

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

Примеры
Входные данные
5
3 2 4 8 5
Выходные данные
2
2
4
Страница: << 378 379 380 381 382 383 384 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест