Тренировка #10 [Меньшиков]

[Условия задач]                    [Список тренировок]

10A. Анти-QuickSort
[antiqs]
Нетипичная задача, требующая глубокого понимания работы быстрой сортировки.
10B. Строки Фибоначчи
[fibostr]
Классная задача на ДП. В наличием определенного опыта в решении подобных задач не представляет больших сложностей. Но есть ряд нюасов, которые нужно учесть.
10C. Игра в зачеркивание
Задача, которая не давала спокойно жить 2 дня. На нее было получено 4 решения, а все описание изложено в отдельном посте
[crossgam] TLE
[crossgam] ДП с запоминанием + vector   [0.105 с.]
[crossgam] ДП с запоминанием + multiset [0.322 с.]
[crossgam] на основе функции Grundy
10D. Граница многоугольника
[border]
Задача скорее на знания, чем на умения. Используем тот факт, что у прямоугольного треугольника количество точек с целочисленными координатами на гипотенузе равно НОД’у(Наибольшему общему делителю) катетов + 1. Представив каждую сторону за гипотенузу, обходим все стороны и получаем результат.
10E. Путь спелеолога
[speleo]
Задача на пространственное воображение и на трехмерный BFS. Особых сложностей быть не должно. Главное не забыть что здесь будет 6 измерений, в отличии от двумерного случая.
10F. Дырявая ткань
[holey]
Предложенное решение сделано полностью по авторскому разбору. Стоит обратить внимание на “приемчик”, как избежать TLE на максимальном тесте.


[Все решения]