Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Интернет-олимпиады
    Google Code Jam(2 задач)
Страница: 1 Отображать по:
#112559
Up and Down
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
3
1 2 3
Выходные данные
0
Входные данные
5
1 8 10 3 7
Выходные данные
1
#112573
Data Packing
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

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

Есть два важных правила хранения данных на дисках: Адам никогда не хранит более двух файлов на одном диске (это нужно, чтоб ему было проще их подписывать), он никогда не делит файл на части. Но диски достаточно большие, чтобы уместить любой файл.

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

1 ≤ T ≤ 100. 1 ≤ X ≤ 700. 1 ≤ S i ≤ X .

В задаче есть две группы тестов: 1. 1 ≤ N ≤ 10 - оценивается в 40 баллов 2. 1 ≤ N ≤ 1 4 - оценивается в 60 баллов

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

Первая строка входного файла содержит число N - количество файлов и X - ёмкость одного диска. Во второй строке дано N чисел S i - размеры файлов.

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

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

Примеры
Входные данные
3 100
10 20 70
Выходные данные
2
Входные данные
4 100
30 40 60 70
Выходные данные
2
Входные данные
5 100
10 20 30 40 60
Выходные данные
3
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест