Məsələlər
Задача Итана Ханта
Задача Итана Ханта
Герой сериала "Миссия невыполнима" Итан Хант известен больше как диверсант. Однако однажды ЦРУ привлекло его в качестве эксперта по оценке надёжности кодов дверей в ЦРУ. Как известно (в основном, по популярным фильмам), кодовые замки в ЦРУ открываются с помощью магнитной карточки. Будем считать, что на этой карточке записана последовательность битов длины \textbf{M}. Последовательность битов считывается, и если записанные биты совпадают с кодом двери, дверь открывается. У Ханта спросили, как бы он вскрывал такой замок, и тот предложил следующую идею.
Возьмём длинную магнитную ленту, запишем на неё произвольную последовательность длины \textbf{N}\textit{ (}\textbf{N}\textit{ }≥\textit{ }\textbf{M}\textit{) }из \textbf{0} и \textbf{1}, такую, что вероятность встретить в ней на каждой позиции \textbf{0} или \textbf{1} одинаковы. Затем проведём этой лентой по замку. Если в этой последовательности где-то встретился код замка, замок откроется (напомним, что дело происходит в голливудском фильме, и то, что физическая кодировка сплошной ленты и магнитной карты никак не совпадают, не столь важно).
В дирекции ЦРУ подумали и решили проверить все коды замков на хантоустойчивость.
\InputFile
В первой строке число \textbf{N} - длина последовательности битов, записанных на ленте ( \textbf{1} ≤ \textbf{N}\textit{ }≤ \textbf{60}). Во второй строке -- код замка, т.е. непустая строка, состоящая из символов "\textbf{0}" и "\textbf{1}", длина которой не превышает \textbf{N}.
\OutputFile
Вероятность наличия кода замка в произвольно взятой последовательности битов длины \textbf{N}. Вероятность выдается в виде несократимой дроби, числитель и знаменатель которой разделены символом "\textbf{/}".
Giriş verilənləri #1
3 00
Çıxış verilənləri #1
3/8