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

Задача вполне понятная, так что дерзайте.

В задачу вносились изменения: вода, телепорты, борода и суперкамни.

Шахты с лямбдами обнаружены в Шотландии! Ваша задача — прочитав карту шахты суметь составить программу для робота.


Ссылка на красивый симулятор: icfp.stbuehler.de/icfp2012

В обсуждении спонтанно родилась задачка, показалась интересной:

Огромный сервис выполняет запросы, результаты которых кешируются. Выполнение незакешированного запроса в десятки тысяч раз дольше, чем закешированного. Однажды что-то слегка испортилось, и процент попаданий в этот кеш упал с 99% до 98%.

Раньше сервис работал на 100 абсолютно одинаковых серверах. Сколько серверов потребуется теперь?

PS: задача не совсем строго сформулирована, но это не должно сильно мешать её решить :)

Думаю, вы в курсе, что Microsoft обвинила TomTom в нарушении ряда патентов. В своём пресс-релизе MS заявляет: «TomTom уважаемая крупная компания. Мы рассчитываем быстро разрешить это неприятную ситуацию»

Посмотрел я, в нарушении чего обвиняют TomTom. И теперь рассчитываю, что уважаемая компания TomTom засудит «Корпорацию Зла» по полной программе. Ведь среди нарушенных патентов есть эти:

6,175,789: патент на установку ПК под управлением многозадачной ОС в автомобиль

6,202,008: патент на установку ПК оборудованного wireless доступом в автомобиль

7,054,745: патент на разработку ПО, которое даёт указания водителю «поворот-за-поворотом»

5,579,517 и 5,758,352 — VFAT и длинные/короткие имена файлов.

[… патенты 6,704,032 7,117,286 6,256,642 пропущены, т.к. я ничего не понял :-)… ]

Кстати, по американским законам каждая сторона несёт расходы на ведение дела самостоятельно, независимо от исхода. Так что денег с TomTom всё равно отожмут.

И ещё: насколько я знаю, в США патентуют всё что угодно, но часть патентов признаются ничтожными, обычно с обоснованием «такое уже было до» (prior art)

Публикую в блоге Microsoft в надежде, что мне сейчас пояснят, почему MS белый и пушистый. Тут должны же быть защитники.

PS: Нежнее с кармой, ей больно!

update: анализ Брюса Перенса и его частичный перевод (thx to tzong)

Люблю задачки с картинками:

В игре дартс игрок бросает 3 стрелки в мишень, разделённую на двадцать секций одинакового размера, пронумерованный от одного до двадцати.

Типография выполняет 16 задач каждую неделю, причём для каждой задачи требуется лист специальной фотобумаги размером A5.

Каждый понедельник мастер достаёт новый лист формата A1.

Он разрезает лист пополам, получая два листа формата А2. Затем режет только один из них еще раз, получает два листа А3 и так далее, пока не получит необходимый для первой печати формат А5.

Все остальные листы запихивает в тумбочку.

Одна из самых сложных для меня задач из более чем 100 решённых:

Существует несколько способов записать число 1/2 как сумму обратных квадратов используя различные натуральные числа.
Например, можно использовать {2,3,4,5,7,12,15,20,28,35}:

Фактически, используя только целые между 2 и 45 включительно, есть только 3 возможности записать 1/2. Оставшиеся два это: {2,3,4,6,7,9,10,20,28,35,36,45} и {2,3,4,6,7,9,12,15,28,30,35,36,45}.
Сколько существует способов записать ½ как сумму обратных квадратов различных целых чисел между 2 и 80 включительно?

PS: Я из блога своего сразу 3 старых перевода запостил, а так спаммить не буду ;-)

Яндекс включил показ зелёных стрелочек на основной странице пробок Москвы. Этот сервис был давно доступен на телефонах, но посмотреть на большом экране всегда приятно. Зелёная стрелка — «след» быстро ехавшего человека с мобильным клиентом и GPS.

Да, пока куча недостатков: их нельзя отключить, их мало (иногда на телефоне я видел свой маршрут по Москве целиком), они не умеют как-то отличать мотоциклистов (но это вопрос роста количества источников).

Но всё равно, сервис великолепен, именно за таким слежением будущее. Вот только не знаю, с кем бы мог яндекс договориться и поставить датчики для набора массы? Грузоперевозчики? Автобусы-Троллейбусы? Маршрутки? Такси? Или просто ждать, пока нарастёт масса обычных людей?

Update: А как думаете, если стрелочками нарисовать неприличное слово, меня забанят как источник?

1. Вот только что промахнулся по стрелке и попал по .

Почему бы не сделать так:

5 баллов, зачем этот pixel hunting?

2. Думал, куда бы запостить про п.1 Вспомнил, что есть что-то типа: «Идеи для хабра». Долго не мог найти «Список всех блогов» на главной странице, пока не догадался нажать на стрелочки с топом.

А есть такое правило: если я чего-то не могу найти 2-3 минуты на сайте, значит половина «обычных пользователей» не найдёт никогда :-) Аль нет тут «обычных пользователей»?

Сегодня зарелизили версию перлового клиента для memcached близкую к окончательной. Багов не замечено. Работает на боевых серверах beon.ru. По бенчам превосходит по скорости все аналогичные модули (как пишут в рекламе, «до десяти раз быстрее»)

wiki проекта

Приятно, когда коммерческие проекты выкладывают хорошую работу в open source!

НПП «СЕМИКО» занимается полезнейшим делом: продвигает в школы новейшую разработку — МК-152.

Для тех, кто забыл или не знал, что такое МК-52, небольшая цитата с сайта:
Программа для решения задачи занимает 17 байт:
ИП1 B↑ ИП2 × П1 ↔ ИП3 + ИП4 + П4 FL0 00 6 0 ÷ С/П

Перед запуском нужно записать исходные значения в регистры памяти:
R0 = 40 (число рыб);
R1 = 5 (время на поимку первой рыбы);
R2 = 1,05 (коэффициент увеличения времени — 105%);

R3 = 2 (время на перекладывание);
R4 = 0 (начальное значение времени на переселение).

Для запуска программы нажать В/О, С/П. Через 0,5 с на индикаторе появится результат — 11,399981 мин. Если есть необходимость пересчитать доли минуты в секунды, нажмем «К Г→М» и получим приблизительно 11 минут 24 секунды.
[...]
Аналогичная программа на Си не намного нагляднее и для выполнения потребует запуска компилятора. Для сравнения, ее текст приведен ниже.

#include <stdlib.h>
main() { int j, r0=40; double r1=5,r2=1.05,r3=2,r4=0; for (j=0; j<r0; j++) {r4+=r1+r3; r1*=r2;} fprint(«Время: %d мин.\n», r4/60); }

PS: В комментах напомнили и я решил добавить про ЕГГОГИ, ЗГГОГИ, тьму и прочее. Но в МК-152 микропрограмма другая, поэтому чудовища народятся свои, уникальные.