Страница: << 60 61 62 63 64 65 66 >> Отображать по:
#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
#112561
Весы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

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

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

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

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

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

Примеры
Входные данные
1 5
Выходные данные
1
Входные данные
5 7
Выходные данные
4
#112598
Два пути
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Как вы знаете, Васин брат живет во Флатландии. Во Флатландии n городов, соединенных n - 1 двухсторонней дорогой. Города пронумерованы от 1 до n . Из любого города можно добраться до любого другого.

Компания «Два пути», в которой работает Васин брат, выиграла тендер на ремонт двух путей во Флатландии. Путем называется последовательность различных городов, последовательно соединенных дорогами. Пути, которые надо отремонтировать, компания может выбрать самостоятельно. Единственное условие, накладываемое тендером, они не должны пересекаться (то есть иметь общих городов).

Известно, что прибыль, которую получит компания «Два пути», равна произведению длин выбранных двух путей. Считая длину каждой дороги один, а длину пути равной количеству дорог в ней, найдите максимальную возможную прибыль.

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

В первой строке записано целое число n (2 ≤ n ≤ 100 000) , где n количество городов в стране. Далее в n - 1 строке записаны сами дороги. Каждая строка содержит пару номеров соединяемых дорогами a i , b i (1 ≤ a i , b i ≤ n )

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

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

Примеры
Входные данные
4
1 2
2 3
3 4
Выходные данные
1
Входные данные
7
1 2
1 3
1 4
1 5
1 6
1 7
Выходные данные
0
Входные данные
6
1 2
2 3
2 4
5 4
6 4
Выходные данные
4
#112603
Кузнечик-K
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.

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

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 32 .

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

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

Примеры
Входные данные
5 4
Выходные данные
8
#112605
Кузнечик и лягушки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.

На некоторых столбиках сидят лягушки, которые едят кузнечиков (Кузнечик не должен попадать на эти столбики!). Определите, сколькими способами Кузнечик может безопасно добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.

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

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 32 . Во второй строке записано число лягушек L ( 0 ≤ L ≤ N - 2 ). В третьей строка записано L натуральных чисел: номера столбиков, на которых сидят лягушки (среди них нет столбиков с номерами 1 и N ).

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

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

Примеры
Входные данные
6 4
2
2 4
Выходные данные
3
Страница: << 60 61 62 63 64 65 66 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест