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

университета в 2010 году.

Для решения задачи необходимо:
вычислить сумму двух чисел;
выделить все цифры суммы в строку;
проверить, является ли полученная строка палиндромом

сводится к проверке правильности скобочной последовательности с использованием стека.
Исходную строку «склеиваем» саму с собой, и далее рассматриваем все подстроки длины N, начинающиеся с открывающей скобки.
Если хотя бы одна из подстрок является правильной скобочной последовательностью – выводим ответ “Yes”, иначе – “No”.

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

Гродненского университета в 2010 году.

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

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

все. Приведём авторское решение:

ab := (a bc := (b ac := (a
if ab and bc then d := b; {a if (not ab) and (not bc) then d := b; {c if ab and (not ac) then d := a; {c if (not ab) and ac then d := a; {b if (not bc) and ac then d := c; {a if bc and (not ac) then d := c; {a

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

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

умения работать с битовыми масками.
Заведём различные битовые маски для каждого символа, входящего в шаблон:

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

массив P из первых 3571 простых чисел (3571 – 500-е простое число).
Тогда результат для заданного k будет равен P[P[k]].

* 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 ещё не завершилась.

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