Разбор задач олимпиады ФПМИ 2010 года (Лига B)


The Presentation inside:

Slide 0

Разбор задач олимпиады ФПМИ 2010 года (Лига B) © 2010, Serge Kashkevich


Slide 1

Статистика решения задач


Slide 2

Числа-палиндромы Автор задачи – С.И. Кашкевич Задача впервые была предложена на чемпионате Гродненского университета в 2010 году. Для решения задачи необходимо: вычислить сумму двух чисел; выделить все цифры суммы в строку; проверить, является ли полученная строка палиндромом


Slide 3

Скобочная последовательность Задача была предложена на интернет-олимпиаде ИТМО 23 сентября 2006 года Задача сводится к проверке правильности скобочной последовательности с использованием стека. Исходную строку «склеиваем» саму с собой, и далее рассматриваем все подстроки длины N, начинающиеся с открывающей скобки. Если хотя бы одна из подстрок является правильной скобочной последовательностью – выводим ответ “Yes”, иначе – “No”.


Slide 4

Скобочная последовательность Алгоритм проверки правильности скобочной последовательности с использованием стека. for i := 1 to N do begin if (Si – открывающая скобка) then заносим Si в стек else begin извлекаем из стека символ T; if (стек пуст) or (типы скобок T и Si различаются) then скобки расставлены неверно; end; end; if (стек пуст) then скобки расставлены верно else скобки расставлены неверно;


Slide 5

Буква А Автор задачи – С.И. Кашкевич Задача впервые была предложена на чемпионате Гродненского университета в 2010 году. Задача решается перебором всех троек отрезков. (Естественно, если N<3, ответом будет 0.) Для каждой тройки: определяем «ножки» - непараллельные отрезки, пересекающиеся в концах; проверяем, является ли третий отрезок правильной «перекладиной» Для решения задачи необходимо уметь определять взаимное расположение двух отрезков.


Slide 6

Алхимия Задача была предложена на интернет-олимпиаде ИТМО 23 сентября 2006 года Строим ориентированный граф, вершинами которого являются вещества, а дуга проходит из вершины A в вершину B, если можно превратить вещество A в вещество B. В полученном графе ищем кратчайший путь из начальной в конечную вершину методом поиска в ширину. Особенностью задачи является то, что начальное и конечное вещество могут отсутствовать в списке веществ, упомянутых в алхимических реакциях.


Slide 7

Золотая середина Автор задачи – С.И. Кашкевич Задача, которую, по идее, должны решить все. Приведём авторское решение: ab := (a<b); bc := (b<c); ac := (a<c); if ab and bc then d := b; {a<b<c} if (not ab) and (not bc) then d := b; {c<b<a} if ab and (not ac) then d := a; {c<a<b} if (not ab) and ac then d := a; {b<a<c} if (not bc) and ac then d := c; {a<c<b} if bc and (not ac) then d := c; {a<c<b}


Slide 8

Округление Автор задачи – С.И. Кашкевич Относительно простая по условию задача требует аккуратного разбора большого количества случаев: N <= количества разрядов в целой части (результат – ‘0’); N <= 0 (выводить или нет десятичную точку); N < 0 (добавлять ли нули в целой части); перенос единицы из дробной части в целую и т. д.


Slide 9

Галлеоны, сикли и кнаты Автор задачи – С.И. Кашкевич Переведём все денежные величины в кнаты. Это даёт возможность проводить все вычисления в целых числах без промежуточных переводов. После выполнения вычислений переведём количество кнатов, оставшихся у Гарри Поттера, в требуемый формат.


Slide 10

Шаблоны Задача была предложена на интернет-олимпиаде ИТМО 23 сентября 2006 года Задача требует умения работать с битовыми масками. Заведём различные битовые маски для каждого символа, входящего в шаблон:


Slide 11

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


Slide 12

Сверхпростые числа Задача была предложена на интернет-олимпиаде ИТМО 7 октября 2006 года Формируем массив P из первых 3571 простых чисел (3571 – 500-е простое число). Тогда результат для заданного k будет равен P[P[k]].


Slide 13

Турнир по переписке Автор задачи – С.И. Кашкевич Заведем матрицу P размера N * N, в которой будут храниться результаты каждой партии: P[i, i] = 0; P[i, j] = 1, если игрок i выиграл у игрока j; P[i, j] = 0, если игрок j выиграл у игрока i; P[i, j] = 0.5, если партия между игроками i и j завершилась вничью; P[i, j] = -1, если партия между игроками i и j ещё не завершилась.


Slide 14

Турнир по переписке Заполнение матрицы будем вести в несколько этапов: полагаем P[i, j] := -1 для всех i<>j; заносим результаты завершившихся партий; определяем, кто из игроков выбыл из турнира; для всех P[i, j] = -1 определяем окончательный результат партии, в зависимости от состояния игроков (ничья, поражение отказавшегося, обоюдное поражение) После этого рассчитываем сумму значений в строках матрицы и выполняем сортировку для вывода.


×

HTML:





Ссылка: