Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 275 276 277 278 279 280 281 >> Отображать по:
#2862
Последовательность
  
Сложная.

Последовательность чисел называется монотонно убывающей, если для любого номера \(i\) (кроме последнего) выполняется \(A_i > A_{i+1}\). Последовательность чисел называется монотонно возрастающей, если для любого номера \(i\) (кроме последнего) выполняется \(A_i < A_{i+1}\). Последовательность называется монотонной, если она или монотонно убывающая, или монотонно возрастающая. Дана последовательность \(A_i\) из \(N\) чисел. За одно действие каждый элемент последовательности можно либо увеличивать на 1, либо уменьшать на 1. Требуется изменить последовательность так, чтобы в ней содержалось ровно \(K\) монотонных непересекающихся последовательностей (один элемент тоже является последовательностью) за минимально возможное количество действий.

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

В первой строке входных данных содержатся числа \(N\) и \(K\) --- количество элементов в последовательности и сколько должно быть монотонный частей, соответственно (\(1 \leq N \leq 50, 1 \leq K \leq 25\)). В слеюущей строке содержатся \(N\) чисел --- элементы последовательности, каждое число по модулю не превосходит \(20\,000\,000\).

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

Одно число, ответ на задачу

Примеры
Входные данные
4 1 
1 1 1 1
Выходные данные
4
Входные данные
6 2
1 2 3 4 5 6
Выходные данные
0
#2863
План уничтожения
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Секретный бункер уходит на N этажей вниз. Под нижним этажом бункера находится сверхсекретная лаборатория. Злобный диверсант хочет вывести лабораторию из строя, залив её водой (даже очень небольшого количества воды хватит, чтобы запоганить сверхточные приборы). Для этого он использует лужицы воды, остающиеся от жизнедеятельности обитателей бункера. В лужицах i-го этажа находится Ei воды. Диверсанту известно, что если на нём скопится больше Сi воды, то перегородка не выдержит и вся вода сольется на этаж ниже. Он может проделать отверстия в некоторых перегородках, по которым вода также стечет вниз. Проделать отверстие в полу i-го этажа стоит Pi у.е. Помогите диверсанту уничтожить лабораторию с минимальными материальными затратами.

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

Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 500000) - количество этажей в бункере, в следующих N строках находятся тройки целых чисел Ci, Ei, Pi (0 < Ei ≤ Ci < 1000000; E1+E2+...+EN < 2000000000; Pi > 0; P1+P2+...+PN < 2000000000). Этажи нумеруются сверху вниз.

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

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

Примеры
Входные данные
4 
1 1 1 
1 1 3 
3 1 2 
3 1 10
Выходные данные
3
1
3
#2864
Вполоборота
  
Темы: [Строки]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Словом считается непустая последовательность больших и маленьких латинских букв. Вам необходимо развернуть все слова во входном файле задом наперед.

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

Во входном файле записано все что угодно. Его размер не превышает 1 Мб.

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

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

Примеры
Входные данные
Summer Informatics School.
Now in Perm!
Выходные данные
remmuS scitamrofnI loohcS.
woN ni mreP!
#2865
Просто матрица
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
+структуры данных

В этой задаче не будет идти речь о Бердяндии, о дорогах или авиарейсах. Здесь не будет надоевших монет. Речь пойдет о простой квадратной матрице.

В квадратную матрицу A порядка n были вписаны числа от 1 до n2, каждое по одному разу. Затем для каждого числа была записана пара чисел topi,j и lefti,j, где topi,j это количество чисел в столбце j стоящих выше числа Ai,j и одновременно больших него, а lefti,j это количество чисел в строке i стоящих левее числа Ai,j и одновременно больших него.

Вам заданы матрица top и left. Ваша задача состоит в нахождении возможной матрицы A, соответствующей входным данным.

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

В первой строке входного файла записано целое число n (1 ≤ n ≤ 600), где n это порядок искомой матрицы. Далее во входном файле записана пара матриц top и left, в виде n строк по n чисел в каждой строке. Матрицы разделены пустой строкой.

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

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

Примеры
Входные данные
3
0 0 0
0 0 0
0 0 2

0 0 0
0 1 0
0 1 2
Выходные данные
1 2 6
5 3 7
9 8 4
#2866
Волки и овцы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Пастбища Берляндии в опасности. Волки напали на пастбище овец. Пастух решил застрелить всех волков, при этом не убив ни одной овцы. Ружье заряжено бронебойными патронами, поэтому пули пролетают насквозь. Овцы и волки представлены отрезками. Пастух находится в точке (0, 0). Траектория полета пули — луч, выходящий из точки (0, 0). Если траектория пули имеет общуюточку с отрезком, характеризующим животное, то животное умирает. Найдите наименьшее количество выстрелов, необходимое для убийства всех волков. Овцы при этом должны остаться живы.

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

В первой строке записаны два целых числа N и M (0 ≤ N ≤ 100000, 0 ≤ M ≤ 100000) — количество волков и овец соответственно. Далее следует N+M строк. В каждой строке записано четыре числа X1, Y1, X2, Y2 (−1000 ≤ X1, X2 ≤ 1000, 1 ≤ Y1, Y2 ≤ 1000), описывающие отрезки. Первые N отрезков описывают положение волков, следующие M строк положение овец.

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

Выведите наименьшее количество выстрелов, необходимое для убийства всех волков. Если невозможно убить всех волков, сохранив овец живыми, то выведите “No solution”.

Примеры
Входные данные
1 1
5 5 6 7
3 5 8 5
Выходные данные
No solution
Входные данные
2 1
1 1 2 3
-5 4 2 2
999 1000 1000 999
Выходные данные
1
Страница: << 275 276 277 278 279 280 281 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест