ACM ICPC NEERC 2009 -2010 Norhern Subregion Разбор задач
Задачи A. Auxiliary Question of the Universe B. Bureaucracy C. Circles on a Screen D. Dragon's Question E. Enigmatic Device F. Four Points G. Grand Theft Auto Wheel H. Homo or Hetero? I. Image Recognition Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 2
Problem A Auxiliary Question of the Universe
Формулировка задачи Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 4
Пример решения l l 0 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 6
Пример решения l 1 l 0+1 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 7
Пример решения l 1+ l 0+1 Georgiy Korneev +(0) ACM ICPC NEERC Northern Subregion / Разбор задач 8
Пример решения l 1+0 l 0+1 Georgiy Korneev +(0)+0 ACM ICPC NEERC Northern Subregion / Разбор задач 9
Пример решения l 1+0+ l 0+1 Georgiy Korneev +(0)+0+(0) ACM ICPC NEERC Northern Subregion / Разбор задач 10
Пример решения l 1+0+1 l 0+1 Georgiy Korneev +(0)+0+(0)+1 ACM ICPC NEERC Northern Subregion / Разбор задач 11
Пример решения l 1+0+1) l 0+1 Georgiy Korneev +(0)+0+(0)+1+(0) ACM ICPC NEERC Northern Subregion / Разбор задач 12
Problem B Bureaucracy
Пример решения 1. declare 2. cancel 1 3. declare 4. cancel 2 5. cancel 3 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 16
Пример решения 1. declare 2. cancel 1 3. declare 4. cancel 2 5. cancel 3 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 17
Пример решения 1. declare 2. cancel 1 3. declare 4. cancel 2 5. cancel 3 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 18
Пример решения 1. declare 2. cancel 1 3. declare 4. cancel 2 5. cancel 3 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 19
Пример решения 1. declare 2. cancel 1 3. declare 4. cancel 2 5. cancel 3 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 20
Problem C Circles on a Screen
Формулировка задачи Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 22
Рассмотрим строку Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 24
Круг 1 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 25
Круг 2 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 26
Случаи при объединении Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 28
Problem D Dragon's Question
Формулировка задачи ln < #d l Нет решения l n = #d ld l n > #d l d<n - #d нулей> Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 32
Problem E Enigmatic Device
Дерево отрезков Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 35
Дерево отрезков Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 36
Проталкивание информации Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 41
Время и память l Время работы l O(m p log n) l Память l O(n p) l p – период (10) Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 42
Problem F Four Points
Формулировка задачи Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 44
Соединяем точки Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 45
Строим окружности Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 46
Проводим диагональ Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 47
Численное решение Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 48
Поворот на 90º градусов Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 49
Problem G Grand Theft Auto Wheel
Формулировка задачи Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 52
Решение l Болт l Выступ l Ключ l Зубец Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 53
«Запрещенные углы» Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 54
Problem H Homo or Hetero?
Problem I Image Recognition
Формулировка задачи Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 61
Problem J Jealous Numbers
Problem K Kripke Model
Пример поиска вершин I типа Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 73
Обращаем ребра Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 74
Рассматриваем вершину 2 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 75
Из нее достижима вершина 1 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 76
Аналогично для вершин 1, 6, 7 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 77
Берем дополнение Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 78
Пример поиска вершин II типа Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 81
Рассматриваем вершину 4 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 82
Из нее достижимы вершины 3, 2, 1 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 83
Аналогично рассматриваем 5 Georgiy Korneev ACM ICPC NEERC Northern Subregion / Разбор задач 84
