Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 241 242 243 244 245 246 247 >> Отображать по:
#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
#3720
11B: пусти козла в огород - 2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Козла пустили в квадратный огород и привязали к колышку. Колышек воткнули точно в центре огорода. Козёл голоден, как волк, прожорлив, как бык, и ест всё, до чего дотянется, не перелезая через забор и не разрывая веревку. Какая площадь огорода будет объедена?

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

Длина стороны огорода и длина верёвки в метрах (положительные целые числа, не превосходящие 100, расположенные в одной строке через пробел).

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

Площадь части огорода (в квадратных метрах, с точностью до 6 знаков после десятичной точки), объеденной козлом.

Примеры
Входные данные
10 6
Выходные данные
95.091113079
#3721
Кассы
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

На одном из московских вокзалов билеты продают \(N\) касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.

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

Сначала вводится одно целое число \(N\) \((0 < N \le 10000)\).

В каждой из следующих \(N\) строк через пробел расположены 6 целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от 0 до 23, минуты и секунды — целые числа от 0 до 59), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.

Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с 10 ч 30 мин 30 с до 10 ч 35 мин 30 с, ежесуточно работает 300 секунд.

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

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

Требуется вывести одно число — суммарное время за сутки (в секундах), на протяжении которого работают все \(N\) касс.

Примеры
Входные данные
3
1 0 0 23 0 0
12 0 0 12 0 0
22 0 0 2 0 0
Выходные данные
7200
Входные данные
2
9 30 0 14 0 0
14 15 0 21 0 0
Выходные данные
0
Входные данные
2
14 0 0 18 0 0
10 0 0 14 0 1
Выходные данные
1
#3722
Корень кубического уравнения
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано кубическое уравнение \(ax^3 + bx^2 + cx + d = 0 \;(a \ne 0)\). Известно, что у этого уравнения ровно один корень. Требуется его найти.

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

Во входных данных через пробел записаны четыре целых числа: \(-1000 \le a,\,b,\,c,\,d \le 1000\).

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

Выведите единственный корень уравнения с точностью не менее 4 знаков после десятичной точки.

Примеры
Входные данные
1 -3 3 -1
Выходные данные
0.999999598818135
Входные данные
-1 -6 -12 -7
Выходные данные
-0.999999999990564
Страница: << 241 242 243 244 245 246 247 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест