Темы --> Информатика --> Алгоритмы --> Алгоритмы сортировки --> Быстрая сортировка
---> 22 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 1 2 3 4 5 >> Отображать по:
#1344
Многоугольники
  
ограничение по времени на тест
0.1 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано такое множество из N многоугольников, что выполняются следующие условия:

  • никакие два многоугольника не имеют общих точек;
  • для каждого i –го многоугольника существует Pi многоугольников, внутри которых он находится, и N-1-Pi многоугольников, которые находятся внутри его, 0 ≤Pi≤N-1.

Напишите программу, которая для каждого многоугольника выдает количество многоугольников, внутри которых он находится.

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

Первая строка входного файла содержит целое число N — количество многоугольников, 3≤N≤100000. Следующие N строк файла описывают N многоугольников. (i+1)–ая строка файла описывает i–ый многоугольник. Первое целое число Ci — количество вершин многоугольника, 3≤Ci≤20. Последующие Ci пар чисел — координаты вершин многоугольника в порядке его обхода. Координаты вершин — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.

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

Единственная строка выходного файла должна содержать N чисел: i–ое число строки должно быть Pi — количество многоугольников, внутри которых находится i–ый многоугольник.

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

Помимо открыток Петя и Вася решили устроить одноклассницам чаепитие и заразили своей идеей еще K–2 своих друзей. Они собрались вместе и выбрали в одном довольно известном супермаркете P тортиков. Настал черед рассчитываться за них.

В магазине есть N работающих касс, занумерованных числами от 1 до N. Про i-ю кассу известно, что кассиру требуется Ai единиц времени на обработку одного товара и Bi единиц времени для того, чтобы рассчитаться с покупателем. Обойдя все кассы, школьники посчитали, что на обслуживание покупателей, уже стоящих в i-ю кассу, уйдет Ti единиц времени.

Теперь Петя и Вася задались вопросом, в какие кассы надо встать им и их друзьям (в каждую из выбранных касс должен стоять хотя бы один из них, и каждый из них может стоять не более, чем в одну кассу, поэтому суммарно они могут стоять не более чем в K касс) и сколько тортиков каждый должен взять, чтобы последний из них вышел из магазина как можно раньше. Некоторые из ребят могут в кассу не стоять, а, отдав все тортики другим, выйти через специальный выход для тех, кто ничего не купил.

Напишите программу, которая определит это минимальное время.

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

В первой строке записано одно число N — количество касс в супермаркете (1 ≤ N ≤ 100000). В следующих N строках записано по три числа Ai, Bi, Ti (0 ≤ Ai, Bi, Ti ≤ 100000). В последней строке записаны два числа — K и P — число школьников и покупок у них соответственно (0 ≤ P ≤ 100000, 2 ≤ K ≤ 100000).

Все числа во входном файле целые.

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

Выведите минимальное время выхода последнего школьника из магазина.

Комментарии к примерам тестов

Здесь лучше всего встать в обе кассы и купить там по одному тортику.

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

Частичные ограничения

Первая группа состоит из тестов, в которых N ≤ 10 и оценивается в 30 баллов.

Вторая группа состоит из тестов, в которых N ≤ K ≤ 100000 и оценивается в 30 баллов.

Третья группа состоит из тестов без дополнительного ограничения и оценивается в 40 баллов.

Примеры
Входные данные
2
100 10 40
10 100 50
2 2
Выходные данные
160
Входные данные
3 
1 2 0
5 2 1
2 10 1
3 5
Выходные данные
7
#2531
Москва — Ханты-Мансийск
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Есть \(n\) человек, которые хотят улететь из Москвы в Ханты-Мансийск. Каждый день летает один самолёт вместимостью \(k\) человек. У каждого человека есть множество дней, когда он может улететь, — отрезок \([a_i,b_i]\). Нужно придумать такое распределение людей по самолётам, что до Ханты-Мансийска долетит максимальное число людей. Среди людей есть участники РОИ, которых нужно перевезти обязательно (остальных людей будем называть обычными).

В связи с проведением в Ханты-Мансийске Всероссийской олимпиады школьников по информатике агентство авиаперевозок обязано перевезти самолётами всех участников олимпиады. Всего за \(m\) дней, пронумерованных от 1 до \(m\), из Москвы в Ханты-Мансийск хотят вылететь \(n\) пассажиров, в том числе и участники олимпиады.

Все желающие вылететь в Ханты-Мансийск заполнили анкеты, в которых указали информацию о возможных днях вылета и об участии в олимпиаде. Информация о возможных днях вылета \(i\)-го пассажира указана в виде пары чисел \((a_i, b_i)\). Это означает, что пассажир согласен вылететь в любой день, начиная с \(a_i\) и по \(b_i\) включительно, и не может вылететь в другие дни.

Самолёт из Москвы в Ханты-Мансийск вылетает всего один раз в день и вмещает не более \(k\) пассажиров. Необходимо распределить пассажиров по дням вылета таким образом, чтобы улетело как можно большее количество пассажиров, при этом все участники Всероссийской олимпиады должны улететь обязательно.

Напишите программу, определяющую распределение пассажиров по дням вылета, при котором максимизируется количество перевезённых пассажиров, или определяющую, что такого распределения не существует.

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

В первой строке входного файла записаны три натуральных числа — \(n\), \(m\) и \(k\) (\(1\le n\le100\,000\), \(1\le m\le100\,000\), \(1\le k\le100\,000\)). Далее следуют \(n\) строк, \(i\)-я из которых содержит результаты заполнения анкеты пассажиром с порядковым номером \(i\) в виде трёх целых чисел, первые два из которых — самый ранний и самый поздний дни вылета \(a_i\) и \(b_i\) (\(1\le a_i\le b_i\le m\)), а последнее число равно 0, если пассажир не является участником Всероссийской олимпиады, и равно 1, если является. Гарантируется, что хотя бы один пассажир является участником Всероссийской олимпиады. Числа в каждой строке разделены пробелами.

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

В первой строке выходного файла выведите максимальное количество пассажиров \(l\), которых можно перевезти из Москвы в Ханты-Мансийск. Если невозможно выполнить поставленную задачу, то в первой строке необходимо вывести число 0. В случае положительного ответа выведите во второй строке n чисел, а именно, для каждого пассажира выведите номер дня, в который запланирован его вылет, либо 0, если этому пассажиру не нашлось места в оптимальном распределении. Числа во второй строке разделяйте пробелами. Если оптимальных распределений несколько, выведите любое из них.

Система оценивания

  • Решения, корректно работающие при \(n\), \(m\) и \(k\), не превышающих 10, будут оцениваться из 20 баллов.
  • Решения, корректно работающие при \(n\), \(m\) и \(k\), не превышающих 100, будут оцениваться из 40 баллов.
  • Решения, корректно работающие при \(n\), \(m\) и \(k\), не превышающих 1 000, будут оцениваться из 60 баллов.
  • Решения, корректно работающие при \(n\), \(m\) и \(k\), не превышающих 10 000, будут оцениваться из 80 баллов.

    • Примеры
    Входные данные
    3 2 1
1 2 1
1 2 0
1 2 1
    Выходные данные
    2
1 0 2
    Входные данные
    3 4 1
1 2 1
1 3 1
1 4 0
    Выходные данные
    3
1 2 3
    Входные данные
    10 4 2
2 3 0
2 3 0
1 3 1
3 4 0
3 4 1
2 3 0
2 2 0
1 3 1
4 4 0
2 4 0
    Выходные данные
    8
2 3 1 4 4 3 2 1 0 0
    #3142
    Автозаправки
      

    Фирма «АйОйЛ» построила на скоростном шоссе Москва-Тверь N автозаправок. Каждая автозаправка имеет свой номер, который присваивался ей при строительстве, начиная с единицы. Кроме того, каждая автозаправка располагается на определенном километре шоссе. Километры на шоссе нумеруются от 0, начиная от Москвы.

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

    Требуется написать программу, которая находит автозаправку, которую можно сократить.

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

    Первая строка входного файла содержит количество автозаправок N (2 ≤ N ≤ 105). Вторая строка входного файла содержит N различных целых чисел xi – километр, на котором расположена автозаправка с номером i (1 ≤ i ≤ N). Числа в строке разделены пробелом. Значения всех xi не меньше ноля и не  превосходят 109 по абсолютной величине.

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

    В первой строке выходного файла необходимо вывести номер автозаправки, которую можно сократить. Если ответов несколько, выведите любой из них.

    Ввод
    Вывод
    5
    10 3 7 2 5
    4
    #3334
    Проходной балл
      

    Одна Очень Престижная Олимпиада, как и все престижные олимпиады в последнее время, состоит из двух туров - регионального и заключительного. Правила отбора во второй тур (заключительный этап) просты:

    1. Призеры олимпиады прошлого года приглашаются на заключительный этап вне зависимости от набранных ими в первом туре баллов.
    2. Все участники, набравшие не меньше баллов, чем установленный жюри проходной балл, проходят во второй тур.
    3. Если в каком-либо из регионов ни один участник по первым двум правилам во второй тур не прошел, то на заключительный этап приглашается участник из этого региона, набравший в нем максимальное количество баллов (это не касается регионов, от которых участников не было).
    4. На второй тур можно пригласить не более \(M\) участников.

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

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

    В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(R\) - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники (\(1 \le M < N\)). Далее в \(N\) строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет \(id\) - уникальный идентификатор участника (\(1 \le id \le N\)), далее номер региона \(region\), в котором данный участник учится (\(1 \le region \le R\)), затем \(score\) - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.

    Гарантируется, что все идентификаторы участников различны, никакие два участника не набрали одинаковое число баллов, и выполнить все правила отбора возможно.

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

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

    Примечания

    Тесты состоят из четырёх групп. Во всех тестах \(0 \le score \le 10^9\).

    1. Тест 1 из условия, оценивается в 0 баллов.
    2. В тестах этой группы все числа на входе не превосходят 1000. Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
    3. В тестах этой группы \(1 \le R \le M \le 10\,000\), \(M < N \le 100\,000\). Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
    4. В тестах этой группы, \(1 \le R \le M < N \le 100\,000\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый из тестов оценивается независимо от других.
    Примеры
    Входные данные
    9 6 5
6 1 799 0
2 4 995 0
1 4 989 1
7 2 538 0
5 4 984 0
8 2 1000 0
3 2 998 0
4 2 823 1
9 1 543 0
    Выходные данные
    985
    Страница: << 1 2 3 4 5 >> Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест