Темы --> Информатика --> Алгоритмы --> Алгоритмы сортировки
    Квадратичные сортировки(24 задач)
    Сортировка записей(9 задач)
    Использование сортировки(13 задач)
    Быстрая сортировка(55 задач)
    Сортировка слиянием(9 задач)
    Сортировка подсчетом(27 задач)
    Сканирующая прямая(39 задач)
    Сортировка событий(4 задач)
---> 194 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 24 25 26 27 28 29 30 >> Отображать по:
#3354
Круг из прямоугольников
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
6 megabytes

Плоскость разбили на одинаковые прямоугольники размера \(M\times N\) со сторонами, параллельными осям координат, и вершинами, расположенными в точках (\(M\times i, N\times j\)), где \(i\) и \(j\) пробегают всевозможные целые числа. Пусть на этой плоскости задана точка \(P(x,y)\) с целочисленными координатами. Назовем расстоянием от точки \(P\) до некоторого прямоугольника наименьшее из расстояний от \(P\) до точек этого прямоугольника, включая его границу. В частности, расстояние от точки до прямоугольника, в котором она содержится, равно 0.
Требуется написать программу, перечисляющую прямоугольники, удаленные от \(P\) на расстояние, не превосходящее \(L\). Прямоугольники должны быть перечислены в порядке неубывания этого расстояния.

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

Во входном файле содержатся целые числа \(M\), \(N\), \(L\), \(x\) и \(y\) (\(1 \leq M\leq 10\), \(1 \leq N\leq 10\), \(0\leq L\leq 1000\), \(–30000 \leq x,y \leq 30000\)), разделенные пробелами и/или переводами строк.

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

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

Примеры
Входные данные
3 2 2
4 3
Выходные данные
7
#3356
Минимальное покрытие
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На прямой задано некоторое множество отрезков с целочисленными координатами концов [\(L_i\), \(R_i\)]. Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок [0, \(M\)], (\(M\) — натуральное число), содержащее наименьшее число отрезков.

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

В первой строке указана константа \(M\) (\(1 \leq M \leq 5000\)). В каждой последующей строке записана пара чисел \(L_i\) и \(R_i\) (\(|L_i|, |R_i| \leq 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.

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

В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка [0; \(M\)]. Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка [0, \(M\)] исходным множеством отрезков [\(L_i\), \(R_i\)] невозможно, то следует вывести единственную фразу “No solution”.

Примеры
Входные данные
1
-1 0
-5 -3
2 5
0 0
Выходные данные
No solution
Входные данные
1
-1 0
0 1
0 0
Выходные данные
1
0 1
#3391
Обратная задача для RMQ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Обратные задачи представляют собой быстро развивающуюся область информатики. В отличии от классической постановки задачи, где по заданным исходным данным \(D\) требуется решить некоторую оптимизационную задачу \(P\), в обратной задаче по заданной задаче \(P\) и результату вычисления \(R\) требуется подобрать исходные данные \(D\), на которых достигается этот результат. В этой задаче вам предлагается решить обратную задачу к задаче о минимуме на отрезке (range minimum query, RMQ).
Пусть задан массив \(a[1..n]\). Ответ на запрос о минимуме на отрезке \(Q(i, j)\) — это минимальное среди значений \(a[i]\), ..., \(a[j]\). Вам дано \(n\) и последовательность запросов о минимуме на отрезке с ответами. Восстановите исходный массив \(a\).

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

Первая строка входного файла содержит \(n\) — размер массива, и \(m\) — количество запросов (\(1 \leq n, m \leq 100000\)). Следующие \(m\) строк содержат по три целых числа: числа \(i\), \(j\) и \(q\) означают, что \(Q(i, j) = q\) (\(1 \leq i \leq j \leq n\), \(-2^{31} \leq q \leq 2^{31} - 1\)).

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

Если входные данные несовместны, то есть искомого массива a не существует, выведите "inconsistent" на первой строке выходного файла.
В противном случае выведите “consistent” на первой строке выходного файла. Вторая строка должна содержать сам массив. Элементы массива должны быть целыми числами между \(2^{31}\) и \(2^{31}-1\). Если решений несколько, выведите любое.

Примечание

Баллы за эту задачу будут начислены только если решение проходит все тесты

Примеры
Входные данные
3 2
1 2 1
2 3 2
Выходные данные
consistent
1 2 2
Входные данные
3 3
1 2 1
1 1 2
2 3 2
Выходные данные
inconsistent
#3394
Школа олимпийского резерва
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Для подготовки к чемпионату мира по футболу 2018 года создается школа олимпийского резерва. В нее нужно зачислить \(M\) юношей 1994−1996 годов рождения. По результатам тестирования каждому из \(N\) претендентов был выставлен определенный балл, характеризующий его мастерство. Все претенденты набрали различные баллы. В составе школы олимпийского резерва хотелось бы иметь \(A\) учащихся 1994 г.р., \(B\) – 1995 г.р. и \(C\) – 1996 г.р. (\(A + B + C = M\)). При этом минимальный балл зачисленного юноши 1994 г.р. должен быть больше, чем минимальный балл зачисленного 1995 г.р., а минимальный балл зачисленного 1995 г.р. должен быть больше, чем минимальный балл зачисленного 1996 г.р. Все претенденты, набравшие балл больше минимального балла для юношей своего года рождения, также должны быть зачислены.

В базе данных для каждого претендента записаны год его рождения и тестовый балл. Требуется определить, сколько нужно зачислить юношей каждого года рождения \(M_{94}\), \(M_{95}\) и \(M_{96}\) (\(M_{94} + M_{95} + M_{96} = M\)), чтобы значение величины \(F = |M_{94} − A| + |M_{95} − B| + |M_{96} − C|\) было минимально, все правила, касающиеся минимальных баллов зачисленных, были соблюдены, и должен быть зачислен хотя бы один юноша каждого требуемого года рождения.

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

В первой строке входного файла находится число \(K\) – количество наборов входных данных. Далее следуют описания каждого из наборов. В начале каждого набора расположены три натуральных числа \(A\), \(B\), \(C\). Во второй строке описания находится число \(N\) – количество претендентов (гарантируется, что \(N \geq A + B + C\)). В каждой из следующих \(N\) строк набора содержатся два натуральных числа – год рождения (число 1994, 1995 или 1996 соответственно) и тестовый балл очередного претендента.

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

Ответ на каждый тестовый набор выводится в отдельной строке. Если хотя бы одно из требований выполнить невозможно, то в качестве ответа следует вывести только число −1. В противном случае соответствующая строка сначала должна содержать минимальное значение величины \(F\), а затем три числа \(M_{94}\), \(M_{95}\) и \(M_{96}\), на которых это минимальное значение достигается, удовлетворяющие всем требованиям отбора. Если искомых вариантов несколько, то разрешается выводить любой из них.

Комментарий

В первом примере на первом наборе ответ не существует, потому что нельзя пригласить хотя бы одного юношу 1995 г.р. Во втором наборе ответ существует и единственный, в третьем – нельзя выполнить правило относительно минимальных баллов.

Во втором примере правильным является также ответ 2 2 2 2.

Подзадачи и система оценки

Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Подзадача 1 (25 баллов)

\(K = 1\); \(N \leq 100\); каждый претендент характеризуется своим баллом от 1 до \(N\).

Подзадача 2 (25 баллов)

Сумма значений \(N\) по всем тестовым наборам не превосходит 10 000, каждый претендент характеризуется своим баллом от 1 до \(10^9\).

Подзадача 3 (25 баллов)

Сумма значений \(N\) по всем тестовым наборам не превосходит 100 000, каждый претендент характеризуется своим баллом от 1 до \(N\).

Подзадача 4 (25 баллов)

Сумма значений \(N\) по всем тестовым наборам не превосходит 300 000, каждый претендент характеризуется своим баллом в диапазоне от 1 до \(10^9\).

Примеры
Входные данные
3
1 1 1
4
1994 3
1994 4
1996 1
1996 2
1 1 1
3
1995 2
1994 3
1996 1
1 1 1
3
1994 1
1995 2
1996 3
Выходные данные
-1
0 1 1 1
-1
Входные данные
1
2 3 1
7
1996 2
1994 7
1994 4
1996 1
1995 3
1994 5
1995 6
Выходные данные
2 3 2 1
#3561
День рождения
  
Источники: [ Командные олимпиады, ВКОШП, 2010, Задача F ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за \(S\) рублей!

Конечно, скидываться придется всем поровну. То есть, если Коля позовет \(k\) своих друзей, то каждому придется заплатить \(S/(k + 1)\) рублей (да, сам Коля тоже должен внести свою долю). При этом \(S\) не обязательно должно делиться на \(k + 1\): главное — купить билет, а между собой друзья уж как-нибудь договорятся.

Всего у Коли \(n\) друзей, при этом \(i\)-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше \(b_i\) (больше денег у него просто с собой нет) и не меньше \(a_i\) (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).

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

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

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

В первой строке входного файлы содержится два целых числа: \(n\) и \(S\) (\(1 \le n \le 100\,000\), \(0 \le S \le 10^9\)) — количество друзей Коли и стоимость билета. В следующих \(n\) строках содержится по три целых числа: в \(i\)-й из этих строк находятся числа \(a_i\), \(b_i\) и \(f_i\) (\(0 \le a_i \le b_i \le S\), \(0 \le f_i \le 10^9\)). Они означают, что \(i\)-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между \(a_i\) и \(b_i\), и он произведет \(f_i\) веселья.

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

В первой строке выходного файла выведите два числа: \(k\) (количество приглашенных на вечеринку друзей) и \(F\) (максимальное суммарное веселье, которое можно получить). Во второй строке выведите \(k\) чисел — номера друзей, которых нужно пригласить.

Страница: << 24 25 26 27 28 29 30 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест