Темы
    Информатика(2656 задач)
---> 304 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 47 48 49 50 51 52 53 >> Отображать по:
#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
#112333
Петя и Робот
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes
У Пети на полке стоят n тетрадей с полным собранием его идей. Тетради пронумерованы различными целыми числами от 1 до \(n\). У Пети есть привычная расстановка тетрадей (возможно, не в порядке нумерации), и он не любит, когда кто-то их переставляет. Петя купил специального Робота, который умеет запоминать расстановку тетрадей и вычислять число беспорядков в этой расстановке.

Робот считает, что две тетради образуют беспорядок, если тетрадь с меньшим номером стоит правее тетради с большим номером. Например, в расстановке (2; 1; 5; 3; 4) беспорядки образуют три пары тетрадей (2; 1), (5; 3) и (5; 4), поэтому число беспорядков в такой расстановке равно 3.

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

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

Протокол взаимодействия

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

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

Затем протокол общения вашей программы и программы жюри следующий:

* Для перестановки двух тетрадей ваша программа выводит в стандартный поток вывода запрос в формате: swap \(i\) \(j\), где \(i\) и \(j\) — номера позиций тетрадей, которые Робот должен поменять местами (1 <= \(i\), \(j\) <= \(n\); i != j). После этого она должна считать из стандартного потока ввода одно целое число — количество беспорядков в получившейся расстановке. Ваша программа может сделать не более 300 000 запросов.

* Когда ваша программа сможет восстановить привычную расстановку тетрадей, она должна вывести эту расстановку в формате: answer \(p\), где \(p\) — последовательность из n различных целых чисел в диапазоне от 1 до \(n\), и завершить работу.

Запрос на обмен и вывод привычной расстановки должны завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) в Pascal/Delphi; fflush(stdout) или cout.flush() в С/C++.

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

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

Подзадача 1

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

Подзадача 2

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

Подзадача 3

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

Подзадача 4

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

#112334
Коллайдер 2.0
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes
Коллайдер — это установка для изучения столкновений элементарных частиц. При его работе частицы разгоняются до большой скорости. Специальный детектор позволяет фиксировать траектории частиц в виде прямых на горизонтальной плоскости.

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

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

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

• появление новой траектории частицы,

• получение фотоснимка камерой, ориентированной по заданной направляющей прямой,

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

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

В первой строке входного файла задано одно целое число n (1 <= \(n\) <= 200 000) — общее количество событий. В следующих \(n\) строках заданы описания событий.

Описание каждого события состоит из пяти элементов. Первый элемент является символом «+», если это событие является появлением новой траектории, или символом «?», если это событие является получением фотоснимка. Последующие четыре элемента — целые числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) (−10 000 <= \(x_1\), \(y_1\), \(x_2\), \(y_2\) <= 10 000) — координаты двух несовпадающих точек. Для событий первого типа указанные точки лежат на траектории частицы. Все траектории различны. Для событий второго типа указанные точки лежат на направляющей прямой камеры.

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

Пусть \(q\) — количество полученных фотоснимков. Выходной файл должен содержать \(q\) вещественных чисел — минимальные возможные площади фотоснимков, перечисленные в порядке их получения камерой.Тест будет успешно пройден, если для каждой из \(q\) выведенных площадей выполняется условие |a - b| / (max(1, b)) <= 10-4, где \(a\) — площадь, выведенная участником, \(b\) — площадь, полученная решением жюри.

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

Далее приведены рисунки для первого и второго примеров соответственно.

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

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

Тест n q Примечание
1. 10 1 Направляющие прямые параллельны осям координат
2. 20 10 Направляющие прямые параллельны осям координат
3. 745 365 Направляющие прямые параллельны осям координат
4. 1997 10 Направляющие прямые параллельны осям координат
5. 2000 1000 Направляющие прямые параллельны осям координат
6. 100001 1 Направляющие прямые параллельны осям координат
7. 100002 1 Направляющие прямые параллельны осям координат
8. 200000 1 Направляющие прямые параллельны осям координат
9. 200000 100000 Направляющие прямые параллельны осям координат
10. 200000 130000 Направляющие прямые параллельны осям координат
11. 1000 10
12. 500 250
13. 10100 10000
14. 700 100
15. 800 71
16. 2001 1000
17. 5003 2000
18. 7005 4000
19. 8007 1000
20. 9009 4500
21. 90100 90001
22. 5000 101
23. 6000 98
24. 5432 2345
25. 9508 4079
26. 156002 151001 Все фотоснимки выполняются после появления всех частиц
27. 157004 152001 Все фотоснимки выполняются после появления всех частиц
28. 197062 190001 Все фотоснимки выполняются после появления всех частиц
29. 148008 141001 Все фотоснимки выполняются после появления всех частиц
30. 169010 163501 Все фотоснимки выполняются после появления всех частиц
31. 165011 159001 Все фотоснимки выполняются после появления всех частиц
32. 185001 179102 Все фотоснимки выполняются после появления всех частиц
33. 176001 168098 Все фотоснимки выполняются после появления всех частиц
34. 155433 147234 Все фотоснимки выполняются после появления всех частиц
35. 159608 152179 Все фотоснимки выполняются после появления всех частиц
36. 165011 159001
37. 185001 179102
38. 176001 174000
39. 155433 153556
40. 159608 157701
41. 200000 1
42. 110000 10
43. 120000 50
44. 199999 70
45. 188888 100
46. 200000 100000
47. 199999 195000
48. 199999 100000
49. 178689 98276
50. 199998 88888
Примеры
Входные данные
6
+ 0 0 0 1
+ 0 0 1 0
+ 1 0 0 2
? 0 0 0 1
+ 2 4 3 6
? 0 0 1 1
Выходные данные
2.0
3.000
Входные данные
7
? 11 4 -7 8
+ -2 -2 1 1
? 0 0 0 1
+ 0 1 1 0
+ 0 2 2 0
? 0 0 0 1
? 0 0 1 1
Выходные данные
0.0
0.0
0.25
0.0000000
Страница: << 47 48 49 50 51 52 53 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест