Pull to refresh
66
0

User

Send message

Задача конкурса ICFPC-2012: робот и λ

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

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

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

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


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

Подробная спецификация
Total votes 35: ↑31 and ↓4 +27
Comments 15

О важности кэшей в IT

Reading time 1 min
Views 605
В обсуждении спонтанно родилась задачка, показалась интересной:

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

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

PS: задача не совсем строго сформулирована, но это не должно сильно мешать её решить :)
Total votes 8: ↑7 and ↓1 +6
Comments 27

Microsoft vs. TomTom: корпорация зла атакует?

Reading time 1 min
Views 2K



Думаю, вы в курсе, что 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)
Total votes 126: ↑105 and ↓21 +84
Comments 209

Задача №109

Reading time 2 min
Views 1.1K
Люблю задачки с картинками:

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



Читать дальше →
Total votes 7: ↑4 and ↓3 +1
Comments 6

Задача №151

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

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

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

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


Читать дальше →
Total votes 4: ↑1 and ↓3 -2
Comments 1

Задача №152

Reading time 1 min
Views 624
Одна из самых сложных для меня задач из более чем 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 старых перевода запостил, а так спаммить не буду ;-)
Total votes 7: ↑2 and ↓5 -3
Comments 1

Пробки 2.0 теперь и в браузере

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

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

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

Update: А как думаете, если стрелочками нарисовать неприличное слово, меня забанят как источник?
Total votes 32: ↑31 and ↓1 +30
Comments 49

Стрелочки у голосовалки за пост и список блогов

Reading time 1 min
Views 662
1. Вот только что промахнулся по стрелке up и попал по down.

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

не нравится5 балловнравится, зачем этот pixel hunting?

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

А есть такое правило: если я чего-то не могу найти 2-3 минуты на сайте, значит половина «обычных пользователей» не найдёт никогда :-) Аль нет тут «обычных пользователей»?
Total votes 128: ↑121 and ↓7 +114
Comments 50

Cache:: Memcached:: Fast 0.08

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

wiki проекта

Приятно, когда коммерческие проекты выкладывают хорошую работу в open source!
Total votes 24: ↑21 and ↓3 +18
Comments 8

ЭВМ в СССР, 16 лет спустя

Reading time 1 min
Views 835

НПП «СЕМИКО» занимается полезнейшим делом: продвигает в школы новейшую разработку — МК-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 микропрограмма другая, поэтому чудовища народятся свои, уникальные.
Total votes 22: ↑20 and ↓2 +18
Comments 66

Information

Rating
Does not participate
Location
Россия
Date of birth
Registered
Activity