udalite (udalite) wrote,
udalite
udalite

Categories:

Пример задачки с чемпионата

update: Сейчас все задачи сдали доступны на официальном сайте контеста: http://icpc.baylor.edu/icpc/Finals/2008WorldFinalsProblemSet.pdf

Чтобы было понятней, что за чемпионат и что за задачки тут. 80% - математика и очень сильная математика. 20% программирования - на то, чтобы быстро, четко и без ошибок написать программу по разработанному математиками алгоритму.В команде 3 человека: обычно 2 сильных математика и один кодер.

Вчера общался с Антоном Панкратьевым и Ворожцовым Артемом -  руководителями команд МГУ и МФТИ соответственно. Они говорят, ни одну из этих задач обычный студент и за семестр не решит, поскольку не обладает достаточными знаниями в математике.

Приведу пример задачки. Она, кстати, мне показалась самой простой сначала - но таковой не оказалось, ее мало кто решил.

Перевод с листочка вольный, адаптированный, сокращенный. Извините, выложить фотку не могу - тут очень тупой интернет.

Поиск пароля

Ты - компьютерный взломщик и почти взломал крутейшую систему. Одна проблема - тебе нужен особый пароль, о котором ты знаешь совсем немного.
Известно, что он состоит из [a-z], так же ты можешь узнать его длину и некоторые его части (которые могут перекрывать друг друга). И конечно, не известно где конкретно в пароле они располагаются.

Задача - написать программу, которая из входной информации (длина пароля, некоторые куски пароля, которые могут пересекать друг друга)  будет определять число возможных паролей и если это число не больше 42, то выводить все варианты.

Входные данные таковы, что число вариантов пароля не больше 10^15.

Длина пароля от 1 до 25, число известных кусков пароля - от 0 до 10.

Слабо решить задачку? Кто решит - тому пирожок привезу.
Subscribe

  • Россия-1

  • Спасибо Яндексу

    Ходил сегодня на Маяк — был Live в 9 часов вечера. Спасибо Яндексу, в последнее время какой-то офигительный всплеск интереса к этим утечкам…

  • Гражданская активность и ремонт дорог

    Расскажу историю о том, как любой человек может реально повлиять на качество дорог, по которым ходит и ездит. Месяц назад дорога рядом с моим домом…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 2 comments