Страница: << 31 32 33 34 35 36 37 >> Отображать по:

#112559

Up and Down

Темы: [Динамическое программирование по подстрокам] [Жадный алгоритм]

Источники: [ Личные олимпиады, Интернет-олимпиады, Google Code Jam, Up and Down ]

Дана последовательность попарно различных чисел A = [ A ₁ , A ₂ , ..., A _N ] , требуется переставить числа так, чтобы было верно A ₁ < A ₂ < ... < A _m > A _{m

+ 1} > ... > A _N (где m лежит между 1 и N включительно) Переставлять можно только пары соседних чисел, требуется минимизировать количество обменов.

1 ≤ A _i ≤ 10 ⁹ 1 ≤ N ≤ 1000 A _i попарно различны.

В задаче есть две группы тестов:

1. 1 ≤ N ≤ 10 - оценивается в 35 баллов

2. 1 ≤ N ≤ 1000 - оценивается в 65 баллов

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

В первой строке число N . Вторая строка содержит N чисел: A ₁ , ..., A _N .

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

Выведите одно число - минимальное количество обменов

Примеры
Входные данные
3 1 2 3
Выходные данные
0
Входные данные
5 1 8 10 3 7
Выходные данные
1

#112561

Весы


Темы: [Задача о рюкзаке]

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

Если в продаже нет стандартного набора гирь, измерение массы становится большой проблемой. Ваш набор содержит n гирь массой 1 грамм, 4 грамма, 16 грамм, ..., 4 ^{n

- 1} грамм. Кроме того, у вас есть две чаши весов. Чтобы взвесить объект, надо положить его на левую чашу весов и поставить некоторые гири на левую и правую чашу для достижения равновесия. Требуется найти, сколько целых масс в диапазоне [1; m ] возможно измерить, используя весы и данный набор гирь.

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

В единственной строке содержаться 2 целых числа m и n (1 ≤ n , m ≤ 10 ⁹ ) .

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

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

Примеры
Входные данные
1 5
Выходные данные
1
Входные данные
5 7
Выходные данные
4

#113104

Расстояние Дамерау-Левенштейна


Темы: [Динамическое программирование: последовательности]

ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Одной из наиболее распространенных опечаток при наборе текста является перестановка двух соседних символов, например, вместо слова «программа» набрано слово «прогармма». Расстояние Левенштейна не учитывает такие опечатки: при вычислении расстояния Левенштейна одна перестановка будет считаться за два редактирования (например, удаление и вставка символа).

При вычислении расстояния Дамерау-Левенштейна, помимо операций замены, вставки и удаления символа допускается еще операция перестановки двух соседних символов. При этом между переставленными символами нельзя вставлять другие символы.

Определите расстояние Дамерау-Левенштейна для двух данных строк.

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

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

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

Требуется вывести одно число – расстояние Дамерау-Левенштейна для данных строк.

Примеры
Входные данные
XABCDE ACBYDF
Выходные данные
4

#113283

Sparse table для суммы


Темы: [Динамическое программирование на таблицах] [Дерево отрезков, RSQ, RMQ]

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан трёхмерный массив. Найдите сумму на параллелепипеде со сторонами, паралельными осям координат.

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

В первой строке даны три числа: 1 ≤ N , M , K ≤ 100 . В следующих N × M строках даны по K чисел - | a _ijk | < 10⁹ . Далее в отдельной строке даётся одно число Q ≤ 10⁵ - количество запросов. В следующих Q строках даются запросы: каждый запрос имеет вид x₁y₁z₁ x₂y₂z₂- две противоположные границы параллелепипеда, сумму которого необходимо подсчитать. 1 ≤ x ₁ ≤ x ₂ ≤ N 1 ≤ y ₁ ≤ y ₂ ≤ M 1 ≤ z ₁ ≤ z ₂ ≤ K

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

Для каждого запроса выведите одно число в отдельной строке - ответ на этот самый запрос

Примеры
Входные данные
3 3 3 2 3 5 1 2 3 4 5 7 1 6 6 9 6 6 8 6 6 4 3 3 2 3 3 5 3 3 1 2 1 2 3 3 3
Выходные данные
54

#113467

Распродажа


Темы: [Сортировка событий] [Дерево отрезков, RSQ, RMQ] [Динамическое программирование: два параметра] [Битовые операции] [Задача о рюкзаке]

ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c _i , время его завоза в магазин a _i и время его вывоза из магазина b _i .

У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m _j , время s _j , которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k _j , которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k _j , при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.

Помогите Иннокентию определить, какие из его планов можно выполнить.

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

В первой строке входных данных содержится число N — общее количество товаров в магазине ( 1 ≤ N ≤ 500 ). Далее содержатся описания товаров, каждый товар описывается тремя целыми числами c _i , a _i , b _i , обозначающими стоимость товара, время его завоза и время его вывоза из магазина ( 1 ≤ c _i ≤ 1 000 , 1 ≤ a _i < b _i ≤ 10 ⁹ ).

Далее содержится число M — количество планов Иннокентия ( 1 ≤ M ≤ 500 000 ). Каждый план описывается тремя целыми числами m _j , k _j , s _j , обозначающими время прихода Иннокентия в магазин, сумму денег, которую он готов потратить в этом плане и длительность его пребывания в магазине ( 1 ≤ m _j ≤ 10 ⁹ , 1 ≤ k _j ≤ 100 000 , 0 ≤ s _j ≤ 10 ⁹ ).

Помните, что это только планы, т. е. ситуация в магазине не меняется вне зависимости от того, может ли Иннокентий осуществить план или нет.

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

Для каждого плана в отдельной строке выведите « YES », если Иннокентий может его осуществить, и « NO » в противном случае.

Примечание

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

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

Тесты 2–7. В тестах этой группы M ≤ 10 , a _i , b _i , m _j , s _j ≤ 20 000 , k _j ≤ 1 000 . Эта группа оценивается в 30 баллов.

Тесты 8–11. В тестах этой группы N ≤ 200 , M ≤ 200 , k _j ≤ 5 000 . Эта группа оценивается в 30 баллов.

Тесты 12–23. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.

Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.

Примеры
Входные данные
5 6 2 7 5 4 9 1 2 4 2 5 8 1 3 9 5 2 7 1 2 7 2 3 2 0 5 7 2 4 1 5
Выходные данные
YES NO YES YES NO

Страница: << 31 32 33 34 35 36 37 >> Отображать по:

Выбрано
:
Отменить
|
Добавить в контест