Я придумал метод решения экспоненциально сложных задач (пусть N — число возможных ответов), ответ к которым просто проверить, для случая, если верна многомировая интерпретация квантовой механики фон Эверетта и принцип квантового бессмертия.

Нужно просто собрать машину, которая гарантированно убивает сидящего внутри человека, если тот отдает ей неправильный ответ на задачу. Человек квантово случайно генерирует ответ (например, с помощью радиоактивного распада) и отдает его машине. В N−1 вселенных машина убивает его, в одной оставшейся наблюдатель выходит из машины с правильным ответом. Согласно принципу квантового бессмертия, с точки зрения самого подопытного наблюдателя это будет выглядеть, будто он решил задачу с первого раза. Точка зрения внешних наблюдателей в большинстве вселенных будет «вот дурак».

Технически проблема состоит в том, что вероятность отказа машины должна быть меньше 1/N. Но если перед вами когда-нибудь возникнет подобная задача, ответ к которой вам дороже жизни, попробуйте этот метод. P = NP, но только для смельчаков!

Это первый на моей памяти SRM с дробным номером: возник он ввиду технических проблем с SRM 453. Увы, я его проспал, и, как оказалось в practice room, напрасно — за 45 минут сдал две задачи, а еще через несколько часов, повтыкав в Петино решение, и 1000 :)

( Задачи )

Дописывая этот пост, я стал свидетелем презанятнейшего явления — вспышки «Иридиума». Это ярчайшее звездоподобное явление (до −9.5^m), даже ярче сверхновой 1054 года (−6^m), которое, увы, длится недолго, всего несколько секунд. Его суть состоит в том, что один из 66 спутников космической связи «Иридиум» ВНЕЗАПНО отражает солнечный свет своей антенной, и тот попадает наблюдателю прямо в глаз.

Выглядело это примерно так: в серо-голубом предрассветном небе, в котором уже не было видно ни одной звезды, вдруг появилась удивительно яркая, быстро движущаяся звездочка (−7^m), и за 3-4 секунды погасла. К счастью, сегодня было две вспышки подряд, разделенные интервалом 9 минут, потому что я чуть не пропустил первую, ошибившись с северным направлением градусов на 15. Товарищ shuffle_c предложил замечательное использование явлению: дарить звезды любимым девушкам, вооружившись расписанием вспышек для вашей местности :)

А еще швейцарский коллектив Lunatica в этом году пополнил замечательный список из групп Delain, Edenbridge, After Forever, Эпидемия, Theatre of Tragedy, Rhapsody of Fire и Ayreon, последние альбомы которых сильно превосходят предыдущее творчество. На их нетленке New Shores замечательна каждая композиция. Голландцы Epica тоже весьма порадовали альбомом Design Your Universe, но он, увы, не стал прыжком вперед.

Среди четырех ярчайших звезд с отрицательной видимой звездной величиной фигурируют Сириус, Канопус и Арктур. А вот четвертую, несмотря на то, что ее тройная система находится ближе к Солнцу, чем любая другая звезда, называют всегда по букве — α Центавра. Но у нее тоже есть имя — Толиман!

Существует старинное поверье, согласно которому человек, посадивший чабрец у себя в саду, непременно встретит эльфов – привлеченные пряным свежим ароматом душистой травы, они поспешат в дом, готовые исполнить любое заветное желание…



Оказывается, достаточно просто посадить чабрец!

  С праздником!  

Кажется, я переплюнул Master Programmer из древнего бояна :) Подготовленный читатель без труда сообразит, реализация чего на няшных шаблончиках^{обожание!} приведена под катом.

( Насладиться )

Исправив ошибку в этом коде:


и отметив, что я потратил на нее примерно час, вы легко посчитаете мою производительность в КБ/сек :)

Решено: верный ответ по аське дал _denplusplus_. Ошибка возникает из-за того, что B в типе A<B, X>::type внутри области видимости struct B означает B<X> (14.6.1.2). A получает первым аргументом шаблона не шаблон, а его специализацию, и закручинивается. Для решения этой проблемы достаточно выйти из области видимости struct B, например, написав ::B.

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

MD5-хэшей 2¹²⁸ штук. Сколько из них имеет прообразы?

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

Кто желает в последний раз попробовать свои ментальные силы, смотрите этот пост, остальные — добро пожаловать под кат.

( Загадки и отгадки )

В игрушечном языке программирования Scratch используются мои любимые диаграммы Насси-Шнейдермана (смерть блок-схемам!).




Нашел я упоминание о нем в очень светлоджедайской статье на Хабре «Classmate/OLPC лагерь». Автор статьи задается вопросом «Будут ли отличаться от своих сверстников дети, которым показали, что работать и создавать — это приятно и интересно?». В качестве ответа на него приведу аббревиатуру МАН и посетую на количество участников.

А вот при чем здесь этот фрукт и аббревиатура БШ, поймут немногие :)

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

Между тем, существует очень простое и элегантное решение, повсеместное внедрение которого почти полностью решит проблему банкротства и рисков бизнеса. Это страхование наемными работниками прибыли нанимателя.

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

На первый взгляд такой метод кажется неожиданным и даже может вызвать реакцию «платить за устройство на работу? никогда!». Но следует заметить, что такая система невыгодна только для лентяев, которые не приносят бизнесу никакой прибыли, ставя под удар всю отрасль и самих себя: добросовестные сотрудники, качественно выполняющие свою работу, с лихвой компенсируют свой залог всего за несколько месяцев труда, без задержек получая зарплату, и без ужаса остаться без копейки в случае увольнения.

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

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

Пока что эта инициатива выглядит непривычно, но я уверен, что всего через несколько лет именно она станет основой выхода из кризиса!

Почему-то утверждается, что ФЯП могут работать с бесконечными списками, а C++ не в силах. Пришла пора достойно ответить злопыхателям!

( Код под катом )

Кратко опишу, что здесь происходит.

next это просто статическая функция N => N+1.
seq это шаблон-генератор бесконечной последовательности int, который принимает в качестве аргументов начальное значение и функцию, с помощью которой можно получить следующий элемент последовательности. Например, seq<42, next> это бесконечная последовательность 42, 43, ...

head и tail — всем известные функции для получения начала (int) и хвоста (бесконечная последовательность) последовательности.

find ищет в бесконечной последовательности первое число, удовлетворяющее статической функции типа int -> bool. Несложно увидеть, взглянув на шаблон find_helper, почему компилятор не производит бесконечного раскрытия бесконечной последовательности.

В качестве примера использования этого извращения предлагается:
1) поиск первого числа в последовательности 42, ..., которое делится нацело на 13 (div13).
2) поиск головы хвоста 42, ... и головы 6 раз взятого хвоста от этой же последовательности.
3) немного более сложный пример: вычисление 100-го простого числа (nthprime). В последовательности nthprime<N-1>+1, ... ищется первое число, для которого проверка на простоту (взятием остатка от деления на все меньшие простые числа) дает true. Сложность такого алгоритма по количеству инстанцированных компилятором шаблонов примерно O(N²lnN) (стоит упомянуть здесь теорему Россера).
4) увы, видимо, в C++ нет способа статически сгенерировать шаблонами массив, вектор или строку, поэтому заполнять вектор с первой сотней простых чисел приходится в рантайме — в конструкторах FillPrimes. Конструкторы вызываются от самого старшего родителя (FillPrimes<0>), поэтому push_back'и вызываются в нужном порядке.

VC++ 2008 отжирает при компилировании этого примера около 580 метров, так что запаситесь терпением :)

или Четвертая митуй-пати
или 3 дня, 6 ботанов и 103 километра по прямой, как летают назгулы Южному Берегу Крыма

Shuffle, 07.08.2009 22:47:20: А ты как-нибудь поедешь еще в Питер?
Sharp, 22:47:28: Вполне возможно
Sharp, 22:47:46: Но лучше вы к нам :)

( Повествование )

Количество компьютерных форматов представления времени поражает всяческое воображение. Видимо ввиду древности возникновения задачи хранить момент времени, область полна архаики. Вкратце перечислю некоторые из решений (рассматриваем наиболее популярную 32-битную архитектуру):

Unix time (POSIX-время, time_t) в 4 байтах хранит время в секундах, прошедшее с 1 января 1970 года, следовательно, может представлять время до 19 января 2038 года.

Unix time 64 — то же, что и предыдущее, только 64-битное. 8 байт, от 1 января 1970 года примерно 292 миллиарда лет.

Юлианские дни (JD) используется для указания дня в астрономии (для указания конкретного момента в дне используют дробную часть). Если ограничить его представление 4 байтами, он представит даты от полудня 1 января 4713 до н. э. примерно 12 миллионов лет. Именно эта дата была выбрана ввиду начала сразу нескольких неинтересных циклов и потому, что до нас не дошли упоминания о более ранних астрономических наблюдениях.

Модифицированные юлианские дни (MJD) используются для сокращения записи юлианских дней вычитанием 2400000.5, точкой отсчета становится ночь 17 ноября 1858 года.

BIOS-time измеряет время в тиках с частотой примерно 18.2 Гц с полуночи, занимает 4 байта.

struct tm используется для представления человеко-читаемой даты в стандартной библиотеке C.


Таким образом, эта структура размером 36 байт может представить дату от 1 января 1900 (и еще 4 миллиарда лет) с точностью до 1 секунды.

Радуют разнообразием форматы времени, используемые в Windows.

GetTickCount возвращает 4-байтовое число, равное количеству миллисекунд, прошедших с момента включения компьютера, представляя интервал до 49.7 суток. GetTickCount64 это ее 64-битный аналог, который позволяет представлять интервалы до 580 миллионов лет.

FILETIME это такой виндовый unix-time, только с БШ. БШ обеспечивается за счет 64-битности, позволяя указывать дату в 100-наносекундных интервалах, начиная с 1 января 1601 года на протяжении 58 тысяч лет.

SYSTEMTIME — БШ-tm от Microsoft.


Экономит на размере полей, поэтому занимает 16 байт, и представляет с секундной точностью время от 1601 года почему-то до 30827.

Кроме вышеперечисленных бинарных форматов существуют текстовые, тысячи, тысячи их. Но еще один виндовый я все же упомяну:

CIM_DATETIME — в формате yyyymmddHHMMSS.mmmmmmsUUU в 25 байтах представляющий с точностью 1 миллисекунда время от 0-го до 9999-го года.


Такое разнообразие страшно раздражает, и я задался вопросом, а нельзя ли как-нибудь решить эту проблему раз и навсегда?

Отметим, что дискретизация самого точного представления (FILETIME), равная 100 наносекунд, совершенно недостаточна для представления длительности, скажем, фемтосекундных лазерных импульсов, которыми давно и успешно исследуют механизмы химических реакций, а диапазона самого «древнего» (JD) и самого «широкого» (tm) недостаточно для датировки древних горных пород или превращения Солнца в красного гиганта.

Согласно принципу квантовой неопределенности и теории относительности, измерить время точнее планковского времени, равного примерно 5.39x10⁻⁴⁴ секунд, принципиально невозможно. Кроме того, время существования нашей Вселенной не превышает 13.85 миллиардов лет. Радостно делим одно на другое, берем двоичный логарифм и получаем, что хватит 203 бит. Округляем до 256 бит (32 байта, tm — и тот больше) и обнаруживаем, что любое обозримое событие и любой наблюдаемый интервал вполне может быть представлен таким числом.


Даешь 32-байтные таймстампы!!!