Темы
    Информатика(2656 задач)
---> 97 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Заключительный этап
    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 задач)
Страница: << 11 12 13 14 15 16 17 >> Отображать по:
#111646
Флешмоб
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Для участников олимпиады на главной площади города «У» планируется игра в форме флешмоба. Главная площадь замощена плитками, образующими клетчатое поле.

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

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

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

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

В первой строке входного файла содержится число N — количество участников флешмоба (1 ≤ N ≤ 123 456). Каждая из последующих N строк содержит четыре целых числа x1i, y1i, x2i, y2i — координаты плиток для i-го участника (1 ≤ x1i,  y1i,  x2i,  y2i ≤ 109; либо x1i = x2i, либо y1i = y2i). Участники перечислены в порядке выхода на площадь.

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

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

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

Примечание

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

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

  2. N ≤ 123. Все координаты не превосходят 234. Подзадача оценивается в 21 балл.

  3. N ≤ 2543. Подзадача оценивается в 23 балла.

  4. N ≤ 123 456. Подзадача оценивается из 56 баллов.

Примеры
Входные данные
5
2 1 2 4
2 4 4 4
5 1 1 1
4 4 4 2
4 2 1 2
Выходные данные
5
1 2
4 3
1 1
3 4
2 3
Входные данные
3
1 1 1 3
2 1 2 3
1 2 2 2
Выходные данные
0
Входные данные
4
1 1 1 3
2 1 2 3
3 3 3 1
1 3 4 3
Выходные данные
4
4 3
3 1
2 1
1 1
#112328
Киноакадемия
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
В финал конкурса Киноакадемии вышли \(n\) лучших кинофильмов 2014 года. В конкурсе награждаются фильмы в двух номинациях: лучшая режиссура и лучший сценарий. По правилам конкурса в каждой номинации должен быть награжден ровно один фильм, причём в разных номинациях — разные фильмы.

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

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

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

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

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

Первая строка выходного файла должна содержать одно число — наибольший возможный суммарный уровень ликования. Вторая строка должна содержать два целых числа — номера фильмов-победителей в номинациях лучшая режиссура и лучший сценарий соответственно. Фильмы нумеруются натуральными числами от 1 до \(n\). Если оптимальных способов выбора награждаемых фильмов несколько, можно вывести любой из них.

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

2 <= \(n\) <= 100

1 <= \(a_i\), \(b_i\), \(c_i\) <= \(10^5\)

Подзадача оценивается в 20 баллов

Подзадача 2

2 <= \(n\) <= 2000

1 <= \(a_i\), \(b_i\), \(c_i\) <= \(10^5\)

Подзадача оценивается в 25 баллов

Подзадача 3

2 <= \(n\) <= \(10^5\)

1 <= \(a_i\), \(b_i\), \(c_i\) <= \(10^9\)

Подзадача оценивается в 55 баллов

Пояснение к примеру

В приведенном примере наибольший суммарный уровень ликования равен 3 + 5 + 9 = 17.

Примеры
Входные данные
3
3 6 9
1 5 7
1 3 9
Выходные данные
17
2 3
#112329
Магистраль "Урал"
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Планируется строительство новой магистрали «Урал». Долговечность автомагистрали зависит от пластов пород, залегающих под ней. Пластом называется геологическое тело, состоящее из одной горной породы.

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

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

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

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

Первая строка входного файла содержит целое число \(n\) — количество пластов. Пласты пронумерованы целыми числами от 1 до \(n\) в произвольном порядке.

В \(i\)-й из следующих \(n\) строк содержатся целые числа \(l_i\) и \(r_i\) (0 <= \(l_i\) < \(r_i\) <= \(10^9\) ) — расстояния от начала магистрали до точек, под которыми начинается и заканчивается \(i\)-й пласт.

В следующей строке записано целое число \(m\) — количество скважин, в которых проводилось бурение. Следующие \(m\) строк описывают результаты бурения: в каждой строке сначала указаны два целых числа \(x\) (0 <= \(x\) <= \(10^9\) ) и \(k\) (0 <= \(k\) <= \(n\)) — расстояние от начала магистрали до скважины и количество обнаруженных в данной скважине пластов, затем — целые числа \(s_1\); \(s_2\), ..., \(s_k\) — номера пробуренных пластов, перечисленные в порядке залегания сверху вниз. Скважины перечислены в порядке возрастания расстояния \(x\).

Гарантируется, что решение существует.

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

Первая строка выходного файла должна содержать n целых чисел \(p_1\); \(p_2\), ..., \(p_n\), описывающих возможный порядок залегания пластов сверху вниз. Среди чисел \(p_1\), \(p_2\), ..., \(p_n\) каждый номер пласта должен встретиться ровно один раз. При этом пласт с номером \(p_j\) не должен нигде проходить выше пластов с номерами \(p_1\), ..., pj-1 или ниже пластов с номерами pj+1, ..., \(p_n\)

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

Система оценки

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

Подзадача 1

1 <= \(n\), \(m\) <= 1000

Каждая скважина пересекает все пласты, залегающие под ней

Подзадача оценивается в 20 баллов

Подзадача 2

1 <= \(n\), \(m\) <= 1000

Подзадача оценивается в 20 баллов

Подзадача 3

1 <= \(n\), \(m\) <= 30000

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

Подзадача оценивается в 20 баллов

Подзадача 4

1 <= \(n\), \(m\) <= \(10^5\)

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

Подзадача оценивается в 20 баллов

Подзадача 5

1 <= \(n\), \(m\) <= \(10^5\)

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

Подзадача оценивается в 20 баллов

Примеры
Входные данные
4
1 5
2 7
7 10
1 11
3
1 1 1
4 1 2
7 2 2 3
Выходные данные
2 1 3 4
#112330
Здоровое питание
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
План студенческого городка некоторого университета представляет собой квадрат \(n\) x \(n\), в каждой клетке которого расположено здание. Здания соединены переходами, если они расположены в клетках, имеющих общую сторону. В левом верхнем углу квадрата расположено студенческое общежитие. В правом нижнем углу расположен учебный корпус.

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

Руководство университета заинтересовалось разнообразием питания студентов, покупающих продукты в автоматах по ходу движения. Для каждого автомата Ai,j планируется найти кратчайший путь из общежития в учебный корпус, проходящий через этот автомат и содержащий как можно больше автоматов, торгующих тем же самым продуктом, что и автомат Ai,j. Количество таких автоматов на этом пути называется избыточностью автомата Ai,j. При этом автомат A1,1 находится в общежитии, а автомат An,n — в учебном корпусе.

Требуется написать программу, которая по информации о продуктах, продаваемых автоматами, для каждого из чисел в диапазоне от 1 до 2n - 1 определяет число автоматов с таким значением избыточности.

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

Первая строка входного файла содержит целое число n (2 <= \(n\) <= 1500). Следующие \(n\) строк содержат по \(n\) чисел в каждой. В \(i\)-й из этих строк \(j\)-е число соответствует номеру продукта, продающегося в автомате A i, j. Номера продуктов находятся в диапазоне от 1 до \(n^2\).

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

Выходной файл должен содержать (2n - 1) целых чисел - количество автоматов с избыточностями 1, 2, ..., 2n - 1 соответственно

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

Для проверки решений этой задачи используются 50 тестов. Тесты оцениваются независимо. Каждый тест оценивается в 2 балла. Значения n в тестах жюри приведены в следующей таблице.

Примеры
Входные данные
3
1 1 1
2 2 2
3 3 3
Выходные данные
0 0 9 0 0
Входные данные
5
1 4 1 3 5
2 1 4 1 2
5 1 1 4 5
3 5 1 1 2
4 3 5 1 1
Выходные данные
2 4 9 0 0 1 1 8 0
#112332
Почему крокодилы не летают?
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Робинзон живет на острове, который представляет собой прямоугольник размером \(n\) × \(m\) клеток.

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

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

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

Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.

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

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

В первой строке входного файла записаны числа n и m — размеры острова с севера на юг и с запада на восток. Последующие n строк по m символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой «.», а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: «N» — север, «S» — юг, «E» — восток, «W» — запад

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

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

Система оценки

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

Подзадача 1

1 <= \(n\), \(m\) <= 30. Подзадача оценивается в 30 баллов.

Подзадача 2

1 <= \(n\), \(m\) <= 500. Подзадача оценивается в 30 баллов.

Подзадача 3

1 <= \(n\), \(m\) <= 2000. Подзадача оценивается в 40 баллов.

Рисунок к третьему примеру

Примеры
Входные данные
1 1
.
Выходные данные
0
Входные данные
1 1
W
Выходные данные
1
Входные данные
5 7
.......
...S...
..WE...
...N...
.......
Выходные данные
2
Страница: << 11 12 13 14 15 16 17 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест