Задачки ШАД на YaC 2013

На YaC 2013, на стенде ШАД, давали первую дозу бесплатно, 5 задачек, для привлечения молодого пополнения, ну и я взял, проверить силы. Итак.

Задача 1. SHAD. SHAD? SHAD!

Решите ребус. Одинаковыми буквами обозначены одинаковые цифры, а разными - разные. Звездочками обозначены произвольные цифры:

             S  H  A  D

             S  H  A  D

            ---------------

           * *  *   *  *

        * * *  *   *   

     * * * *  *

  * * * * *

-------------------------

  * * * * S  H  A  D

Не сложная задача, я решил методом перебора. Начинаю перебирать со значения D, берем

D = 0

        A   0

        A   0

      --------

      0*A 0

      A*0

       -------

        A   0

      Значит (D * A)%10 + (A * D) % 10 + 0(это перенос с D*D) = A => A = 0, что противоречит условию

D = 1

     A % 10 + A % 10 + 0 = A => (2*A) % 10 = A

     Это уравнение верно только при A = 0

     D = 1, A = 0

     Получаем уравнение вида: (2* H) % 10 = H оно верно только при H = 0, что противоречит условию, сл-но A != 0, D != 1

D = 2, 3, 4 аналогично

D = 5

     Получаем уравнение вида (5A + 5A + 2) % 10 = A

     (10A + 2) % 10 = A

     Перебираем А

     A = 0, 1 не подходит

     A = 2 подходит

          Подбираем H

             Необходимо решить уравнение вида (5H + 5H + 10) % 10 = H

             H = 0, 1, 2, 3, 4, 5 - не подходят

             H = 6 подходит

               Подбираем S

                  Необходимо решить уравнение вида: (10S + 10) % 10 = S

                  Что верно при S = 0

Итого 0625. 

Но при сдаче задания мне сказали что 0 использовать нельзя, хотя ответ и верен.

Можно продолжить перебирать D и вывести другой ответ: 9376

Задача 2. Программиста

Я не опечатался, название действительно такое.

Два программиста играют в игру. Выписаны все целые числа от 0 до 2^10 в порядке возрастания. Программисты по очереди делают 10 ходов: вычеркивают 2^10(10 - n) чисел, где n - номер хода. Когда остаются 2 числа, второй программист пишет за первого столько строк кода, какова разность(по модулю) между двумя оставшимися числами. Сколько строчек кода придется написать второму программисту за первого при правильной игре обоих.

Тут главное найти стратегию игры за обоих. 

Для первого я выбрал такую: на каждом ходе он вычеркивает числа через одно. Т.е. после первого его хода, разница между двумя ближайшими будет не меньше 2. После второго не меньше четырех.

Для второго игрока я не смог придумать стратегию которая могла бы помешать первому. Поэтому я решил, что ему лишь бы не навредить и поэтому он будет уполовинивать оставшийся интервал.

Итак, первый ход за первым программистом, он вычеркивает 2^9 чисел через одно, 2^9 чисел остается. Разница между двумя близлежащими не менее 2. 

Второй игрок на втором ходу вычеркивает 2^8 чисел и оставляет после себя 2^8. Он не может уменьшить минимальный интервал, просто отсекает правую или левую половину.

Далее 3, 4.... ходы аналогично.

Наступает 9 ход.

Осталось 4 числа, ходит первый программист, расстояние между двумя близлежащими не менее 15.

Например, могли остаться 0, 16, 32, 48.

Вот тут я посчитал, раз второй будет писать разность между двумя оставшимися, то я вычеркну 16 и 32, и тогда разность будет 48. Но когда я разговаривал на стенде с авторами, они сказали что у меня логика верная, но на 9 ходе первый программист должен также вычеркнуть через одно, и тогда второй будет писать 32 строки и это правильный ответ.

Они мотивировали это тем, что второй программист должен сделать 10-й ход, хотя не совсем понятно при чем здесь это.

           

Задача 3 Perla negra

Слепой пират захватил 20 корзин с жемчугом. В 19 корзинах жемчуг белый, а в одной черный. Черная жемчужина в два раза тяжелее белой. У пирата есть чашечные весы без гирь, которые издают щелчок в момент, когда весы приходят в равновесие. Пират никому не показывает свой трофей, а хочет сам найти корзину с черным жемчугом. Как ему это сделать за одно уравновешивание весов.

Тривиальная задача:

Берем 2 жемчужины из любой корзины и считаем ее белой. Далее перебираем по одной жемчужины из оставшихся 19 корзин. Если среди них есть черная, то мы обязательно услышим щелчок. Если щелчка не услышали, значит изначальная предпосылка ошибочна и первая корзина черная.

Задача 4 Путники в Сахаре

4 исследователя запаслись 40 пайками и отправляются в экспедицию в Сахару. Каждый может нести запас провианта и воды на 10 дней. Цель экспедиции - наиболее далеко продвинуться в глубь пустыни, т.е. хотя бы один исследователь должен продвинуться как можно дальше, и все они должны вернуться обратно. Путешественники совершают переходы в течение дня, а вечером могут передавать друг другу провиант, а также строить хранилища пайков. Как далеко сможет пробраться экспедиция(в пересчете на дневные переходы).

Вот на эту и следующую задачу уже не хватило времени. Эта задача еще интересна и тем, что я, позже, не смог свести ее к какой-либо стандартной(можно было бы даже набросать программку для ее решения). Т.е. методом перебора я попробую ее решить и думаю смогу. Но вот если бы исследователей было 10, пайков пусть 200, то перебором ее решить было бы уже чрезвычайно сложно. В ближайшее свободное время постараюсь разобраться с ней и написать.

Задача 5 Чай вприкуску

К купчихе Капитолине Львовне пришли гости, и она пригласила их пить чай с сахаром вприкуску. Поставила самовар, достала сахар и обнаружила, что сахар отсырел, и все 27 кубиков слиплись в один большой куб. Капитолина Львовна уже хотела расколоть кусок сахара, но капризные гости сказали, что они не желают пить чай с кубиками сахара, а хотят, чтобы кусочки были какой-нибудь необычной формы(т.е. фигурками, составленными из кубиков, но не являющимися прямоугольными параллелепипедами). К тому же гости захотели, чтобы все кусочки сахара были разной формы(фигурки считаются разными, если их можно совместить только при отражении, но нельзя при повороте)ю Зато они обещали не обижаться, если им достанется разное количество кубиков. Немного поразмышляв, Капитолина Львовна все же выполнила прихоть гостей. А про себя подумала: "Вот если бы еще кто-нибудь пришел в гости, то тогда уж точно задача была бы невыполнимой!". Сколько же гостей пришло к Капитолине Львовне, если сама она сладкого не ела.

Пространственные задачки тоже не приходилось решать, разберусь - напишу решение. Но тут, учитывая размер задачи, думаю можно решить даже простым перебором.