Разбор задач олимпиады ФПМИ 2010 года (Лига B) © 2010, Serge Kashkevich. - презентация

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

2 Статистика решения задач Название задачи Сложность (по мнению авторов) Количество решивших Числа-палиндромы 116 Скобочная последовательность 46 Буква А 50 Алхимия 40 Золотая середина 115 Округление 30 Галлеоны, сикли и кнаты 215 Шаблоны 45 Сверхпростые числа 310 Турнир по переписке 44

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

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

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

6 Буква А Автор задачи – С.И. Кашкевич Задача впервые была предложена на чемпионате Гродненского университета в 2010 году. Задача решается перебором всех троек отрезков. (Естественно, если N

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

8 Золотая середина Автор задачи – С.И. Кашкевич Задача, которую, по идее, должны решить все. Приведём авторское решение: ab := (a

9 Округление Автор задачи – С.И. Кашкевич Относительно простая по условию задача требует аккуратного разбора большого количества случаев: N

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

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

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

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

14 Турнир по переписке Автор задачи – С.И. Кашкевич Заведем матрицу 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 ещё не завершилась.

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