Разбор задач 1 тура чемпионата

Разбор задач выполнил Василий Болгар, студент 145 группы ИТНИТ СыктГУ

Шахматный конь
Самая простая задача на турнире. Сначала нужно считать строку S и перевести ее в целочисленные координаты коня. Например, в Паскале ord(S[1]) ‑ ord('A') и ord(S[2]) ‑ ord('1') дают нам две координаты (x, y), каждая из которых лежит в отрезке [0..7]. После этого мы последовательно ходим конем на все возможные восемь позиций и проверяем, что координаты все еще лежат внутри отрезка [0..7], то есть мы не вышли за пределы доски. Если мы все еще на доске ‑ добавляем единицу к счетчику. Не забываем инициализировать счетчик нулем.
Выводим ответ.
Задачу можно было решать как угодно, в том числе можно было задать двумерный массив позиций коня на доске и в каждую клетку записать вручную посчитанный ответ.
Замечание. У одного участника была проблема с языком Си++. Вторую координату он брал необработанной и получал выражение наподобие '1' - 1, а так как CHAR также числовой тип, то получалось выражение эквивалентное этому: ord('1') - 1 = 49 - 1 = 48. И это явно не то, что участник хотел от своей программы.
Любопытство
Задача была взята с портала Timus Online Judge. Там она называется "Утро сороконожки". И она обувает сначала левые 40 ног, потом правые 40 ног. Соответственно нужно выбрать наихудший по времени способ обуть сороконожку.
Рассмотрим два варианта обувания.
1 вариант. Сначала "неудачно" пытаемся обуть левые ноги всеми правыми ботинками (соответственно, правые ноги будут обуты к концу всех попыток, так как и a и b не меньше 40). И оставшимися левыми ботинками дообуваем 40 левых ног.
Итого = b * 2 + 40
2 вариант. Сначала нам попадается 39 правых ботинок. Потом сорок левых, потом мы пытаемся на оставшиеся правые ноги надеть все недоодетые левые ботинки, и, в конце концов, последний правый.
Итого = 39 * 2 + 40 + (a - 40) * 2 + 1
Выбираем наибольшее число из этих двух - PROFIT!!!
Светлячки
Задача на структуры данных. Мы должны иметь такую структуру, чтобы всегда могли вытащить из батареи минимальный заряд. Это двоичная куча (Heap). Дальше имитируем заряд батареи. Смотрим, если наш заряд помещается, то есть при его добавлении весь заряд не превышает максимум ‑ добавляем заряд, если нет, то вытаскиваем минимальные заряды, пока не поместится.
Странный язык
У нас есть словарь, состоящий из слов - in, input, out, output, one, puton. Нужно проверить, принадлежит ли он языку. Это тоже задача с портала Timus Online Judge.  Там она называется "странный диалог".

Первое, что приходит в голову - смотреть в начало строки, если подстрока совпадает с любым элементом словаря - удаляем ее. Если мы смогли удалить все ‑ значит перед нами язык, если нет – значит, нет.
Но тут возникает проблема, существуют коллизии. Например, нам дана строка "inputon". Если мы сначала удалим "input", то у нас останется "on", остаток мы удалить не сможем - выведем NO, но ведь in + puton вполне себе язык, а значит, мы должны вывести YES.
Можно рассмотреть все варианты, запустить рекурсию, которая будет удалять "in" и рекурсивно рассматривать "puton" и удалять "input" и рассматривать "puton". Если хоть какая-то процедура придет к пустой строке - выводить YES, иначе - NO. И такое решение проходило на предложенных ограничениях.
Но проще всего было смотреть диалог с конца, то есть, перевернуть все строки в условии и вводе задачи.
В таком случае мы получаем набор ni, tupno, tuo, tuptuo, eno, notup, который НЕ СОДЕРЖИТ коллизий, и мы можем линейно удалять из перевернутого ввода, например "notupni" все подходящие варианты префиксов не задумываясь.
Замечание. Префикс - подстрока строки, начинающаяся с ее первого символа. Префиксы abcde ‑ a, ab, abc, abcd, abcde.
Очередь
В задаче вас напрямую просят найти перестановку по номеру. Алгоритм общедоступен, почитать о нем можно здесь - http://cppalgo.blogspot.ru/2011/02/4.html