Занимательные задачки → Картина и гвозди
Имеется картина, к которой двумя концами привязана длинная веревка. Требуется повесить её на N вбитых в стену гвоздей так, чтобы при вытаскивании из стены одного любого гвоздя картина и веревка падали. Веревка имеет пренебрежимо малую толщину, не рвётся и нерастяжима, гвозди не гнутся и перпендикулярны стене, трения нет. Одним словом, задача решается без всяких хитростей и уловок.
Занимательные задачки → Скачки
Задача известная (решение нагуглить можно), но, как мне кажется, достаточно интересная.
У нас есть 25 лошадей, мы должны выбрать из них 3х лучших. Для этого мы можем устроить несколько забегов. В каждом забеге могут участвовать не более 5 лошадей.
Все лошади разные (т.е. никакие две не бегут с одной и той же скоростью), скорость лошади от забега к забегу не меняется.
Требуется минимизировать число забегов.
UPDATE: Время измерять мы не умеем, после забега мы узнаем только порядок участвовавших в нем лошадей.
Формальное описание: есть множество из 25 элементов, на котором задан линейный порядок. За один запрос мы можем узнать часть этого порядка на выбранных нами 5 элементах. Требуется найти 3 минимальных элемента за минимально возможное число запросов.
У нас есть 25 лошадей, мы должны выбрать из них 3х лучших. Для этого мы можем устроить несколько забегов. В каждом забеге могут участвовать не более 5 лошадей.
Все лошади разные (т.е. никакие две не бегут с одной и той же скоростью), скорость лошади от забега к забегу не меняется.
Требуется минимизировать число забегов.
UPDATE: Время измерять мы не умеем, после забега мы узнаем только порядок участвовавших в нем лошадей.
Формальное описание: есть множество из 25 элементов, на котором задан линейный порядок. За один запрос мы можем узнать часть этого порядка на выбранных нами 5 элементах. Требуется найти 3 минимальных элемента за минимально возможное число запросов.
Занимательные задачки → Трансатлантическая линия связи без электричества

Прежде всего, спеша предотвратить гневные возгласы, заявляю: я не знаю решения этой задачи! Точнее так: у меня есть некоторые мысли на этот счет, но красивого и «правильного» решения пока нет. Считайте этот пост возможностью поразмять мозги и почувствовать себя изобретателем.
Итак, условие
Представьте себе цивилизацию, которая достигла нашего нынешнего уровня развития во всем, кроме одного: электричество так и не открыто. Все остальные технологии, не связанные с электричеством, освоены. Физика, химия, металлургия, машиностроение, гидравлика, пневматика, оптика и т.д. — к вашим услугам, а вот даже простейшую батарейку не изобрели.
В таких вот нелегких условиях вам предлагается организовать трансатлантическую линию связи. Естественно, все технологии, так или иначе зависящие от электричества, тоже недоступны (про радио забудьте!). Решение предлагаю оценивать по трем параметрам:
- Время отклика. Если время передачи превышает время пересылки письма пароходом, то такая линия никому не нужна.
- Пропускная способность. Чем выше, тем лучше, 1 бит в сутки никого не устроит :)
- Надежность. Желательно, чтобы передача данных не зависела от погоды, времени суток и прочих прихотей природы. В идеале — линия должна быть доступна в режиме 24/7.
Алгоритмы → Алгоритм нахождения N первых простых чисел из песочницы
В процессе обучения программированию я столкнулся с задачей поиска 1M первых простых чисел.
На Хабре уже не раз писали об этом. Но, чаще всего, речь шла о поиске всех простых чисел до числа N. Я же расскажу о том, как решал задачу нахождения N первых простых чисел.
На первый взгляд может показаться, что разницы в этих задачах практически нет. И это действительно так, пока мы не поймем, что перебор делителей справляется с задачей крайне плохо.
В результате проведенной работы на поиск 1 миллиона простых чисел у меня уходит всего 0,262 секунды, что, конечно же, не предел, но уже впечатляет. Алгоритм реализован на C++.
На Хабре уже не раз писали об этом. Но, чаще всего, речь шла о поиске всех простых чисел до числа N. Я же расскажу о том, как решал задачу нахождения N первых простых чисел.
На первый взгляд может показаться, что разницы в этих задачах практически нет. И это действительно так, пока мы не поймем, что перебор делителей справляется с задачей крайне плохо.
В результате проведенной работы на поиск 1 миллиона простых чисел у меня уходит всего 0,262 секунды, что, конечно же, не предел, но уже впечатляет. Алгоритм реализован на C++.
Блог компании REG.RU → Разыгрывается билет на РИТ++!
Хабровчане, приветствуем!
Мы приготовили очередной сюрприз от компании REG.RU – розыгрыш билета на РИТ++ – главную профессиональную конференцию года. Предупреждаем: на этот раз мы придумали задачу не из легких!
Участникам конкурса нужно предложить лучший вариант оптимизации времени загрузки/отображения главной страницы сайта www.reg.ru. Проявите изобретательность — ведь, безусловно, разработчики REG.RU перепробовали очень многое, и компании удалось найти эффективные решения — как среди стандартных, так и среди нестандартных способов оптимизации.
Мы приготовили очередной сюрприз от компании REG.RU – розыгрыш билета на РИТ++ – главную профессиональную конференцию года. Предупреждаем: на этот раз мы придумали задачу не из легких!
Участникам конкурса нужно предложить лучший вариант оптимизации времени загрузки/отображения главной страницы сайта www.reg.ru. Проявите изобретательность — ведь, безусловно, разработчики REG.RU перепробовали очень многое, и компании удалось найти эффективные решения — как среди стандартных, так и среди нестандартных способов оптимизации.
PHP → Задача при собеседовании на работу в один крупный шведский сайт
Я — PHP-Developer, живу в Стокгольме. Недавно был на собеседовании в один большой шведский сайт (более миллиарда page views в месяц). Интервью проводили 2 программиста из этой фирмы. В определенном моменте, один из них достал листок бумаги и сказал, что предлагают мне решить небольшую задачку (тут же на бумаге, без компьютера). И что у меня есть 10 мин. Попросили так же комментировать каждый шаг.
Скажу сразу, что я ее не решил. Сначала все вроде просто, а потом… Так что, ушел со встречи не солоно хлебавши. С моей стороны она так и осталась нерешенной.
Зачем публикую это? Во-первых, может кому-то пригодится как хороший тест для нанимаемых разработчиков; во-вторых, кто-то, если встретит нечто подобное, будет уже полон знаний; в-третьих, может кто-нибудь поместит правильное решение в коментах?
Ниже — сама задача. Оставляю все в оригинале, как было.
Скажу сразу, что я ее не решил. Сначала все вроде просто, а потом… Так что, ушел со встречи не солоно хлебавши. С моей стороны она так и осталась нерешенной.
Зачем публикую это? Во-первых, может кому-то пригодится как хороший тест для нанимаемых разработчиков; во-вторых, кто-то, если встретит нечто подобное, будет уже полон знаний; в-третьих, может кто-нибудь поместит правильное решение в коментах?
Ниже — сама задача. Оставляю все в оригинале, как было.
Я пиарюсь → Небольшой квест на тему WEB 2.0
Вашему вниманию предлагается интересный двухуровневый квест по тематике информационной безопасности в сфере технологий WEB 2.0.
Сервер: http://46.4.187.243:8080/
Задача:
Минимум – получить часть исходного кода серверной части приложения.
Максимум – добиться выполнения своего кода на стороне сервера.
Задание не типичное и довольно сложное. Успехов в прохождении!
Примечание: сервер слабенький, поэтому использовать автоматизированные средства не рекомендуется. Более того, для решения задания автоматизация не поможет :)
Автор задачи Qwazar. Подробности по ссылке: http://qwazar.ru/?p=68
Сервер: http://46.4.187.243:8080/
Задача:
Минимум – получить часть исходного кода серверной части приложения.
Максимум – добиться выполнения своего кода на стороне сервера.
Задание не типичное и довольно сложное. Успехов в прохождении!
Примечание: сервер слабенький, поэтому использовать автоматизированные средства не рекомендуется. Более того, для решения задания автоматизация не поможет :)
Автор задачи Qwazar. Подробности по ссылке: http://qwazar.ru/?p=68
C++ → Задача-шутка
Это моя самодельная задачка :)
В коде мы пишем дробные числа через точку. Но в некоторых случаях можно извратиться и писать через запятую.
Итак, как заставить работать этот пример так, чтобы можно было записать дробное правое слагаемое (не только 2,1415) через запятую, и получить корректный ответ, как будто оно написано через точку?
Ответ под катом. Напоминаю, что это скорее шутка, и она не представляет практической ценности. Однако ответ по всем правилам C++, то есть без Edit – Replace, и даже без #define-ов.
В коде мы пишем дробные числа через точку. Но в некоторых случаях можно извратиться и писать через запятую.
Float f = 1;
cout << (f + 2,1415); //3.1415
Итак, как заставить работать этот пример так, чтобы можно было записать дробное правое слагаемое (не только 2,1415) через запятую, и получить корректный ответ, как будто оно написано через точку?
Ответ под катом. Напоминаю, что это скорее шутка, и она не представляет практической ценности. Однако ответ по всем правилам C++, то есть без Edit – Replace, и даже без #define-ов.
Занимательные задачки → Нарисуем? Головоло-ломка
Доброй ночи! Пятничная задачка.
Полистав задачки на хабре, вспомнилась одна довольно нетривиальная. Необходимо нарисовать фигуру:

Условия:
(1) нельзя проводить по одной линии два раза
(2) отрывать ручку/карандаш от листа можно только два раза
Проявите креативность! Возьмите друга и поспорьте на пару бутылок пива, кто быстрее!
ПС: существует два известных мне варианта решения, одно наиболее элегантное.
ППС: кто решил, делитесь впечатлениями, но дайте насладиться другим! Не выкладывайте решение сразу!
Полистав задачки на хабре, вспомнилась одна довольно нетривиальная. Необходимо нарисовать фигуру:

Условия:
(1) нельзя проводить по одной линии два раза
(2) отрывать ручку/карандаш от листа можно только два раза
Проявите креативность! Возьмите друга и поспорьте на пару бутылок пива, кто быстрее!
ПС: существует два известных мне варианта решения, одно наиболее элегантное.
ППС: кто решил, делитесь впечатлениями, но дайте насладиться другим! Не выкладывайте решение сразу!
