Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 221 222 223 224 225 226 227 >> Отображать по:
#3336
Волейбол
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В одной Очень Известной Летней Школе наиболее популярным видом спорта является волейбол. Для каждого из \(N\) школьников известно его умение играть в волейбол. Перед началом занятий школьников необходимо распределить между двумя тренерами.

Тренеры сочли справедливым следующий алгоритм разделения на две группы. Сначала они выбирают два целых числа \(p\), \(q\) (\(0 < p \le q \le N\)). Затем первый берет себе \(p\) лучших школьников, после чего оба тренера, начиная со второго, берут по очереди по \(q\) лучших школьников из оставшихся, пока их количество не меньше \(q\). В конце очередной тренер просто берет всех оставшихся.

Оба тренера заинтересованы в наиболее справедливом распределении школьников между группами. Поэтому они стремятся найти такие \(p\) и \(q\), чтобы разница суммарных умений между двумя группами школьников оказалась минимальной. При этом, вообще говоря, не обязательно, чтобы количество школьников в каждой из групп было одинаковым.

Помогите тренерам подобрать такие "справедливые" значения \(p\) и \(q\) (\(0 < p \le q \le N\)), при которых разница в суммарных умениях образованных групп школьников по абсолютной величине будет минимальна.

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

В первой строке входного файла записано единственное целое число \(N\). Во второй строке содержатся \(N\) неотрицательных целых чисел, не превосходящих \(10^9\) - умения школьников играть в волейбол.

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

Выведите искомые целые значения \(p\) и \(q\) (\(0 < p \le q \le N\)). Если искомых пар несколько, то выведите любую из них.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. В тестах этой группы \(2 \le N \le 300\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(2 \le N \le 2\,000\). Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
  4. Offline-группа, \(1 \le N \le 100\,000\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Тесты этой группы оцениваются независимо друг от друга.

Примеры
Входные данные
8
5 3 3 3 3 3 7 1
Выходные данные
1 2
#3337
Забор
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Чтобы куски метеорита не были испорчены любопытными туристами, для проведения научных исследований решили построить один забор, которым огородить не менее \(K\) кусков метеорита. Естественно, что забор должен быть минимально возможной длины, и внутри него должны оказаться любые \(K\) (или больше) кусков метеорита (кусок считается лежащим внутри забора как когда он лежит строго внутри, так и когда забор проходит непосредственно через него).

Конечно, ученые хотят огородить как можно больше кусков, но как всегда, все упирается в деньги. Главный бухгалтер решил составить такую таблицу: для каждого \(K\) от 1 до \(N\) определить, какой минимальной длины нужно построить забор, чтобы внутри него оказалось не менее \(K\) кусков метеорита. Помогите ему.

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

В первой строке входного файла записано единственное целое число \(N\). В каждой из следующих \(N\) строк записано по паре целых чисел, по модулю не превосходящих \(1\,000\) - координаты точек, куда упали куски метеорита. Никакие два куска не упали в одну и ту же точку.

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

Выведите \(N\) чисел, \(i\)-е (\(1 \le i \le N\)) должно быть равно минимальной длине забора, внутри которого окажется не менее \(K\) кусков метеорита. Выведенный ответ будет сравниваться с правильным с точностью до \(10^{-6}\).

Примечания

Тесты состоят из четырёх групп.

  1. Тесты 1--2, из условия, оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N \le 16\). Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le N \le 30\). Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Offline-группа. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Тесты объединяются в подгруппы, каждая из которых оценивается в 10 баллов, баллы за каждую подгруппу начисляются только при прохождении всех тестов подгруппы. Подгруппы соответствуют ограничениям \(N \le 40\), \(N \le 60\), \(N \le 80\), \(N \le 100\).

Примеры
Входные данные
4
0 0
0 1
1 0
1 1
Выходные данные
0.000000000
2.000000000
3.414213562
4.000000000
Входные данные
3
1 1
0 0
2 0
Выходные данные
0.000000000
2.828427125
4.828427125
#3338
Наименьшее общее кратное (BCD)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Найдите наименьшее общее кратное всех целых чисел от \(1\) до \(N\). Наименьшим общим кратным натуральных чисел \(a_1\),\(a_2\),…,\(a_k\) называется число \(A\), такое что \(А\) делится на \(a_i\) для всех \(i\) от \(1\) до \(k\), причем \(A\) – наименьшее натуральное число, обладающее этим свойством.

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

Одно целое число (\(1 \leq N \leq 1000\)).

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

Выведите одно целое число – наименьшее общее кратное всех чисел от \(1\) до \(N\).

Примеры
Входные данные
3
Выходные данные
6
#3339
Сортировка (D)
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дана последовательность целых чисел из диапазона [-2147483648, 2147483647]. Вам поручается отсортировать эту последовательность и удалить из нее все повторения элементов, т. е. необходимо удалить все кроме одной копии числа в последовательности.

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

В первой строке входного файла находится целое число \(N\) – количество чисел в последовательности (\(1 \leq N \leq 65536\)). Последующие \(N\) строк содержат \(N\) целых чисел (по одному числу в строке).

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

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

Примеры
Входные данные
6
8
8
7
3
7
7
Выходные данные
8
7
3
#3340
Площадь (C)
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Подсчитайте площадь заданного многоугольника.

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

В первой строке входного файла находится число \(N\) (\(3 \leq N \leq 50000\)) – количество вершин многоугольника. Последующие \(N\) строк содержат по 2 целых числа \(x\) и \(y\) (\(-10000 \leq x,y \leq 10000\)) – координаты вершин.

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

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

Примеры тестов

Входные данные
3
0 0
1 0
0 1
Выходные данные
0.500000000000000...000

Выходной файл содержит 600 нулей.

Страница: << 221 222 223 224 225 226 227 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест