Темы --> Информатика --> Алгоритмы --> Алгоритмы сортировки
    Квадратичные сортировки(24 задач)
    Сортировка записей(9 задач)
    Использование сортировки(13 задач)
    Быстрая сортировка(55 задач)
    Сортировка слиянием(9 задач)
    Сортировка подсчетом(27 задач)
    Сканирующая прямая(39 задач)
    Сортировка событий(4 задач)
---> 15 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Заключительный этап
    2004(6 задач)
    2005(6 задач)
    2006(6 задач)
    2007(6 задач)
    2008(6 задач)
    2009(6 задач)
    2010(6 задач)
    2011(8 задач)
    2012(8 задач)
    2013(8 задач)
    2014(7 задач)
    2015(8 задач)
    2016(8 задач)
    2017(8 задач)
Страница: << 1 2 3 Отображать по:
#1341
Граффити на заборе
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Около прямолинейного забора, состоящего из N одинаковых бетонных плит, проводится конкурс граффити, в котором участвуют M граффити-художников. Художники должны разрисовать все плиты своими произведениями за наименьшее возможное время.

Плиты пронумерованы числами от 1 до N, граффити-художники имеют номера от 1 до M. Первоначально i-й граффити-художник находится около плиты с заданным номером pi. Каждому художнику требуется b минут на разрисовывание любой плиты. Каждую плиту должен разрисовать ровно один граффити-художник.

В начале работы, а также после разрисовывания любой плиты граффити-художник может перейти к любой неразрисованной плите. Время перемещения граффити-художника от любой плиты к соседней с ней одинаково и равно a минут. Таким образом, чтобы перейти от плиты с номером i к плите с номером j художнику требуется a×|i – j| минут.

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

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

В первой строке входного файла указаны числа N — количество плит в заборе и M — количество граффити-художников (1 ≤ N, M ≤ 100000). Во второй строке заданы два целых числа: a — количество минут, которое требуется для перехода от любой плиты к соседней, и b — количество минут, которое требуется граффити-художнику на разрисовывание одной плиты (1 ≤ a, b ≤ 106). В третьей строке заданы M чисел p1, p2, …, pM — начальные положения граффити-художников (1 ≤ pi ≤ N).

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

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

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

Примечание

Решения, корректно работающие при M ≤ 2, будут оцениваться из 40 баллов.

Примеры
Входные данные
10 2
19 56
9 2
Выходные данные
375
5 10 9 8 7 6 
5 1 2 3 4 5
#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
    #2534
    Земледелие 2.0
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    Фермер Архип решил заняться земледелием и выращивать брюссельскую редиску. Для этого он купил прямоугольное поле, состоящее из \(n\) рядов по \(m\) участков в каждом. Все участки являются одинаковыми и имеют квадратную форму. Оказалось, что на момент покупки некоторые из этих участков уже удобрены, а некоторые — нет. Редиска растет только на удобренных участках.

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

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

    Напишите программу, которая по заданному полю находит фрагмент поля для удобрения и фрагмент поля под посадку.

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

    В первой строке входного файла записаны натуральные числа \(n\) и \(m\) (\(2\le n\le2\,000\), \(2\le m\le2\,000\)), где \(n\) — количество рядов на поле, а \(m\) — количество участков в каждом ряду (количество столбцов). Далее в \(n\) строках содержится описание поля. Каждая из этих \(n\) строк содержит \(m\) символов. Символ «1» обозначает, что соответствующий участок поля удобрен, а «0» — не удобрен. Гарантируется, что поле содержит хотя бы один удобренный и хотя бы один неудобренный участок. Поле расположено таким образом, что первая строка его описания соответствует северной стороне, а первый столбец — западной стороне.

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

    Первая строка должна описывать фрагмент поля для удобрения. Фрагмент описывается четырьмя числами \(a\), \(b\), \(c\), \(d\), где \(a\) и \(b\) — номер ряда и столбца самого северо-западного его участка, а \(c\) и \(d\) — номер ряда и столбца самого юго-восточного. Ряды нумеруются с севера на юг от 1 до \(n\), а столбцы — с запада на восток от 1 до \(m\).

    Вторая строка должна описывать фрагмент под посадку в том же формате.

    Третья строка должна содержать площадь фрагмента (количество участков) под посадку.

    Если решений несколько, выведите любое.

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

    Решения, корректно работающие при \(n\le40\) и \(m\le40\), будут оцениваться из 30 баллов, а решения, корректно работающие при \(n\le300\) и \(m\le300\), будут оцениваться из 60 баллов.

    Примеры
    Входные данные
    4 4
1110
1010
1110
0000
    Выходные данные
    2 2 2 2
1 1 3 3
9
    #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
    #112817
    Вышивка жемчугом
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    512 megabytes
    Дано изображение дерева из \(n\) вершин на прямоугольной сетке. Каждое ребро — либо вертикальный, либо горизонтальный отрезок длины \(1\) Дано \(q\) запросов, каждый имеет вид "сколько компонент связности образуется при вырезании данного прямоугольного фрагмента"

    Со стародавних времён в поморских деревнях рукодельницы вышивали жемчугом на прямоугольных полотенцах, состоящих из одинаковых клеток. Вышивка начиналась с пришивания жемчужины к полотенцу в центре одной из клеток. Чтобы пришить новую жемчужину, рукодельница делала стежок из клетки, уже содержащей жемчужину, в соседнюю с ней по горизонтали или вертикали свободную клетку. Новая жемчужина пришивалась в центре клетки на конце стежка. Этот процесс повторялся, пока не заканчивались жемчужины.

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

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

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

    Первая строка входных данных содержит два целых числа a и b — размеры полотенца в клетках по горизонтали и вертикали.

    Вторая строка содержит два числа \(n\) и \(q\) — количество жемчужин в узоре и количество фрагментов соответственно.

    Следующие (\(n − 1\)) строк содержат описания стежков. Каждый стежок имеет один из следующих видов:

    • \(h \times y\) означает, что клетки с координатами \((x, y)\) и \((x + 1, y)\) содержат жемчужины, соединённые горизонтальным стежком (\(1 \le x \le a − 1; 1 \le y \le b\));

    • \(v \times y\) означает, что клетки с координатами \((x, y)\) и \((x, y + 1)\) содержат жемчужины, соединённые вертикальным стежком (\(1 \le x \le a; 1 \le y \le b − 1\)).

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

    Следующие \(q\) строк описывают фрагменты. Каждое описание содержит четыре целых числа \(x_1\), \(y_1\), \(x_2\) и \(y_2\) — координаты левой нижней и правой верхней клетки фрагмента (\(1 \le x_1 \le x_2 \le a; 1 \le y_1 \le y_2 \le b\)).

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

    Выходные данные должны содержать \(q\) строк, где \(i\)-я строка содержит количество связных частей узора в \(i\)-м фрагменте.

    Таблица системы оценивания

    Замечание

    Пояснение к тесту из условия

    Примеры
    Входные данные
    4 3
8 4
v 1 1
h 1 1
h 2 1
v 2 1
v 2 2
h 1 3
h 3 1
1 1 4 3
3 2 4 3
3 1 3 1
1 2 3 3
    Выходные данные
    1
0
1
2
    Страница: << 1 2 3 Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест