Первоапрельский контест 2013: разбор задач Контест окончен; надеюсь, вам понравилось. 1465 человек решило хотя бы одну задачу — по-моему, отличный результат. Увы, все 6 задач не дались никому; мои поздравления [user:ShadowSong,2013-04-01], который выиграл контест, решив 5 из них с наименьшим штрафом! #### [problem:290A] Год назад было экспериментально установлено, что отсутствие условия не мешает участникам благополучно решить и сдать задачу, а автору экономит немножко усилий по его написанию. Сегодня мы еще раз в этом убедились. Можно было бы сочинить длинную и запутанную легенду о том, как вас, юного, но многообещающего программиста, вызвали в Белый дом и дали важнейшее задание: составить интерактивный список президентов Соединенных Штатов от основания страны до наших дней. В ней могли бы фигурировать долгие и напряженные поиски нужной информации, погони, перестрелки, умирающий напарник, последними словами которого было "Восьмой — Van Buren, не забудь... вывести Van, просто Buren... не пройдет..." Но зачем?...

Full text and comments »

Просто задача на подумать. <P>Я не буду просить, чтобы вы ее решили. Просто кажется интересным.</P><P>Пусть дан некоторый массив $a$ размером $N &lt; 2^30$ 32-битных целых чисел. Требуется выполнить $M$ запросов вида "сумма чисел на данном отрезке" за O(N+M), используя как можно меньше дополнительной памяти.</P><P>Очевидно, что существует решение, использующее $30*N$ бит дополнительной памяти.</P><P><BR></P><P>Update 1.<BR>Если допускать сложность O(N+M*log(N)), то можно добиться $6*N$ бит дополнительной памяти.<BR></P><P><BR></P><P>=============</P><P>В связи с особыми шаманствами, думаю, надо формализовать задачу немного по-другому.</P><P>Пусть дан некоторый массив $a$ размером $N$ из $\beta$-битных целых чисел. Требуется выполнить $M$ запросов вида "сумма чисел на данном отрезке" за O(N+M), используя как можно меньше дополнительной памяти. Операция сложения и обращения по индексу выполняются за О(1), умножение процессор не поддерживает.</P><P>Очевидно, что существует решение, использующее $N\log N$ бит дополн...

Full text and comments »

GCC 4.5.x Всем привет, Сегодня при дорешивании Харьковской Зимней Школы (а у них стоит G++ 4.5.3) столкнулся с такой проблемой, что довольно очевидное дерево отрезков получало WA2, когда как у меня часовой стресс-тест никаких багов не нашёл. Задача такая: дан массив, поступают запросы "GET l r a b", нужно выводить количество чисел на [l,r], значения которых находятся в промежутке [a,b]. Мой код: http://pastie.org/3810241 Наивное решение: http://pastie.org/3810252 Тест: http://pastie.org/3810319 Скрин: http://imgur.com/tquWU После часа шаманства нашёл причину, если код функции calc просто перенести в query, или же тупо написать inline перед calc, то всё становится окей. Причём у меня на GCC 4.6.x разницы никакой нет, а на 4.5 ветке ответы получаются разными. Компилирую с "-O2". Я не особо знаток плюсов, помогите пожалуйста, почему так получается?

Full text and comments »

Восстановление mbr Всем привет! Пишу я не по теме спортивного программирования и алгоритмов. Делая некоторые шаманства (слияние и создание разделов диска), я обнаружил, что у меня не загружается комп. Погуглив достаточно долго я смог сделать флешку которая запустила винду, но без нее винда по прежнему не грузится. Проблема то ли в загрузчике Windows, то ли в mbr (хотя может это одно и то же). В общем как восстановить и то и другое если у меня нет Live CD с Windows 7? Утилиту Bootrec.exe я долго искал в сети и для Windows 7 x64 не нашел.

Full text and comments »

Быстрое вычисление обратного квадратного корня Нашел интересную статью, о том как в Quake 3 происходит [вычисление обратного квадратного корня](http://www.codemaestro.com/reviews/9). Вот что такое промышленное шаманство)

Full text and comments »

Русские буквы В некоторых <strike>извращенных</strike> задачах бывает нужно вводить русский текст (редко, но бывает), есть ли какой то способ сделать это без геморроя в С++? Под геморроем я подразумеваю ввод посимвольно и шаманство после этого с кодами символов.

Full text and comments »