Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 70 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 6 7 8 9 10 11 12 >> Отображать по:
#111226
Театр начинается с актеров
  
Темы: [Хеш]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Участники олимпиады пришли в казанский театр на спектакль, где играют N неизвестных для них актеров. В фойе театра висят портреты всех актеров труппы, которая в полном составе задействована в спектакле. Портреты не подписаны. Зрителям раздали программки, в которых для каждого действия спектакля приводится список фамилий участвующих в нем актеров, но не указаны их роли. Театрал Виталий решил узнать, как выглядит каждый из актеров, упомянутых в программке. Для этого в антракте после каждого действия он выходил в фойе и сопоставлял портреты с увиденными актерами. Требуется написать программу, которая по заданному числу актеров N и списку фамилий актеров, участвующих в каждом из M действий, определяет номер действия, после которого впервые становится возможным установить соответствие между фамилией актера из программки и его портретом.

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

Первая строка входного файла содержит два натуральных числа N – число актеров и M – количество действий в спектакле (1 < N ≤ 100000, 1 ≤ M ≤ 100 000). В каждой из следующих M строк сначала записано количество актеров Ki, участвующих в i–ом действии (1 ≤ Ki ≤ N, K1 + K2 + ... + KM ≤ 100 000), а затем Ki различных натуральных чисел, не превосходящих N, обозначающих фамилии этих актеров. Соседние числа в каждой строке разделены пробелом.

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

Выходной файл должен содержать одну строку, состоящую из N записанных через пробел чисел. i-е число этой строки – это номер действия, после которого впервые становится возможным установить соответствие между i–м актером и его портретом. Если к концу спектакля установить соответствие между каким-либо актером и его портретом так и не удалось, то соответствующее число в строке должно быть равно нулю.

Примечание

В первом примере три актера участвуют в спектакле с тремя действиями. В первом действии участвуют два актера с номерами 1 и 2. Так как актеров всего трое, то после первого акта становится понятно, какой портрет соответствует актеру с номером 3, поэтому третье число строки выходного файла равно 1. Во втором действии участвуют два актера с номерами 3 и 2. Поскольку только второй актер участвовал и в первом, и во втором действиях, то его портрет можно определить после второго действия. А так как портретов всего три, то после второго действия можно установить, что последний портрет соответствует актеру номер 1. Третье действие на ответ не влияет.

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

  1. (оценивается в 30 баллов) Количество актеров N не превосходит 100, количество действий M не превосходит 100, K1 + K2 + ... + KM ≤ 100.

  2. (оценивается в 30 баллов) Количество актеров N не превосходит 10 000, количество действий M не превосходит 10 000, K1 + K2 + ... + KM ≤ 10 000.

  3. (оценивается в 40 баллов) Количество актеров N не превосходит 100 000, количество действий M не превосходит 100 000, K1 + K2 + ... + KM ≤ 100 000.

Примеры
Входные данные
3 3
2 1 2
2 3 2
2 1 2
Выходные данные
2 2 1
Входные данные
5 3
3 1 2 3
3 2 1 3
2 1 3
Выходные данные
0 3 0 0 0
Входные данные
4 3
1 1
1 3
1 2
Выходные данные
1 3 2 3
#111491
Березовая аллея
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

На краю деревни растет старая березовая аллея. Аллея имеет форму прямой полосы шириной \(W\) метров. Вдоль левой стороны аллеи растет \(N\) берез, а вдоль правой — \(M\) берез, при этом \(i\)-я береза с левой стороны аллеи находится на расстоянии \(a_i\) метров от начала аллеи, а \(j\)-я береза с правой стороны — на расстоянии \(b_j\) метров от начала аллеи.

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

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

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

Первая строка входного файла содержит два разделенных пробелом целых числа: длину ленты \(L\) и ширину аллеи \(W\) (\(1 \leq L \leq 2 \times 10^5\), \(1 \leq W \leq 10^4\)).

Вторая и третья строки описывают березы вдоль левой стороны аллеи. Вторая строка содержит число \(N\) — количество берез (\(1 \leq N \leq 2000\)), а третья строка содержит \(N\) различных целых чисел \(a_1\), \(a_2\), …, \(a_N\) (\(0 \leq a_i \leq 10^5\)), заданных по возрастанию.

Четвертая и пятая строки описывают березы вдоль правой стороны аллеи. Четвертая строка содержит число \(M\) — количество берез (\(1 \leq M \leq 2000\)), а пятая строка содержит \(M\) различных целых чисел \(b_1\), \(b_2\), …, \(b_M\) (\(0 \leq b_i ≤ 10^5\)), заданных по возрастанию.

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

Выходной файл должен содержать одно целое число: максимальное количество берез, которое можно оградить заданной лентой.

Гарантируется, что если максимальное число берез, которое можно оградить лентой длины L, равно X, то нет способа оградить (X + 1) березу лентой длины (L + \(10^{-5}\)).

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

Правильные решения для тестов, в которых 1 ≤ N + M ≤ 50, будут оцениваться из 30 баллов.

Правильные решения для тестов, в которых 1 ≤ N + M ≤ 500, будут оцениваться из 60 баллов.

Примеры
Входные данные
18 4
3
0 3 6
4
0 3 6 10
Выходные данные
5
Входные данные
5 3
1
0
1
0
Выходные данные
0
#111582
Гарри Поттер и Зал Пророчеств
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Отряд Дамблдора готовится к полёту в Отдел Тайн Министерства Магии. Так как на их пути за Пророчеством могут встретиться слуги Волан-де-Морта, Гарри с Невиллом решили потренироваться в дуэльных боях.

Они решили провести \(n\) раундов дуэли, а после каждого раунда выпивать восстанавливающее зелье, чтобы не тратить лишних сил. Всего у ребят \(2n\) зелий. После каждого раунда дуэли они выбирают два наиболее близких по мощности восстанавливающих зелья. Из нескольких таких пар они выбирают ту, у которой сумма мощностей наибольшая. Затем Невилл выпивает более мощное зелье из пары, а Гарри - менее мощное.

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

Формат входного файла

Первая строка входного файла содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) - количество раундов дуэли. Во второй строке входного файла содержится \(2n\) целых чисел \(a_1, a_2, \ldots, a_{2n}\) (\(1\le a_i \le 10^9\)), где \(a_i\) - мощность \(i\)-го восстанавливающего зелья.

Формат выходного файла

В первой строке выведите \(n\) чисел - мощности зелий, которые выпьет Невилл. Во второй строке выведите \(n\) чисел - мощности зелий, которые выпьет Гарри. Зелья надо выводить в том порядке, в котором Невилл и Гарри должны их выпивать.

Примеры
Входные данные
1
3 6
Выходные данные
6
3
Входные данные
2
11 43 56 22
Выходные данные
22 56
11 43
#111636
Древние династии
  

История Татаро-монгольского ханства богата на правителей. Каждый из N правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй — праздник мёда.

На конференции по истории Татаро-монгольского ханства каждый из S учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее KLi лет, но не более KRi лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее MLi лет, но не более MRi лет.

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

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

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

В первой строке входного файла записано число N (2 ≤ N ≤ 200 000) — количество праздников в летописи. Следующая строка содержит целые числа X1, X2, ..., XN (1 ≤ X1 ≤ X2 ≤ ... ≤ XN ≤ 109) — годы проведения праздников.

В третьей строке записано число учёных S (1 ≤ S ≤ 50). В каждой из последующих S строк записаны четыре натуральных числа KLi, KRi, MLi, MRi (1 ≤ KLi ≤ KRi ≤ 109), (1 ≤ MLi ≤ MRi ≤ 109).

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

Первая строка выходного файла должна содержать числа P и Q, где P — номер учёного, версии которого соответствует распределение с наименьшим показателем сомнительности, а Q — показатель сомнительности этого распределения.

Вторая строка должна состоять из N цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности Q, выведите любое из них.

В случае, если ни в одной из версий учёных не существует способа распределения периодов правления между династиями так, чтобы не нарушались ограничения на промежутки времени между праздниками, выходной файл должен содержать единственное число 0.

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.

  2. 2 ≤ N ≤ 15, 1 ≤ S ≤ 10. Подзадача оценивается в 20 баллов.

  3. 2 ≤ N ≤ 2000, 1 ≤ S ≤ 50, N × S ≤ 2000. Подзадача оценивается в 20 баллов.

  4. 2 ≤ N ≤ 10 000, 1 ≤ S ≤ 50, N × S ≤ 10 000. Подзадача оценивается в 20 баллов.

  5. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50, N × S ≤ 200 000. Подзадача оценивается в 20 баллов.

  6. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50. Подзадача оценивается в 20 баллов.

Примеры
Входные данные
3
1 2 3
1
1 1 1 1
Выходные данные
1 1
211
Входные данные
4
1 6 9 13
2
1 2 2 3
6 7 3 3
Выходные данные
0
Входные данные
5
3 6 8 9 10
2
2 3 1 1
1 4 1 10
Выходные данные
2 0
21212
#111878
Взвешивание камней
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Джек нашел \(N\) камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий  2 и так далее, самый тяжелый получил номер \(N\).

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

Ваша задача — определить состояние весов после добавления каждого камня. Точные массы камней не известны — даются только их номера.

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

Первая строка содержит целое число \(N\) (1 \(\le\) \(N\) \(\le\) 100000).

Каждая из следующих \(N\) строк содержит по два целых числа: \(R\) (1 \(\le\) \(R\) \(\le\) \(N\)) и \(S\) (1 \(\le\) \(S\) \(\le\) 2). \(R\)  номер камня, который будет положен на чашу \(S\). Все \(R\) будут различны.

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

Выведите \(N\) строк  по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры
Входные данные
5
1 2
3 1
2 1
4 2
5 1
Выходные данные
<
>
>
?
>
Страница: << 6 7 8 9 10 11 12 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест