Category: it

Category was added automatically. Read all entries about "it".

uzel

Угадай 2/3 как инструмент ана

Слышали ли вы про игру "угадай 2/3 среднего"?
http://en.wikipedia.org/wiki/Guess_2/3_of_the_average
Я посмотрел итоги отыгрышей в нескольких группах. Ощущение примерно
такое: чем больше в группе "внутреннего уважения", тем меньшее число
выигрывает.
Коллективы программистов, в которых выигрывает что-то около 33, нужно
немедленно расформировывать, какими бы умными ни были их отдельные
члены

KK, http://kostya.tel
uzel

Задача специально для программистов

Вряд ли эту задачу будут давать на интервью, и тем не менее... Музыка задачи - М.Антипова, текст мой.

Компьютер печатает одно за другим натуральные слагаемые. Первое слагаемое равно 1, а каждое следующее слагаемое получается либо удвоением предыдущего, либо прибавлением к нему единицы. Компьютеру хочется сделать так, чтобы сумма всех напечатанных им слагаемых была равна 2^2013. Сможете ли вы ему помочь, чтобы он, бедный, не замучился в переборе вариантов?

Комментарии скрыты.
19.03. Раскрываю комментарии. Есть несколько совершенно правильных решений.
uzel

Третья задачка для программистов

(Уже точно не для начинающих.)

На вход поступают целые числа. Все, кроме двух, встречаются ровно 2 раза, а два числа встречаются по 3 раза. Как найти эти числа? Для определенности: общая длина потока меньше 2^64, и все числа тоже меньше 2^64
uzel

Две задачки для начинающих программистов

Время от времени мимо пробегают разнообразные задачи типа "из программистских интервью". Иногда - очень забавные. Формулируются они обычно нарочито неточно, чтобы отбить разнообразные встречные вопросы о том, насколько оптимальный алгоритм нужен. Чем оптимальнее сделаешь - тем выше будущий работодатель оценит (в рублях) твои умения и навыки.

Значится, так и запишем: я формулирую математическую суть, а на уточняющие вопросы, касающиеся реализации, отвечать не собираюсь.

Задачка 1. На вход поступают одно за другим натуральные числа. Известно, что во входном потоке каждое число, кроме одного, встречается дважды, а одно число - три раза. Как быстро (-пребыстро) его обнаружить?

Задачка 2. На вход поступают в случайном порядке натуральные числа от 1 до 1000. Известно, что во входном потоке будет ровно 998 чисел, причем ни одно число не повторится дважды. Как быстро (пребыстро) обнаружить те два числа, которых там не хватает?

Комментарии скрыты.

P.S. Раскрыл все комментарии. Кратко - о тех решениях, которые мне нравятся.

В первой задаче это, разумеется, простой побитовый XOR (не требующий O(N) дополнительной памяти).

Ключевая идея второй задачи - завести два разных счетчика, по итоговым значениям которых мы сможем однозначно найти пропущенные числа A и B как решения системы двух уравнений с двумя неизвестными. Один возможный счетчик очевиден - это сумма всех поступивших чисел (для нахождения A+B достаточно вычитать эту сумму из 500500, т.е. суммы всех чисел от 1 до 1000). Вторым счетчиком можно сделать и произведение, а для нахождения AB достаточно делить 1000! на каждое поступающее число (да, это фантастика, потому что 1000! в память компьютера не влезает, - но как справедливо указано в одном из комментариев, ничто не мешает сразу прологарифмировать и вместо деления вычитать логарифм). Но гораздо приятнее докумекать до более простого второго счётчика - суммы квадратов. Благо, сумма первых 1000 квадратов тоже вполне аычисляется по стандартной формуле. Предложенный кем-то из комментаторов вариант "сумма попарных произведений" является разновидностью этого же решения, поскольку эта сумма получается, если из квадрата суммы всех чисел вычесть их сумму квадратов и разделить на 2.
Ну и, наконец, как корректное и АЛЬТЕРНАТИВНОЕ СТАНДАРТНЫМ ИДЕЯМ решение отмечу "произведение по простому модулю 1009". Действительно, полученная в итоге система уравнений по модулю 1009 всегда имеет единственное решение, а если два числа, меньшие 1000, сравнимы по такому модулю, то они с неизбежностью равны.
qr

Ты сюда не ходи...

Список групп, встреч и сообществ, которые очень хотело закрыть ФСБ (официальное письмо Павлу Дурову см. тут: http://twitpic.com/7q9u8o)

http://vk.com/event27483334
http://vk.com/stop_er
http://vk.com/spb_protiv
http://vk.com/spb_protiv_er
http://vk.com/narod_protiv_er
http://vk.com/club32807199

Интересно, эти пингвины хоть понимают, что и зачем делают?
qr

Получим 917?

Конец прошлой недели для меня ознаменовался активным участием в одной забавной игре на сайте braingames.ru.

Есть цифры: 1 2 3 4 5. надо расставить мат. знаки между ними, чтобы получать числа от 1 по порядку. Например, (1+2+3+4)/5=2, (34^2 - 1) / 5 = 231.
Разрешенные знаки: + - ( ) * / ^ ! SQRT. Порядок цифр не фиксирован. Цифры разрешается объединять в многозначные числа, как во втором из приведенных примеров.

В этой игре участники добрались от 1 до числа 916 (!!), а на следующем застряли. Застревание тем более обидное, что дальнейшие несколько чисел получаются без проблем:
918 = 51 * (4! - 3 * 2)
919 = (3!)! + 5! * 2 - 41
920 = (5! / 3) * (4! - 1^2)
921 = (3!)! + 14^2 + 5

Кто может (и хочет) получить 917 ? (Только чур, без программирования, а то неинтересно.)
Комменты не скрываю
qr

Что такое фишинг - глядите сами

Инструкция:
1. Если Ваш вход на сайт vkontakte.ru на Вашей машине настроен "по умолчанию" (то есть сайт Вас _помнит_), перед тем, как переходить по приведенной мной ниже ссылке зайдите в свою страничке ВКонтакте и нажмите на "Выйти". Убедитесь, что теперь Вы не залогинены, перейдите в новое окно браузера, и только тогда набирайте там следующий адрес.

2. Набрав адрес, ни в коем случае не вводите ни свой логин, ни свой пароль от сайта ВКонтакте.
Просто полюбуйтесь - как ловят лохов.
Collapse )
qr

Скандинавские аукционы - раздолье для умных программистов

Забрел перед новым годом на http://vezetmne.ru
Забавные аукционы, - система выглядит очень простой, а организаторы, скорее всего, наваривают уйму денег. При том, что товары улетают с молотка по цене, а разы меньше, чем их реальная стоимость...
Collapse )
qr

Мозырь - наш новый козырь

http://mymozyr.info/2007/12/05/priznanie_na_mezhdunarodnojj_arene.html

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

(Буду показывать всем знакомым ЧГКшникам, которые что-то будут вякать о невозможности и недостоверности высоких результатов у никому не известных команд. В ACM "слив" исключен на 100%.

Подробнее - статья Парфёнова. http://www.it-belarus.net/news/read/2588/