?

Log in

No account? Create an account

Previous Entry | Next Entry

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

Вот, например, задача, которую я могу переформулировать для простоты так. Каждое целое число n изоморфно упорядоченному множеству цифр в своей десятичной записи S(n). Найти сумму по модулю 9 всех чисел, изоморфных элементам булеана множества цифр S(n) данного числа n. Например, для числа 123 это (0+1+2+3+12+23+13+123) mod 9. Алгоритм должен работать по крайней мере для n ≤ 1080.

Задача в принципе не сложная. Мне хватило минут 15 на то, чтобы допереть до алгоритма решения. Что меня потрясло, так это то, что трое лучших олимпийцев решили эту задачу за, соответственно, 86, 90 и 96 секунд. В это время вошло чтение задачи — а там несколько абзацев текста с несколькими примерами чисел, придумывание алгоритма и написание собственно кода. Если до того, как я это увидел, у меня еще были некоторые сомнения насчет своих программистских неспособностей, теперь они развеялись окончательно.

Однажды я прочел книгу по пользованию «Фотошопом», где говорилось, что тот, кто не учится работать с этим редактором клавишами, а тыцает в команды мышкой, не имеет никаких шансов на выживание в скоротечном бизнесе редактирования изображений. Сэкономленные доли секунды в пересчете на каждое действие проводят границу между успехом и неудачей.

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

Tags:

Comments

calcin
Dec. 26th, 2011 10:19 am (UTC)
Я бы предложил отследить корреляцию между классом задач и отдельными успешными программистами.
Например, для этой задачи быстро ответит тот, кто просто "умеет" решать данный класс задач.

Для данной задачи:
mod 9 взято для того, чтобы найти не сумму по модулю всех чисел, а сумму по модулю всех цифр этих чисел (10^n всегда даёт в остатке 1 при делении на 9).

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

Кстати, я не очень понял. А что, ограничения на числа нет? Допустим, в вашем примере число 3333333 даёт множество S(3333333) = {'3'}, соответственно, оно также изоморфно подмножеству S(123).
fregimus
Dec. 26th, 2011 10:47 am (UTC)
Множество цифр числа, { 3, 3, 3, 3, 3, 3, 3 } в данном случае. Это разные тройки. Наверное, я не очень хорошо переформулировал задачу.