- Задача Шляпы (Ким Вячеслав)
Представим себе, что сидят 3 человека, есть 7 шляп. 3 из них точно черные, поэтому количество белых не превышает 4, то есть M-N.
Если все шляпы черные, тогда все очевидно, любой может встать и сказать, что на нем черная.
Если одна шляпа белая, а остальные черные, тогда каждый мог подумать таким образом: “Я вижу перед собой две черные шляпы. Если бы на мне была белая, то для других было бы очевидно, что на них черные. Но они так не сказали, когда ведущий спрашивал, следовательно, на мне черная”.
Если бы было две белых шляп, тогда можно было ...
В силу небольших ограничений на длину строк мы можем перебрать всевозможные варианты соединений, которые могут быть получены из данных имен. Сделаем это следующим образом: будем убирать по одному символу справа из первого имени и приписывать к нему второе, при этом каждый раз будем проверять: начинается ли образующаяся таким образом строка с первого имени, если это так, то данная строка удовлетворяет необходимому условию (заканчиваться она будет вторым имененем по построению). При встрече очередной строки, начинающейся и заканчивающейся нашими именами, будем сравнивать ее с ранее найденной, на текущий момент самой короткой. Если текущая окажется короче, то ее следует запомнить. После перебора всех ...