Пожилой чекист спрашивает молодого "Знаешь, какое наше самое главное оружие, на букву Н" - хм... Наган? нет... может, Наручники? тоже нет... а что же? - Балда ты, наше главное оружие есть Нтеллект!

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

Итак, здесь частенько всплывают вопросы типа "какую IDE вы рекомендуете/используете" и немного реже вопросы по поводу "какую ОС". Однако компьютер, ОС и компилятор любимого языка это лишь необходимый минимум того, что нужно программисту по жизни. Есть ещё несколько вещей которые и полезны в личном обиходе - и которые (если их употребить в качестве волшебных слов на самом первом собеседовании) заставят работодателя относиться к вам с бОльшим доверием.

Хотя не следует ждать, что если только вы освоите что-то из нижеперечисленного, то у вас тут же рейтинг поднимется и ник покраснеет. Нет. Просто, возможно, это поможет вам лучше организовать свою учёбу, свои разработки и т.п... ;-)

Системы контроля версий

А где мы храним свои исходники? В папочке, на флешке? Этот подход хорош только тем что он кажется естественным, однако рассмотрим пример: при участии в марафоне, или другом длинном соревновании (типа google ai-challenge) копятся десятки версий вашей программы - в таком случае порой очень хочется уметь быстро найти старую версию, сравнить исходники разных ревизий, отделить разработку какого-то сложного/спорного функционала в отдельную ветку, или вновь состряпать из нескольких веток одну новую и т.п.

Или если вы работаете над небольшой программулиной, проектом более чем одной парой рук - носить файлы друг другу на дискетке, конечно, архаично - но не менее архаично кидать их в общий сетевой каталог, спрашивая "а этот файл ты менял? нет, ну тогда я его затру!" (хотя есть ещё даже целые конторы которые до сих пор на флешках-папочках живут - ну это называется "мужественно создаём себе трудности и мужественно их преодолеваем!")

В профессиональной деятельности такие вопросы возникают вообще постоянно. Ну вот тут мы и приходим к использованию систем контроля версий.

Я не собираюсь описывать как с ними работать - на это есть громадные тюториалы и мануалы. Обычно всё это выглядит так: исходники (разных версий) хранятся в отдельном хранилище (репозитории), откуда вы себе для работы извлекаете нужную ревизию файлов (checkout), а потом, поработав с ними в своё удовольствие, можете сохранить обратно в репозиторий (commit). При этом до коммита вы можете сделать несколько полезных действий:

* update - обновить свои исходники (возможно уже изменённые) новыми версиями из репозитория, если ваш коллега успел там что-то поменять (или вы сами на другом компе поработали над частью проекта в выходные у бабушки, скажем);

* revert - заменить свои локальные изменённые исходники на оригинальные их версии из репозитория если поняли, что сделали что-то не то (таким образом все сделанные изменения будут убиты);

* diff - сравнить свою локальную версию с той что в репозитории (построчно, возможно с выделением цветами и т.п.);

* log - посмотреть сообщения сделанные при сохранении предыдущих ревизий

* и кстати, самому оставить вменяемое сообщение при коммите (например "исправлен баг описанный в тикете № 1529" - см ниже).

Главное то, что всё, что однажды сохранено в репозиторий, впоследствии в нём можно найти (и хранится это в достаточно эффективном по объёму виде). При этом использовать такие системы не обязательно для больших проектов. Можно завести в репозитории отдельные папки например, для задач с тимуса, CodeForces, ProjectEuler и т.п. - даже если большинство файлов будут иметь единственную ревизию, это всё равно будет удобно.

При этом вам не обязательно разворачивать систему контроля версий у себя на компьютере - можно пользоваться готовыми хранилищами в интернете (FreePository, Assembla) и т.п. Но можно и развернуть (это не очень сложно, однако вы можете обнаружить что вам нужно установить и веб-сервер типа Apache httpd, что впрочем тоже не так страшно, как звучит). Необходимым является только клиентский интерфейс, который позволяет пользователю "общаться" со своим репозиторием. Кстати в большинстве современных IDE уже встроены, как в NetBeans (или в виде плагинов, как в Eclipse) возможности для работы с популярными системами контроля версий. Ну кроме того в большинстве систем есть возможность доступа по http - т.е. можно зайти в репозиторий браузером и посмотреть что у нас там творится.

Какие системы наиболее употребимы? Пожалуй, CVS - хотя он сейчас считается малость устаревшим, потом SVN (Subversion) и Git. Нужно вводить в гугле "учебник по SVN" например и смотреть, как им пользоваться (имеет смысл делать это на языке который вам понятен). Под виндовс существуют очень удобные клиенты TortoiseSVN (TortoiseCVS, TortoiseGIT) - они прямо в проводнике помечают изменённые файлы красными флажками, неизменённые зелёными и т.п. (в учебниках вы найдёте кучу поясняющих картинок). В linux часто используется набор клиентских утилит для командной строки - ну они требуют привычки для использования, хотя тоже всё не так страшно, как звучит.

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

Я лично сторонник SVN т.к. он сейчас довольно распространён и он есть на всех сервисах управления проектами которыми мне приходится пользоваться, впрочем всё может потихоньку измениться. Многие утверждают что Git это неимоверно круто. Посмотрим как-нибудь.

Кроме того рекомендовал бы, если нет опыта, не начинать знакомство с клиентов, встроенных в IDE (а то можете либо поломать голову, либо развить в себе неадекватные навыки - коммиты по одной ревизии на каждый файл и т.п.), а попробовать сначала отдельный (например TortoiseSVN, т.к. он наглядный).

Эти умения (и клиентские программулины) зачастую понадобятся вам и в тех случаях когда вы захотите поучаствовать в чужих проектах.

Картинка: Windows Explorer показывает папку, находящуюся под версионным контролем - TortoiseSVN расставил забавные флажки у папок. Открыто меню TortoiseSVN, встроенное в контекстное меню проводника.

Картинка: blame в TortoiseSVN - этот режим позволяет посмотреть для данного файла, кто и когда в нём какую правку вносил (см. номера ревизий слева), можно также копнуть и посмотреть что было в этой строке раньше и т.п. - классная вещь когда непонятно, кто накосячил или зачем этот кто-то это сделал (в частности сейчас виден комментарий автора, сделавшего данную правку, к коммиту с которым он сохранил этот файл в репозитории).

Багтрекеры

Точнее "Issue Tracker-ы". Не знаю стандартного перевода для термина. Это системы для исключительно банальной цели, которую многие однако недооценивают.

Допустим, я добавляю функционал в проект и вдруг замечаю, что где-то сбоку, при специфических обстоятельствах выскакивает дурацкая ошибка. Должен ли я сразу кидаться её исправлять?

В общем, нет. Я открываю багтрекер, создаю новый тикет "баг" и пишу в нём "Если в форме такой-то поле Имя длиннее чем столько-то символов, то приложение падает.", устанавливаю важность "пустяк" и жму кнопку "сохранить".

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

Впоследствии когда я не могу вспомнить чем заняться, я открываю трекер и вижу список недоделок или пожеланий. Выбираю из них либо самое важное, либо самое простое, делаю, проверяю, сохраняю (при работе в команде возможно проверяет другой человек) и пишу в соответствующий тикет "сделал так и так, сохранил в репозитории в ревизии 237". После чего тикет "закрываю" (resolve) так что он в дальнейшем не отображается в списке насущных задач.

Полезно держать несколько трекеров - скажем, по одному для каждого из насущных проектов и отдельный, допустим, для задач о которых вы где-то слышали и хотели бы когда-нибудь попробовать порешать, но сейчас у вас нет времени или скиллов. Да хоть для покупок в магазине, которые приходится пока отложить на потом... ;-)

Удобный трекер обычно может иметь веб-интерфейс (так нескольким человекам легче работать с одним трекером - просто в браузере набрали его адрес и ура), возможность делать ссылки между тикетами или назначать одни тикеты дочерними для других. Кроме того, как уже ясно, многие любят использовать трекер который удобно совмещается с любимой системой контроля версий. Это не очень принципиально, но тоже полезно. Некоторые трекеры содержат в себе wiki, к другим её можно подключить. Большинство трекеров позволяют кастомизацию в широких пределах (нам обычно хочется лишь привести вид к симпатичному, отредактировав css-файл).

Какой трекер использовать? Они существуют как для огромных команд, так и для небольших, в т.ч. единоличных. Правда, большинство из них используют в качестве хранилища какую-либо из известных БД.

Если интересно повозиться с настройкой трекера самому, можно попробовать Mantis, Trac или RoundUp. Первый из них на PHP, остальные два на Питоне (при этом эти два могут использовать встроенную БД, так что её не придётся настраивать отдельно - хотя запустить mysql сервер и создать в нём базу - прямо скажем не ахти какая задача). Трекеров на Java свободных мало, желающие могут поэкспериментировать например с JTrac (или вот популярная JIRA предлагает себя всего за 10долл для маленьких проектов либо бесплатно для опенсорсных?).

Я сам имел дело с разными багтрекерами (mantis, bugzilla, redmine, trac, jtrac) - но когда выбирал для личных потребностей, то скачал RoundUp - мне оказалось его легче настроить, кроме того на сервере, где я его размещал, не было возможности использовать существующую СУБД, а отдельную под багтрекер заводить не хотелось и притом интерфейс мне не показался слишком отвратительным с первого взгляда (особенно когда я слегка поправил стили). Возможностей у него не ахти как много, но внутренние ссылки я наконец нашёл а это одно из самых важных.

Кроме того можно взять "hosted" трекер - т.е. размещённый в интернете и поддерживаемый какой-то конторой, позволяющей завести бесплатно несколько трекеров под собственные проекты. Типичный пример Unfuddle. Если же вы разрабатываете проект на каком-то из известных ресурсов типа SourceForge, то вы скорее всего найдёте здесь встроенные трекер и репозиторий для своих целей.

Картинка: список тикетов в Mantis - цвет означает состояние (открыт, отработан, возвращён и т.п.). Видна также "серьёзность" задач и к какому проекту они относятся (мантис позволяет сразу несколько проектов видеть).

Картинка: список тикетов в RoundUp (по умолчанию группировка по важности - видно, кто создал и на кого назначил задачу).

Картинка: просмотр тикета в RoundUp, видны сообщения, добавленные в разных стадиях работы и история изменения тикета. Видно что цвета, шрифты и т.п. несложно поменять на приятные/кислотные, ненужные поля (типа "зарегистрироваться) удалить и т.п. а ссылка на другой тикет появляется сама если вписать "issue #" (или "msg #" - ссылка на конкретное сообщение к тикету).

Для иных разработчиков иметь аккаунты в нескольких общественных багтрекерах и репозиториях так же естественно как иметь аккаунты в почте и соцсети. Если вы используете подобные софтины (не на работе!), то отпишитесь в комментах о своих предпочтениях.

P.S. Думал, стоит ли в связи с багтрекерами отдельно написать о СУБД, раз уж их можно использовать не только для багтрекера (ха-ха) но и для своих разработок, даже небольших - но что-то подсказывает что это уж совсем будет тупо, общеизвестно и значительно менее актуально.

Думаю, в силу известных обстоятельств, все уже слышали про MemSQL. ;-)

На столе лежат в ряд палочки. Можно брать одну палочку или две соседних. Тот кто берёт последнюю проигрывает.

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

Пример:

начальная позиция:
XXXXXX
После хода игрока А
XX__XX
После хода игрока B
XX___X
После хода игрока A
______X
Игрок B берёт последнюю и проигрывает.

Очевидно, что любая позиция может быть либо выигрышной (если существует ход переводящий её в проигрышную), либо проигрышной (если любой ход делает её выигрышной). Пример проигрышной позиции 1 палочка, пример выигрышной - пустой стол.

Стратегия игры очевидно напрямую связана с возможностью определять выигрышность позиции.

Требуется внятный алгоритм определения выигрышности позиции. Мне он неизвестен. Статьи по такой именно игре вроде есть в сети, но они не обязательно описывают алгоритм (или не обязательно в доступных терминах). Буду рад помощи!

Кстати, с интересом заметил что рейтинг всех моих старых постов находится на уровне минус 200-300 баллов. По-моему даже JKeeJ1e30 такого не удостаивался. Польщён, весьма польщён! (Вот соплежуям озорникам некуда технический гений направить!) :D

UPD: вижу что случилось какое-то массовое обнуление "вкладов". Чем дальше, тем любопытственнее.

Всем добрый день.

Существует ли возможность узнать статистику использования языков программирования на CF (ну скажем как процент отосланных решений на тех или других языках).

Интересуют соотношения по категориям:

- среди участников использующих русскоязычный / англоязычный интерфейс;
- среди соревнующихся из Div1 / Div2;
- по всем успешным / по всем отосланным задачам.

Анализы типа http://codeforces.net/blog/entry/1917, а также  вроде "статистика среди учеников нашего препода" или комменты вроде "а я счетаю лутшым езыком Scala патому што это убудущее" не очень интересуют. ;-)

UPD: Попробовал сохранить страничку standings.htm с 85 раунда и постучать по ней egrep-ом. Это (я надеюсь) позволило мне определить количество задач, сдававшихся на тех или иных языках (не обязательно сданных):

Div1: C++ 1372, Java 130, Pascal 94, Python 16, PHP 2

Div2: С++ 2990, Java 370, Pascal 447, Python 123, PHP 3

Вот что-то вроде этого и хочется, только более полно и с учётом остальных категорий... (Pascal = Delphi | FPC)... %)

Как вы считаете, имело бы смысл попытаться урегулировать использование двойных (и более) аккаунтов?

Например ввести правило что если человек использует несколько аккаунтов, то все они должны иметь ссылки друг на друга.

Я полагаю что:
- если кому-то нужен второй аккаунт в достойных целях (например для совмещения административной и спортивной деятельности), для него нет проблемы указать связь между аккаунтами;
- а если цели достаточно недостойные и такую связь хочется скрыть - то возможно тогда дополнительные аккаунты этого человека с точки зрения сообщества являются злом которое нужно пресекать?

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

Несмотря на то что мега-существенных нововведений в Java 7 к нам не пришло, всё-таки любопытно, начиная с какого из следующих контестов в решениях можно будет использовать то немногое новое, чем товарищи из Оракл решили нас порадовать.

Или уже?

Итак нынче мы наблюдаем проявления троллинга в лице человека, вероятно обиженного коллегами, сверстниками, преподавателями и т.п. Не вдаваясь в рассуждения о причинах его поведения, хочу ещё раз (ещё, ещё!) обратить внимание на то, как бы нам изжить такие проблемы. Резюме моего поста в том что Профессиональному обществу нужны профессиональные инструменты для общения.

Я не хочу сказать дурно о разработчиках ресурса. Многие решения хороши, или были хороши какое-то время назад. Но очевидно требуется развитие, модификация.

В блоге 20 причин... прозвучало:

Тролли приживаются когда можно создавать бурные обсуждения из ничего. А учитывая то что было например в теме "Брак по расчету", можно сказать что люди здесь любят пообсуждать нетрадиционную ориентацию, и другие щекотливые темы

Уважаемые товарищи!

Буду очень признателен если кто-то более умный чем я подскажет оптимизацию алгоритма.

Постановка задачи

Фрагменты строки сравниваются с фрагментами образца с применением нечёткого сравнения.

Входная строка текста разбивается на фрагменты (например, на отдельные слова) и дальше рассматривается как последовательность таких слов:
[T1, T2, ..., Tn]

Образец (шаблон) для сравнения может содержать элементы 3 типов (возможно, вложенные):
1. "Простой" - представляется как последовательность символов в кавычках - например, "стол" - и сравнивается с одиночным словом, давая результат от 0.0 (совсем непохожи) до 1.0 (идентичны).
2. "Последовательность" - представляется как набор дочерних элементов, разделённых запятыми, например "стол", "стоит", "у", "стены". Сравнивает по порядку следования дочерние элементы со словами входного текста.
3. "Выбор" - представляется как набор дочерних элементов разделённых символом "|", например "стол" | "буфет" | "кровать".

Пример сложного шаблона:
("стол" | "буфет" | "кровать"), "стоит", (("у", "стены") | ("на", "полу"))

Как найти результат сравнения со сложным шаблоном?

Естественным казалось ввести такие правила:
а) Результатом "Последовательности" является среднее геометрическое результатов дочерних элементов.
б) Результатом "Альтернативы" является максимальный из результатов дочерних элементов.

Однако возникает проблема в шаблонах содержащих вложенные "последовательности", например:
( "bla" | ("ola", "gde") ) , "chmoda"
Сравним это с "bla ide chmoda" - тогда "альтернатива" выберет лучшим вариант "bla" т.к. он даёт 1.0 тогда как "ola", "gde" даёт только 0.66, однако после этого остаток строки составит два слова "ide chmoda" и сравнение с просто "chmoda" даст для них 0.0, и общий результат будет 0.0.
В то же время, если был бы выбран для "альтернативы" второй вариант, то остаток строки сравнился бы идеально и общий результат был около 0.76.

Простая идея - перенумеровать все простейшие элементы в шаблоне:
("bla"=E1, "ola"=E2, "gde"=E3, "chmoda"=E4)
И построить все возможные варианты сравнения:
E1:T1, E4:T2
E2:T1, E3:T2, E4:T3
Если теперь вычислить среднее геометрическое результатов, приняв T1=bla, T2=ide, T3=chmoda, то мы конечно найдём оптимальный вариант.

Однако это неэффективно, т.к. например:
("bla"|("ola","gde")),("xyz"|"pur"|"lti")
здесь будет уже 6 вариантов, но для строки "bla ide xaz" сравнение "pur" или "lti" с "xaz" дало бы 0.0, и если определить это заранее, то 4 из 6 вариантов можно было бы не рассматривать (тк. ср. геометрическое всё равно будет 0.0). Но как такие вещи "определять заранее"?..

В общем, буду благодарен светлым головам... Также будет неплохо если кто-то укажет что задача сводится тем или иным образом к какой-то из известных...

с уважением,
Родион

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

Всплыла тема. Давайте её пилить отдельно... %)

Для IT-шника(-цы) обсуждаются несколько возможностей по выбору себе невесты (жениха):
- чтобы она (он) тоже был(а) IT-шницей(ком), причём, со схожим направлением деятельности;
- либо то же самое, но с как можно более отличающейся "деятельностью", например, программист(-ка) + тестировщица(-к) это модель идеальной семьи;
- либо профессионал из другой области науки/искусства (правда ряд инженерных профессий непонятно как расценивать - как IT-шные или нет);
- либо непрофессионал (ну их на фиг, людей увлечённых!)

Сам я в своё время над разными вариантами, в основном среди двух последних, размышлял - и теперь с профессиональной точки зрения у нас с супругой общее лишь то, что мы занимаемся преподавательской деятельностью (правда она - профессионально, а для меня это night-job). В остальном же различия капитальны. Я ей помогаю бороться с антивирусами и браузерами - она же меня учит записывать подобранные мною мелодии в Сибелиусе и умеет растолковать "пачиму тут не 3/4 а 6/8"... Ну а то, какие ученики-школьники теперь ленивые (в среднем) мы можем обсуждать вместе... %)

Так что кто в браке состоит или собирается когда-нибудь состоять, вкратце можете приписать свои мысли... Забавнее всего, впрочем, будет лет через 5-10 их перечитать... %)

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

Задан образец некой фразы, состоящей из нескольких слов
p1 p2 ... pN
С ним сравнивается фраза, из такого же количества слов
w1 w2 ... wN
Т.е. слова разделены пробелами или ещё чем нибудь, не важно - и мы просто сравниваем каждое слово w с соответствующим по порядку образцом p. Результатом такого сравнения является, какой-то критерий e, например, количество опечаток (от 0 до length(p)) - или в принципе какая-то "похожесть" в промежутке [0, 1]... или ошибочность (в том же промежутке... или от 1 до +inf... Критериев можно много придумать и их несложно друг из друга получить... В общем, будет у нас N оценок:
e1, e2, ... eN.

Так вот. Вопрос в том - как оценить "похожесть" (или "релевантность") полного образца (из N элементов) и целой фразы (из N элементов).

Например, сначала я использовал для соответсвия слова элементу образца критерий "ошибочность" (от 0.0 до 1.0) и для фразы в целом брал "ошибочность" как max{e}.

Однако, получалось что если скажем у меня четыре слова, и три из них без ошибок, а в одном ошибочность равна 0.5, то фраза целиком не проходила, если порог установлен например 0.3.

Тогда я стал считать их среднее геометрическое. Точнее среднее геометрическое величин, дополняющих "ошибочность" до 1 (назовём это "похожестями"):
e_total = 1 - (П(1-e_i))^1/N

С этой оценкой хорошо то, что если одна из "ошибочностей" равна 1.0, то и общая ошибочность тоже будет 1.0, а если все "ошибочности" равны, то общая "ошибочность" равна ошибочности каждого из элементов.

Теперь однако выходит что если, например, сравнивается фраза из 3 слов и из них два безошибочны, то третье может иметь ошибочность около 0.65... Т.е. в общем оно может оказаться почти непохожим на элемент образца.

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

Так что буду рад и благодарен любым подсказкам, советам, идеям и возражениям.

Ещё одна старая задача на теорию вероятностей. Немного видоизменю её чтоб гугловому поиску не мешала.

В кабачке на Марсе зелёные человечки имеют возможность сыграть в простую азартную игру. Крупье бросает 6 одинаковых игральных костей в форме додекаэдров (правильный 12-гранник с 5-угольными гранями). Каждый из играющих перед этим загадывает одно из чисел, присутствующих на гранях (скажем, от 0 до 11). Если загаданное игроком число не выпало ни на одной кости, он платит крупье 1 евро (да-да, и туда добрались!), в противном случае крупье сам платит игроку столько евро, на скольки костях выпало загаданное число (т.е. от 1 до 6).

Определить требуется, конечно, матожидание выигрыша крупье после того как он сыграл, скажем, с миллионом желающих. Кости совершенно честные (т.е. каждая грань выпадает с равной вероятностью 1/12).

Более простой вопрос - кто на ваш взгляд будет выигрывать (при большом числе игр) - крупье или игроки.

Провёл опрос среди коллег и учеников. Посмеялся.

Часто, рассказывая о бинарном поиске (дихотомии) авторы, преподаватели, учителя, менторы и тьюторы упоминают что существует вариант при котором отрезок поиска делится не пополам а в отношении "золотого сечения". Правда не припомню, чтобы они объясняли в каких случаях и зачем это нужно.

А вы знаете?

Можете просто ответить - знаете или нет. Объяснение я хотел под катом привести, но он как-то не очень работает.

Однако если вы не знаете объяснения - попробуйте догадаться. Пожалуй стоит намекнуть что область применения - поиск не по массиву значений (вспомните когда ещё нужен двоичный поиск).

Не секрет, что существуют два противоположных взгляда на олимпиадное (спортивное?) программирование:

Первый из них - почёт и уважение лучшим, вплоть до благоговейного трепета.

Второй взгляд часто - вот де, зачем это надо, получаются гениальные горе-программисты которых трудно потом переучить для работы в нормальной конторе разработчиков.

Помню, когда я впервые устроился работать в одну из контор, разрабатывающую банковское (и вообще коммерческое) ПО, я был поражён примерами кода - проверки и логгирование ошибок для каждой строки, идентификаторы по 50 символов длиной, префиксы различных видов имён и т.п. Пояснения для потомков, доксижен, пространные комменты в системе контроля версий и багтрекере.

Ну и когда я впервые разглядывал исходники сильных спортсменов с топкодера, скажем - я тоже поражался. Некоторым текстам даже обфускатор уже не понадобится - естественно, ведь автор справедливо осознаёт что написать нужно быстро, а возвращаться к этому коду ему вряд ли понадобится.

Сам я ни с тем ни с другим мнением отдельно согласиться не могу. Считаю что и "профессиональные" программисты должны знать что существуют алгоритмические задачи посложнее двоичного поиска - и спортсмены должны примерно представлять сложности "профессиональной" разработки.

Впрочем обсуждать это всё долго, да и много на эту тему говорилось, даже здесь, по блогам уважаемых людей:
http://codeforces.net/blog/entry/1851
http://codeforces.net/blog/entry/2047
и т.п.

Среди своих знакомых - профессиональных разработчиков - я с удивлением не нашёл никого, кто хоть когда-то заходил бы на популярные ресурсы связанные с олимпиадным программированием. Теперь хочу узнать "обратную сторону" вопроса. Так что просто поделитесь (если не тайна):

- работаете ли вы программистом/тестировщиком, и т.п. (если да, то как часто доводилось заниматься интересными алгоритмическими задачами - мне, скажем, раза 4 за два года, притом больше околоматематическими алгоритмами);
- работаете ли вы "математиком/аналитиком-программистом" (или как называется ваша должность) - т.е. человеком который на практике занят разработкой, модификацией или внедрением достаточно неординарных алгоритмов в проектах;
- работаете ли вы в решительно иной отрасли (в инженерной - или нет?);
- либо не работаете пока вообще, но собираетесь (или не собираетесь) работать в IT, даже с учётом того что "интересных задачек" там отнюдь не так много и достаются они обычно либо лучшим, либо везучим... ;-)

Заранее спасибо.

По просьбе freopen.

В селе живут девушки-пастушки. В рамках здоровой конкуренции они подкладывают друг другу свиней. Подложенную свинью девушка должна распознать, при этом распознавание каждой следующей свиньи происходит за время на q процентов меньшее, чем предыдущей. Время распознавания 1-й свиньи девушкой будем называть профессионализмом девушки p (чем меньше, тем лучше).

(Если девушке подкладывают свинью, геометрически идентичную одной из предшествующих, то она распознаётся за время 0. Т.о. задача рассматривает только геометрически различных свиней. Свиньи похожие с точностью до отражения/поворота - идентичны.)

Итак, есть набор K девушек с разным количеством измерений. Размерность каждой девушки - целочисленная, при этом наименьшая 2, наибольшая K+1.

N-мерной девушке нужно подкладывать только N-мерную свинью. Такая свинья состоит из N+1 органов, которые мы в рамках задачи не различаем. Органы имеют форму N-мерного куба со стороной 1 и в составе свиньи они соединены N-1-мерными гранями. Если у свиньи есть хотя бы одна ширина меньшая 2, то такая свинья дефектная и не участвует в задаче т.к. не может считаться полностью N-мерной.

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

Входная строка содержит числа K и q (int и double). Выходная должна содержать K чисел (double) показывающих, какой профессионализм должна иметь каждая из девушек (по порядку возрастания размерности девушки) чтобы победила дружба.

Выдать любое решение с точностью до 1e-9. K меньше 15, q меньше 100 и кратно 10.

Пример:
2 50
15 10

Вариант: выдать решение с точностью до 1e-3.

Указания на неудачность формулировок и возможные коррективы принимаются благожелательно.

Нашёл здесь среди спортсменов несколько своих учеников. Позабавило. В связи с этим вспомнил задачу которую давал некоторым поколениям в качестве одного из тестов на вступительном испытании на мой спецкурс.

На поле девушки пасут свиней. При этом всего насчитывается 106 ножек и 336 сисек. Сколько голов?

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

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

Решение подписывать не стоит т.к. оно очевидно. Ответ тоже... Просто проверьте себя при желании (и наличии чувства юмора)... ;-)

Идея возможности взлома во время, пока другие участники ещё решают задачи, мне кажется внове.

На topcoder это мероприятие вынесено в отдельную фазу, когда отсылать задачи уже нельзя.

А тут я сразу задумался. Уж наверняка если можно видеть чужие решения во время соревнования, то либо никто не догадался использовать это для читинга (с двумя логинами на одного человека или с пару "компаньонов") - либо же 21-й век накладывает свой отпечаток на моральные качества людей и все, хотя и догадались, но никто, безусловно, не опустился до такого жульничества...

Прав ли я, полагая, что всё действительно безоблачно - или существуют уже известные прецеденты на эту тему? Если прецеденты есть - как Вы полагаете - лучше было бы выделить взломы в отдельную фазу, после фазы решения - или нет.

(я не имею в виду что topcoder добился высот в борьбе с мошенничеством - там свои проблемы есть, но от этого не лучше, ведь так?)

Хотя не могу не признать что мне пока от возможности "взлома" только позитив - благодаря тому что какой-то доброжелатель нашёл своевременно ошибку в моём решении, я (поначалу, конечно, вытаращив от удивления глаза) подумал и смог догадаться где допустил (идиотский, спору нет) косяк... А впрочем - как Вы считаете - такая возможность, увидеть что тебя взломали - и исправиться - она накладывает ли положительный или отрицательный эффект на "корректность" соревнования?