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

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

8A. Несоставляемое число
[nosum]
Хорошая задача, сродни Рюкзаку. Нужно быть внимательным и не ошибиться с выбором типа данных для хранения ответа.
8B. SMS
Очень хорошая задача, которая является логическим продолжением серии задач на динамическое программирование. Первая задача на двумерное ДП. Над ней думал пару дней, в результате чего получилось следующее решение:
[sms] локаничная запись
В книге Павловской вычитал следующий девиз: “Better simpler than clever” (лучше по-простому, чем по-умному). В результате чего увидел в авторском разборе более понятную реализацию, которая делает тоже самое:
[sms] понятная запись
8C. Дерево игры
[gametree]
3-я задача на тему антагонистические игры. Не должна вызывать серьезных затруднений. Решается по аналогии с  предыдущими задачами. В ходе решения явно использовалась рекурсия. Если по условию задачи видно, что глубина рекурсии будет непозволительно большой, то можно модернизировать решение до неявного использования рекурсии или, если это поможет, увеличить глубину стека. Мы такое уже делали раньше.
8D. Дуга на сфере
[spherarc]
Задача на знание формул. А формулы, как говорится, надо знать или уметь их выводить.
8E. Путь коня
[knightw]
Эта задача уже была подробно рассмотрена в тренировках Михаила Долинского. Но решить ее еще раз будет крайне полезно.
8F. Грядки
[beds]
Очередная задача на DFS/BFS. Долго не мог понять, зачем автор дал столько много однотипных задач. Но когда ознакомился с разборами стало ясно, что на маленьких ограничениях можно успешно сдать решение с большой алгоритмической сложностью, но более лаконичной записью. В наших разборах я их не упомянул, поэтому всех заинтересовавшихся перенаправляю в книгу.  

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