Имеется массив целых чисел, каждый в интервале от -10000 до 10000. Нужно найти непрерывный интервал в этом массиве, чтобы сумма элементов на этом интервале была положительной и максимально возможной среди других интервалов.
Как результат надо вывести начальный и конечный индексы этого интервала.
Подразумевается решение O(n).
Показаны сообщения с ярлыком задачки. Показать все сообщения
Показаны сообщения с ярлыком задачки. Показать все сообщения
пятница, 17 июня 2011 г.
воскресенье, 5 июня 2011 г.
Задача про винты и гнезда
Разгребая старые записи, я нашел несколько задач, виденных мной на различных интервью.
Вот одна из них.
Имеется n винтов и n гнезд, расположенных в произвольном порядке. Каждому винту соответствует по диаметру только одно гнездо. Все винты имеют разные диаметры.
Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. В результате такой операции можно выяснить: (1) винт тоньще гнезда - не подходит, (2) винт толще гнезда - не подходит, (3) или винт точно входит в гнездо - подходит.
Сравнивать винты или гнезда между собой нельзя.
Очевидное решение за O(N^2) - попробовать каждый болт последовательно в каждое гнездо до совпадения. Но есть решение быстрее.
Вот одна из них.
Имеется n винтов и n гнезд, расположенных в произвольном порядке. Каждому винту соответствует по диаметру только одно гнездо. Все винты имеют разные диаметры.
Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. В результате такой операции можно выяснить: (1) винт тоньще гнезда - не подходит, (2) винт толще гнезда - не подходит, (3) или винт точно входит в гнездо - подходит.
Сравнивать винты или гнезда между собой нельзя.
Очевидное решение за O(N^2) - попробовать каждый болт последовательно в каждое гнездо до совпадения. Но есть решение быстрее.
четверг, 17 марта 2011 г.
Задача: выборы мэра
В городе N жителей. Надо выбрать мэра. Чтобы минимизировать коррупцию во власти, мэр должен быть таким человеком, которого лично знают все, но он лично не знает никого.
Как выбрать мэра?
Как выбрать мэра?
вторник, 8 февраля 2011 г.
NORCPU hackme challenge или взлом программы для однокомандного процессора
Разного рода "ненормальное" программирование весьма популярно среди любителей поломать голову над разными задачками. Порой программу для очередной "ненормальной" среды программирования уже нереально написать вручную, а надо писать генератор, создающий код.
В задаче, что предлагаю я, программы все еще можно писать вручную на некотором высокоуровневом макроассемблере.
Итак, имеется модель некоторого виртуального процессора, выполняющего только одну логическую операцию - Стрелку Пирса.
На этом процессоре написана программа, на вход которой подается некоторый пароль. Если пароль неверный, то в ответ выдается строка "Wrong password!". Если верный, то выдается определенное волшебное сообщение.
Задача: любым образом выяснить это волшебное сообщение. Как вариант, можно, например, угадать пароль, и программа сама выдаст секрет.
Логика написана таким образом, что разобравшись в алгоритме, можно без труда расшифровать волшебное сообщение.
В прошлом году я описал использованный подход во всех деталях.
Оригинальный подход, на котором основан мой эксперимент, был не совсем "чистым", так как команда сложения был вынесена за логику процессора. В моей версии все до единой команды реализованы на самом процессоре. Для этого потребовалось немного изменить интерпретатор, добавив в него сдвиговый регистр.
Для желающих попробовать взломать мой эксперимент, я сделал страничку, на которой на JavaScript'e реализован выше описанный виртуальный процессор с одной командой и программа для него, проверяющая пароль.
Итак, ссылка на задачу: http://demin.ws/norcpu/norcpu.html
Удачи.
P.S. Для первого взломавшего - небольшой приз! Информация по ссылке.
среда, 21 апреля 2010 г.
Смесь двоичной и десятичной арифметики
Многие знают, что происходит при выполнении присваивания "n &= (n - 1);" просто потому, что это весьма распространенный шаблон, и для чего может понадобиться выполнение его в цикле, пока n не станет нулем.
Интересно другое: четкое математическое (и/или алгоритмическое) объяснение, почему это работает именно так, строгое доказательство.
Update:
Чтобы разобраться в вопросе надо понять, что является корнем недопонимания.
Для людей, не часто имеющих дело с двоичной системой, обычно не совсем очевидна суть трансформации внутреннего двоичного представления числа при выполнении арифметической операции в десятичной нотации. Кажется, что если вычесть единицу, то расположение битов после операции будет иметь мало общего с тем, что было до вычитания. И дальнейшее выполнение "and" вообще не имеет смысла.
С точки зрения битового представления любого числа, есть только два случая:
1. Если число нечетное, на конце будет единица: "xx...xx1". Вычитание из такого числа даст: "хх...хх0". Поэтому "(xx...xx1) & (xx...xx0)" даст "(xx...xx0)". Фактически, мы убрали младший бит.
2. Если число четное, на конце будет ноль (или несколько нулей): "xx...xx100...00". Видно, что вычитание единицы из такого числа однозначно не изменит разряды "xx...xx", стоящие слева после первой единицы. Более того, результат вычитания единицы однозначно предсказуем: "xx...xx011...11". Теперь точно видно, что будет после операции "and": ("xx...xx100...00") & ("xx...xx011...11") даст ""xx...xx000...00". То есть мы убрали единицу из самого младшего ненулевого разряда.
Теперь ясно видно, что именно проиходит в присваивании "n &= (n - 1);". А именно, обнуление самого младшего ненулевого разряда.
Использование этого трюка в цикле, пока n не равно нулю, позволяет подсчитать количество ненулевых бит. На каждой итерации мы "выбиваем" ровно один бит, поэтому Число итераций будет равно количеству единиц в n.
Интересно другое: четкое математическое (и/или алгоритмическое) объяснение, почему это работает именно так, строгое доказательство.
Update:
Чтобы разобраться в вопросе надо понять, что является корнем недопонимания.
Для людей, не часто имеющих дело с двоичной системой, обычно не совсем очевидна суть трансформации внутреннего двоичного представления числа при выполнении арифметической операции в десятичной нотации. Кажется, что если вычесть единицу, то расположение битов после операции будет иметь мало общего с тем, что было до вычитания. И дальнейшее выполнение "and" вообще не имеет смысла.
С точки зрения битового представления любого числа, есть только два случая:
1. Если число нечетное, на конце будет единица: "xx...xx1". Вычитание из такого числа даст: "хх...хх0". Поэтому "(xx...xx1) & (xx...xx0)" даст "(xx...xx0)". Фактически, мы убрали младший бит.
2. Если число четное, на конце будет ноль (или несколько нулей): "xx...xx100...00". Видно, что вычитание единицы из такого числа однозначно не изменит разряды "xx...xx", стоящие слева после первой единицы. Более того, результат вычитания единицы однозначно предсказуем: "xx...xx011...11". Теперь точно видно, что будет после операции "and": ("xx...xx100...00") & ("xx...xx011...11") даст ""xx...xx000...00". То есть мы убрали единицу из самого младшего ненулевого разряда.
Теперь ясно видно, что именно проиходит в присваивании "n &= (n - 1);". А именно, обнуление самого младшего ненулевого разряда.
Использование этого трюка в цикле, пока n не равно нулю, позволяет подсчитать количество ненулевых бит. На каждой итерации мы "выбиваем" ровно один бит, поэтому Число итераций будет равно количеству единиц в n.
среда, 7 апреля 2010 г.
Задача про гномов
Товарищ рассказал интересную задачку и был очень удивлен, что я ее не слышал.
Поймал людоед несколько гномов (количество в задаче не задается), и сказал, что завтра он всех выстроит в колонну один за другим и оденет всем на головы либо черную, либо белую шапку. Гномы будут стоять так, что каждый будет видеть шапки только тех, кто впереди (последний видит всех, кроме себя, а первый – никого). Свою собственную шапку гномы не видят. Количество черных и белых шапок произвольное (хоть все белые, хоть все черные). Далее людоед, начиная с последнего, будет каждого спрашивать, какая шапка у него на голове. Гном может ответить только одним из двух слов «черная» или «белая». Если ответ неверный, но гном съедается, иначе переходят к следующему. В процессе поедания все пока еще живые гномы слышат, что проиходит сзади, то есть хоть они и не видят товарищей сзади, но слышат – когда кого съели, а кого нет, и также их ответы.
В общем, за ночь гномы покумекали, и придумали стратегию, как они все останутся живыми кроме одного. Но и тот один будет иметь шанс выжить.
Вопрос: что за стратегию придумали гномы?
Задача имеет очень красивое решение, имеющее прямое отношение к компьютерной науке.
Ответ будет позже, если кто вдруг не догадается.
Поймал людоед несколько гномов (количество в задаче не задается), и сказал, что завтра он всех выстроит в колонну один за другим и оденет всем на головы либо черную, либо белую шапку. Гномы будут стоять так, что каждый будет видеть шапки только тех, кто впереди (последний видит всех, кроме себя, а первый – никого). Свою собственную шапку гномы не видят. Количество черных и белых шапок произвольное (хоть все белые, хоть все черные). Далее людоед, начиная с последнего, будет каждого спрашивать, какая шапка у него на голове. Гном может ответить только одним из двух слов «черная» или «белая». Если ответ неверный, но гном съедается, иначе переходят к следующему. В процессе поедания все пока еще живые гномы слышат, что проиходит сзади, то есть хоть они и не видят товарищей сзади, но слышат – когда кого съели, а кого нет, и также их ответы.
В общем, за ночь гномы покумекали, и придумали стратегию, как они все останутся живыми кроме одного. Но и тот один будет иметь шанс выжить.
Вопрос: что за стратегию придумали гномы?
Задача имеет очень красивое решение, имеющее прямое отношение к компьютерной науке.
Ответ будет позже, если кто вдруг не догадается.
Подписаться на:
Сообщения (Atom)
Сообщения
