xpic99 25 сен 2008 в 07:46

Устройство на работу

2 мин

4.2K

IT-компании

+74

260

Комментарии 260

Leeb 25 сен 2008 в 08:04

Первая должна остаться, вроде как.

Leeb 25 сен 2008 в 08:06

черт, прошу прощения, не дочитал, думаю дальше. а методы и правда… конкурс, конкуренция…

hooey 25 сен 2008 в 09:51

Я думаю, при любом N открытыми останется M коробок.

andrew_b 25 сен 2008 в 12:24

moon4ik 25 сен 2008 в 10:26

Ответ прост: Целая часть от корня числа N =)

НЛО прилетело и опубликовало эту надпись здесь

antosj 25 сен 2008 в 10:39

Если уж интересуетесь, могу вот это посоветовать — www.koob.ru/poundstone_w/kak_sdvinut_goru_fudzi
Небольшая книжечка, в которой рассказывется откуда ноги растут такой методики приёма на работу… поверьте, бывает и хуже =)
+ там много подобных и не очень задач и пояснения какими методами их решать. В частности эта задача там есть насколько я помню, только не с коробками а со шкафчиками в раздевалке.

jeje 25 сен 2008 в 08:04

садистские методы приема на работу.

jeje 25 сен 2008 в 08:07

меня вопрос теперь мучает, действительно решение такой задачи отображает на реальное качество работы человека?

aleks_raiden 25 сен 2008 в 08:50

ну по результатам работы гугла видим, что да.

luminoushowl 25 сен 2008 в 11:59

Результат работы гугла = результату его отдела маркетинга :)

el777 25 сен 2008 в 17:40

Нет, только знание мат. методов.

svdesign 25 сен 2008 в 09:28

да зажрались они уже, звонят и говорят «мол ты тупица и не нас достоин»

trix 25 сен 2008 в 09:49

меня они по телефону заставляли писать реализацию очереди :)
ну и прочие задачки на теорию вероятности, комбинаторику и производительность алгоритмов

jeje 25 сен 2008 в 10:09

даже боюсь спросить… успешно?

trix 25 сен 2008 в 10:21

Увы-увы :) как раз теория вероятности и комбинаторика у меня оказались слабоваты.
Там были еще вопросы по языку и API (java) и общие вопросы по технологиям (сети, SQL, скриптовые языки), но это всё достаточно традиционно для IT-собеседований
Вообще, по совокупности впечатлений от нескольких людей, собеседовавшихся в гугле, можно заключить, что там ценят в большей степени «академические» знания, чем практический опыт.
Уж не знаю, оправдано ли это их процессом разработки или это особенность тех людей, которые проводят собеседования.
Было бы интересно узнать, какие требования к людям у них были лет 6 назад.

jeje 25 сен 2008 в 10:23

Такое ощущение что они нейронные там сети строят. Выход им нужны просто специалисты в области математики и т.п. нежели программисты.

sero 26 сен 2008 в 07:58

Я думаю, что эти методы достаточно оправданы для компании, которая имеет ткой широкое поле деятельности. Выучить Java API или, как строить SQL запросы может и гуманитарий, это лишь инструмент, но вот для грамотного использования этих инструментов необходимо аналитическое мышление, которое развивается исключительно математикой\физикой\другими точными науками. Программирование, конечно, тоже вносит свою лепту в развитие, но довольно специфическую. Любой программист легко написал бы программу, которая решит предложенную задачку — для данного N посчитать число открытых ящиков, но чтоб решать такие задачки математически, или аналитически, нужно в другой плоскости мыслить

jeje 26 сен 2008 в 08:01

да я собственно это уже понял, не судьба многим туда попасть, но я думаю к лучшему.

kvladimir 25 сен 2008 в 10:27

может они просто хотели посмотреть как человек отреагирует на нестандартную ситуацию?

AlexCult 29 сен 2008 в 17:34

Вычислили его местоположение с помощью google-maps?

cre8or 25 сен 2008 в 16:47

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

jeje 25 сен 2008 в 08:13

половина коробок

dna 25 сен 2008 в 08:15

а если коробок к примеру пять?

jeje 25 сен 2008 в 08:18

я сомневаюсь, что тут участвуют нечетные числа.

jeje 25 сен 2008 в 09:36

ну не прав, я не прав

Leeb 25 сен 2008 в 08:24

проверил я сейчас 5, 10 и 20 коробок. или я чего-то непонял в условии, или не половина остается.

jeje 25 сен 2008 в 08:41

x — закрыта
_ — отрыта

1 _ _ _ _ _ _ _ _ _ _
2 _ x _ x _ x _ x _ x
3 _ x x x _ _ _ x x x
4 _ x x _ _ _ _ _ x x
5 _ x x x x _ _ _ x _
6 _ x x x x x _ _ x _
7 _ x x x x x x _ x _
8 _ x x x x x x x x _
9 _ x x x x x x x _ x
10 _ x x x x x x x x _

1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
2 _ x _ x _ x _ x _ x _ x _ x _ x _ x _ x
3 _ x x x x _ x x x x x _ x x x x x — x x
4 _ x x _ x x x _ x x x x x x x _ x x x _
5 _ x x x _ x x x x _ x x x x _ x x x x x
6 _ x x x x _ x x x x x _ x x x x x _ x x
7 _ x x x x x _ x x x x x x _ x x x x x x
8 _ x x x x x x _ x x x x x x x _ x x x x
9 _ x x x x x x x _ x x x x x x x _ x x x
10 _ x x x x x x x x _ x x x x x x x x x x
11 _ x x x x x x x x x _ x x x x x x x x x
12 _ x x x x x x x x x x _ x x x x x x x x
13 _ x x x x x x x x x x x _ x x x x x x x
14 _ x x x x x x x x x x x x _ x x x x x x
15 _ x x x x x x x x x x x x x _ x x x x x
16 _ x x x x x x x x x x x x x x _ x x x x
17 _ x x x x x x x x x x x x x x x _ x x x
18 _ x x x x x x x x x x x x x x x x _ x x
19 _ x x x x x x x x x x x x x x x x x _ x
20 _ x x x x x x x x x x x x x x x x x x x

вообще м да, но где то в первом ошибка у меня

basilisk 25 сен 2008 в 08:53

Первый график, пятая строка, четвёртый ящик у вас самопроизвольно закрылся…

prudis 25 сен 2008 в 09:35

и во втором уже ошибку нашел.
3-я строка изменился почему то и 5-й и 6-й символ, хотя должен только 6-й измениться. Ну и соответственно дальше по цепочке все неправильно.
Вот оно…

____________________
_X_X_X_X_X_X_X_X_X_X
_XXX___XXX___XXX___X
_XX_____XX_X_XX_____
_XX_X___X__X_X_____X
_XX_XX__X____X___X_X
_XX_XXX_X________X_X
_XX_XXXXX______X_X_X
_XX_XXXX_______X___X
_XX_XXXX_X_____X____
_XX_XXXX_XX____X____
_XX_XXXX_XXX___X____
_XX_XXXX_XXXX__X____
_XX_XXXX_XXXXX_X____
_XX_XXXX_XXXXXXX____
_XX_XXXX_XXXXXX_____
_XX_XXXX_XXXXXX_X___
_XX_XXXX_XXXXXX_XX__
_XX_XXXX_XXXXXX_XXX_

NewStoic 25 сен 2008 в 08:13

ну по идее N/2 коробок останется открытыми.

Android 25 сен 2008 в 08:14

половина коробок останется открыта?

Assargin 25 сен 2008 в 08:17

Опытным путем получается, что одна коробка останется открытой

<?
$bcount=123; // число коробок

// массив состояний коробок, true — open, false — close
$b=array();
for($x=0; $x<$bcount; $x++)
  $b[]=true;

// решаем задачу
for($x=1; $x<=$bcount; $x++)
  for($y=1; $x<=$bcount; $x++)
    if($x%$y==0) // если нету остатка от деления, инвертируем состояние коробки
      $b[$x]=!$b[$x];

// подсчитываем число открытых коробок
$n=0;
for($x=0; $x<$bcount; $x++)
  if($b[$x])$n++;

echo $n;
?>* This source code was highlighted with Source Code Highlighter.

И она как раз первая и будет

jeje 25 сен 2008 в 08:19

начертил на листике и совсем по другому вышло, первая половина коробок изменяет состояние всего один раз, вторая половина 2 раза.

Assargin 25 сен 2008 в 08:26

Ну если уж на листике чертить…
допустим, для простоты, что у нас 8 коробок
Будет сколько проходений человека, открывающего-закрывающего коробки? Правильно: 7, потому что он сначала он меняет состояние каждой 2-й коробки, потом каждой 3-й… потом каждой 8-й.

Получаем:
ОООООООО
ОЗОЗОЗОЗ
ОЗЗОЗООЗ
ОЗЗЗЗООО
ОЗЗЗЗЗОО
ОЗЗЗЗЗЗЗ
ОЗЗЗЗЗЗЗ

где:
О — открыто, З — закрыто

P.S.: В моноширинном шрифте нагляднее бы смотрелось))

Leeb 25 сен 2008 в 08:28

а почему в третьей строке четвертый символ из З стал О? меняли же каждый третий…

set 25 сен 2008 в 08:33

а почему у вас все коробки только закрываются? ведь если коробка закрыта, её открывают… ну, по условиям задачи…

set 25 сен 2008 в 08:33

ой, сори, недоглядел…

set 25 сен 2008 в 08:34

моноширинным бы шрифтом было бы действительно наглядней…

basilisk 25 сен 2008 в 08:31

Ваш цикл неверный. Проверьте хотя бы для 4-х коробок. Результат должен быть 2 (открыты первая и четвёртая).

dna 25 сен 2008 в 08:40

<? php
$n = (int)$_GET['n'];
$boxes = array_fill(1, $n, 1);
for($i = 2; $i <= $n; $i++)
{
    for($j = $i; $j <= $n; $j = $j + $i)
    {
        $boxes[$j] = !$boxes[$j];
    }
}
//print_r($boxes);
echo array_sum($boxes);

PSHKGRZN 25 сен 2008 в 09:42

Все кто задачу разгадал — милости просим в гуголь :)

Assargin 25 сен 2008 в 08:41

Короче, я поспешил… и Хабрасообщество насмешил…

vrakhmanov 25 сен 2008 в 08:18

Есть анекдот на эту тему.
Два менеджера по персоналу опытный и стажёр сидят в офисе и обсуждают
дела. Молодой достает огромную пачку резюме, штук 300: «Мы должны просмотреть
их все, чтобы подобрать кандидатов на эту вакансию». Опытный
хладнокровно берет у него пачку, делит ее пополам, одну часть на стол,
вторую в шреддер. У молодого глаза по пятаку: «А как же претенденты?!»
Опытный невозмутимо: «А зачем нам неудачники?»

sanch3z 25 сен 2008 в 09:17

В жизни так и есть.

PSHKGRZN 25 сен 2008 в 09:53

Видно по аватару!

dna 25 сен 2008 в 08:21

$n — кол-во коробок

$openboxes = floor(sqrt($n));

Leeb 25 сен 2008 в 08:26

правдаподобно

lenis2000 25 сен 2008 в 08:29

Да, закрыты останутся те, которые тронуты нечетное число раз, а это в точности полные квадраты.

mdevils 25 сен 2008 в 08:53

А вот и нет)

lenis2000 25 сен 2008 в 09:27

Ну все же открыты сначала.
У предыдущего докладчика ошибка, там надо
$openboxes = n — floor(sqrt($n));

DmitriKadykov 25 сен 2008 в 09:36

Больше похоже на то что закрытыми останутся четные степени простых чисел.

для 2-ки:
2^2 = 4
2^4 = 8
2^6 = 32

3-ка:
3^2 = 9
3^4 = 81

И т. д. Но нужно
1) доказать что они и только они
2) как-то выразить всю эту лабуду через N

mdevils 25 сен 2008 в 08:46

Думаю, это правильный ответ.

mdevils 25 сен 2008 в 08:50

Нет, не правильный) Вы рассматривали малые N, где делителями являются лишь пары чисел. Рассмотрите 2*3*4, например. Этот ящик тоже останется открытым, хотя и не является квадратом целого числа.

dna 25 сен 2008 в 08:57

oxoxoxoxoxoxoxoxoxoxoxox
oxxxoooxxxoooxxxoooxxxoo
oxxoooooxxoxoxxoooooxxox
oxxoxoooxooxoxoooooxxxox
oxxoxxooxooooxoooxoxxxoo
oxxoxxxoxooooooooxoxoxoo
oxxoxxxxxooooooxoxoxoxox
oxxoxxxxoooooooxoooxoxox
oxxoxxxxoxoooooxoooooxox
oxxoxxxxoxxooooxooooooox
oxxoxxxxoxxxoooxoooooooo
oxxoxxxxoxxxxooxoooooooo
oxxoxxxxoxxxxxoxoooooooo
oxxoxxxxoxxxxxxxoooooooo
oxxoxxxxoxxxxxxooooooooo
oxxoxxxxoxxxxxxoxooooooo
oxxoxxxxoxxxxxxoxxoooooo
oxxoxxxxoxxxxxxoxxxooooo
oxxoxxxxoxxxxxxoxxxxoooo
oxxoxxxxoxxxxxxoxxxxxooo
oxxoxxxxoxxxxxxoxxxxxxoo
oxxoxxxxoxxxxxxoxxxxxxxo
oxxoxxxxoxxxxxxoxxxxxxxx

basilisk 25 сен 2008 в 08:29

Открытыми остаются коробки 1, 4, 9, 16, 25 и т.д.

Но решать такие задачки на улице без чего-нить под рукой, где даже не сконцентрируешься — нафик, нафик…

mdevils 25 сен 2008 в 08:50

А 24?

basilisk 25 сен 2008 в 08:56

Будет закрыт при любых N.

mdevils 25 сен 2008 в 09:00

Попробуйте вручную это проверить. 24 — это первое число из ряда тех, которые не соответствуют вашему предположению.

angelZ 25 сен 2008 в 09:04

24, такс проверим.
2 — закр
4 — откр
6 — закр
12 — откр
24 — закр.

mdevils 25 сен 2008 в 09:06

3 забыли

angelZ 25 сен 2008 в 09:07

и 8 тоже забыл :)

ZorroGFS 25 сен 2008 в 09:08

забыли 3 и 8

nep 25 сен 2008 в 09:10

24 будет закрыто. Его коснутся 7 раз (2,3,4,8,6,12,24) => т.к. изначально коробки открыты, то коробка под номером 24 будет закрыта.

basilisk 25 сен 2008 в 09:57

Проверил вручную. 24-я — закрыта. Простыни сюда выкладывать? ;)

Calvrack 25 сен 2008 в 09:07

24 закрта. Делители ее номера 1,2,3,4,6,8,12,24. На 2,4,8,24 шаге ее закрыват, на 3,6,12 открывают.

НЛО прилетело и опубликовало эту надпись здесь

makchammer 25 сен 2008 в 09:34

читайте внимательнее условие

basilisk 25 сен 2008 в 09:42

Вручную посчитайте для 4-х коробок. Открытыми будут 1-я (её никто не закрывал) и 4-я (её 1 раз закрыли-открыли)

NickMitin 25 сен 2008 в 08:29

А если мне звонят, и я, например, на важной встрече. Или просто не могу говорить? Я бы сказал им что мне сейчас не удобно разговаривать.

Мне кажется это был тест на личные качества, а не про коробки.

devx 25 сен 2008 в 09:30

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

NickMitin 25 сен 2008 в 09:56

Я бы все равно отказался собеседоваться по телефону.

devx 25 сен 2008 в 10:08

с этим согласен, думаю, я поступил также

Setti 25 сен 2008 в 10:14

Респект!
Человеку — человеческое.
А на точность вычислений пусть google арифметику тестирует.

Temmokan 25 сен 2008 в 08:30

N-2, если на последнюю тоже «нажимаеем».

Kudja 25 сен 2008 в 08:34

На сколько я слышал — задачи они постоянно такие дают при приеме, но чтоб по телефону и прямо на улице — впервые слышу…

Reijii 25 сен 2008 в 08:35

по-моему ряд будет 1 открыта 2 закрыты 1 открыта 3 закрыты 1 открыта 4 закрыты и т.д.

НЛО прилетело и опубликовало эту надпись здесь

angelZ 25 сен 2008 в 08:55

сомневаюсь что именно такой ответ их устроил бы. Хотя он абсолютно верен

Calvrack 25 сен 2008 в 09:14

А почему? Тут и ответ и решение (почти все). Просто и ясно, говорит о хорошей математичсекой подготовке и хорошей способности к абстракции.

mdevils 25 сен 2008 в 09:16

Хороший ответ (имхо) — это:

Ответ = f(N)
f(N) =… <тут ответ>

angelZ 25 сен 2008 в 09:19

согласен, техническое образование заставляет искать ответ именно в такой форме.

angelZ 25 сен 2008 в 09:18

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

Setti 25 сен 2008 в 10:15

есть теория, что их устроил бы любой оригинальный ответ

onichan 25 сен 2008 в 08:59

тоесть гугль хотели услышать:
открытыми останутся коробки в количестве равном округленному в меньшую сторону корню из N?

angelZ 25 сен 2008 в 09:03

именно

Setti 25 сен 2008 в 10:16

да пошли они!

makchammer 25 сен 2008 в 09:07

думаю к вашему ответу следует прибавить единицу

angelZ 25 сен 2008 в 09:09

нет не надо

FFire 25 сен 2008 в 09:27

Лучше +1 в карму

nep 25 сен 2008 в 09:18

Поясните, пожалуйста, логический переход: если у М четное количество делителей от 2 до N>=М, то М является полным квадратом.
Понятно, что решение верное, но никак не могу понять этот переход.

НЛО прилетело и опубликовало эту надпись здесь

nep 25 сен 2008 в 10:08

2x2x3x3 — тоже подходит под «полный квадрат». Уточню — все простые делители в четных степенях.
Разобрался таки с решением. Опишу — вдруг кому также как и мне — «не очевидно».

Из вышестоящих ответов ясно, что коробка останется открытой, если у ее номера — числа М — будет четное количество делителей от 2 до М включительно (т.е. ее тронут четное количество раз).

Разложим число М на простые множители. Каждый из них будет в четной или нечетной степени.
пусть — i, j, k… и т.д. степени простых множителей. Каждый делитель нашего числа М состоит из всех его простых множителей в степенях от 0 до i (до j, до k и т.д.). Т.е. всего делителей будет Д = ((i+1)(j+1)(k+1)… — 1 ) вычитаем 1 т.к. вариант, когда все множители в степени 0 нам не нужен (1 не считаем делителем в нашем случае). Чтобы число делителей Д было четным, нам нужно, чтобы произведение было нечетным. Произведение чисел может быть нечетным тогда и только тогда, когда все они нечетные. Таким образом — все степени i, j, k… простых множителей должны быть четными. Если все степени простых множителей четные — то число является полным квадратом. чтд.

ps. не знаю, как это может быть очевидным… Уж тем более смутно представляю как такое можно провернуть в уме и по телефону.

Midnighter 25 сен 2008 в 09:45

Например 24-я коробка 2^3 х 3^1 имеет 4 кратных простых делителя, и будет открытой, хотя не есть полным квадратом.

F(N) = sum(1 — A(i) mod 2)
i=1… N
A(i) — количество простых множителей с учетом кратности.

Попроще не придумывается формулы…

basilisk 25 сен 2008 в 09:59

… а всё-таки 24-я будет закрыта :)

Midnighter 25 сен 2008 в 10:07

Точно, это я недосмотрел… Надо не только простые делители учитывать

l2k 26 сен 2008 в 11:42

Совершенно верно :)
Тоже пришел к такому-же результату.

Radius 25 сен 2008 в 08:38

Не надо было соглашаться на такого формата собеседование. Нужно уважать себя.

freehome 25 сен 2008 в 08:38

Писал им в том году, до отъезда за бугор.
Ответ пришел через 2 месяца, когда уже был, по сути, не нужен.
Тормоза.

vertix 25 сен 2008 в 08:39

Google не виноват, что он испугался попросить перезвонить ему позже. Я думаю там работают адекватные люди, и если они уж заинтересовались резюме, то наверняка перезвонили бы еще раз.

EaE 25 сен 2008 в 08:45

Где-то была очень простая статистика: в Гугль в минуту поступает N резюме. N резюме в минуту, понимаете? Что это значит? Это значит, что по определению гугль не испытывает недостатка в отличниках, в людях с опытом работы, в людях с хорошим портфолио, в олимпиадниках, в людях со светлой головой — в общем, какой бы критерий отбора вы не выбрали, таких людей у них в очереди на собеседование больше, чем им нужно. Поэтому они могут себе позволить, и более того, имеют моральное право выбрать среди них например того, кто может решить задачку в уме на шумной улице посреди каких-то своих дел. Погуглите, как бы цинично это не звучало, в Сети на предмет собеседований в гугле. Очень много людей до вас интересовалось этим вопросом. И в общем, выясняется следующее: поскольку выбирать гуглерам приходится, по определению, среди и так уже лучших, выбирают часто по принципу личной совместимости. То есть, человека возьмут потому, что с ним приятно общаться. Или не возьмут потому, что лично в ту команду, которая его собеседует, он не впишется. И т.д. И то, каким выдающимся программистом он был до собеседования, особо роли не играет — высокий профессионализм подразумеватся по умолчанию.

Примерно так.

jeje 25 сен 2008 в 09:00

собственно как в анекдоте vrakhmanov.

trix 25 сен 2008 в 09:34

это в целом. а на конкретную вакансию в конкретном городе обычно поступает не так много резюме. просто в силу естественных ограничений рынка работы

EaE 25 сен 2008 в 09:39

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

trix 25 сен 2008 в 09:46

так то пиковый случай :)

alexshelkov 25 сен 2008 в 09:36

Ну и фиг с ними тогда — мы построим свой гугл, с блэкджеком и шлюхами =)

OmSoft 25 сен 2008 в 11:01

Апач, и ты здесь? ;)

dkuznetsov 25 сен 2008 в 08:53

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

cre8or 25 сен 2008 в 16:51

Эту экстремальную ситуацию человек сам себе создал.

egorinsk 25 сен 2008 в 18:16

Думаю, ничего страшного и экстремального в предложении решить задачку нет))

dkuznetsov 25 сен 2008 в 18:18

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

egorinsk 25 сен 2008 в 18:21

Значит, им нужны не просто программисты. Логично? А написать пару строк на php — тут конечно, каждый справится.

dkuznetsov 25 сен 2008 в 18:25

Да, им нужны не просто программисты. Если человек сходу решит такую задачку — он вероятно талантлив, что им подходит. Если человек знал о такой задачке — то он вероятно интересуется заковыристыми задачками, что говорит по крайней мере о том, что он не совсем уж глуп. Это тоже не так уж плохо. У Гугла эффективный способ отсева серой массы, как по мне.

msalomatin 25 сен 2008 в 08:55

Ну, вы даете! N коробок останется.

Catalyst 25 сен 2008 в 08:55

Одна останется?

crash 25 сен 2008 в 09:01

Они не задачу проверяли небось, а как всегда замуты с личными качествами типа лидер бы сказал, что сейчас не время и предложил бы перезвонить.

SmartyCZ 25 сен 2008 в 09:20

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

НЛО прилетело и опубликовало эту надпись здесь

MrDee 25 сен 2008 в 11:36

Ну если это шутка, то правильнее было-бы написать, скажем, M, т.к. N исходное количество.

НЛО прилетело и опубликовало эту надпись здесь

angelZ 25 сен 2008 в 09:02

По моим расчётам ответ будет таким:
$M=floor(sqrt(N));
т.е. при любом значении N количество открытых коробок будет корень из N с округлением до меньшего целого.

dragonhome 25 сен 2008 в 09:04

Задачка вообще математически решается?
По моему посчитать количество простых чисел на интервале и то проще ;/

shai_xylyd 25 сен 2008 в 09:56

Это и является ответом:)

gaki 25 сен 2008 в 10:02

У меня тоже задача вызвала ассоциации с «решетом Эратосфена» :)

Yevhen 25 сен 2008 в 09:05

Оценить нормально человека только задачкой — «бред» их HR-менеджера, а так же показывает, что они (скорей отдел по поиску персонала) изначально неуважительно относятся к сотруднику.

Gregory 25 сен 2008 в 09:24

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

Yevhen 25 сен 2008 в 09:37

это больше смахивает на какой-то «трюк». Тут вот и с гуглом пока решения не нашли.
Имхо, таким способом можно потерять кучу толковых ребят )

Snipe 25 сен 2008 в 15:58

Зато те, которые останутся…

Yevhen 25 сен 2008 в 17:23

Не факт, что останутся гении )

dkuznetsov 25 сен 2008 в 09:25

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

egorinsk 25 сен 2008 в 18:17

вы думаете, что нет людей, способных решить эту задачу в уме?

Yevhen 25 сен 2008 в 18:27

суть не в этом. Если да же есть такие люди и эта задача решается, не факт, что они лучше специ, чем те, кто не решил эту задачу… слишком простое отсеивание

Chips 25 сен 2008 в 09:05

Если N коробок = 1, то открыты все коробки
Если N коробок = 2, то открыто N/2 коробок
Если N коробок = 3, то открыто (N/2)-1 коробок
Если N коробок = 4, то открыто N/2 коробок
Если N коробок >= 5, то открыто (N/2)-1 коробок

тестировал только на маленьких значениях, но мне кажется что тенденция (N/2)-1 сохраняется

Emin 25 сен 2008 в 09:10

Только не (N/2) -1, а (N-1)/2.
Т.е. для чётных N/2, а для нечётных (N-1)/2.

НЛО прилетело и опубликовало эту надпись здесь

mumia 25 сен 2008 в 09:15

1 не вляется простым числом

mdevils 25 сен 2008 в 09:19

формальность)

angelZ 25 сен 2008 в 09:11

нет, ибо на тех же 3 и 5 вы получите открытыми 0.5 коробки и 1.5 коробки. А при 6-ти коробка что получите?

Chips 25 сен 2008 в 09:12

черт, посчитал еще немного и пришел к выводу, что:
При четном количестве коробок — остается 2 открытых коробки
А при нечетном — 3 коробки открыты

НЛО прилетело и опубликовало эту надпись здесь

p0is0n 25 сен 2008 в 09:19

Гугл жестокий)

p0is0n 25 сен 2008 в 09:29

import sys

# True = open; False = close

countBoxes = 40

_boxes = range(1, countBoxes + 1)
_count = [True] * countBoxes

def stat():
	[sys.stdout.write('%s ' % ('x' if not _count[i] else '-')) for i, box in enumerate(_boxes)] and sys.stdout.write('\n')
stat()
for step in xrange(1, countBoxes):
	for box in _boxes[step::step + 1]:
		try:
			box = _boxes.index(box)
		except:
			pass
		else:
			_count[box] = not _count[box]
	stat()

al1k 25 сен 2008 в 09:51

>countBoxes = 40
а если ящиков больше 40? скажем 400?

p0is0n 25 сен 2008 в 16:14

ну? а в чем проблема?

monsterzz 25 сен 2008 в 16:33

Зачем использовать sys.stdout.write если есть print?

kav 25 сен 2008 в 09:20

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

alexhabr 25 сен 2008 в 09:21

Ему нужно было сказать хоть что то. Хотябы 45 или 1 или 256. Так как любой пусть и не правильный ответ лучше чем никакой.

kav 25 сен 2008 в 09:29

Вот сейчас на работе маркетолог мне минут 10 предлагала наугад кучу вариантов, типа «В таких задачах ответ обычно '1', либо 'все'.........». Так что отвечать наугад — самый имхо глупый вариант, показывающий вашу неспособность подумать самому, тем более зная контору, с которой вам дали задание.

gaki 25 сен 2008 в 10:01

Хм… 1 либо все… у человека явно мистическое восприятие реальности. Вроде бы, уже чисто умозрительно должно быть понятно, что всегда получатся закрытыми вторая коробка, последняя коробка и все коробки между ними, чьи номера являются простыми числами, и это еще далеко не ответ :)

basilisk 25 сен 2008 в 10:09

Насчёт последней коробки — вы погорячились. При N=4 или 9 последняя открыта.
Но самой логики ваших абстрактных рассуждений это не меняет.

gaki 25 сен 2008 в 13:34

Да, на счёт последней коробки я жостко прогнал — число хитов по ней есть величина переменная, значит, она может быть как открытой, так и закрытой.

gaki 25 сен 2008 в 09:57

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

alexhabr 25 сен 2008 в 10:07

Ну вы же не будите говорить: «И так мой ответ наугад такой то»
Вы серьезным голосом скажите мой ответ 666.

gaki 25 сен 2008 в 13:35

Ага, а они мне: «Неправильно.» А я тогда: «Ну… эээ… 665?...»

MagicWolf 25 сен 2008 в 09:25

Да это элементарное распи№;%йство с их стороны, они этим еще два года назад страдали при приеме, когда я к ним поступал.

А как я добивался возврата денег за самолет — это вообще песня, я прозрел от несоответствия всем тем красивым картинкам в интернете. С их конкурсом на место они действительно могут себе позволить и иногда позволяют неуважительное отношение к кандидатам. Погуглите «google job interview».

Надо был говорить «сейчас не могу, давайте позже».

inlanger 25 сен 2008 в 09:31

То есть, если я когда-то такую задачу решал(для интереса, препод в школе задал, в инете ответ увидел и т.д.), и ответил правильно, то прошел бы собеседование, а кто-то, кто умнее меня, но с такой задачей не сталкивался — не прошел бы?

nightday 25 сен 2008 в 09:32

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

nightday 25 сен 2008 в 09:40

Кстати, вот формула: если есть число M=(p1^n1)*(p2^n2)*(p3^n3)*...*(pk^nk), то
количество разных делителей будет равно ((2^k)-1)*n1*n2*n3...*nk. Если это число четное, то коробка будет открытой, нечетная — закрытой.

moon4ik 25 сен 2008 в 10:37

нету нету… есть!
Ответ: Целая часть от корня числа N.

nIx0iD 25 сен 2008 в 09:34

nIx0iD 25 сен 2008 в 09:37

т.е. floor(sqrt($n))

kav 25 сен 2008 в 09:47

Ваше решение надо поместить в тему топика, иначе ответы так и будут сыпаться ;)

jrip 25 сен 2008 в 09:35

Опытным путём получается таки $openboxes = floor(sqrt($n)); как и написано выше.
На счёт сложности посчитать в уме… На сколько я помню, в вышке есть некий метод для примерного вычисления корня. И наверное, зная этот метод можно было бы, наверное, и догадаться.

GreenAngel 25 сен 2008 в 09:36

Вы тут все математики, а задача-то лигическая.

prudis 25 сен 2008 в 09:39

Фигасе логика :) на два коммента выше (на данный момент на 2) есть результаты для всех вариантов до 100. Даже там логически сложно вывести формулу посреди улицы и выдать в трубку ответ в виде формулы, не говоря уже об ответе сразу на задачу.

GreenAngel 25 сен 2008 в 09:41

Логика не в том как решить задачу, а что ответить интервьюеру.

123 25 сен 2008 в 09:43

Конечное состояние каждой коробки зависит от числа натуральных делителей её порядкового номера в диапазоне [2; Nкор.]:
— если число делителей четное, то коробка открыта;
— если число делителей нечетное — коробка закрыта.
Т.е. подсчитав кол-во чисел от 1 до N, имеющих четное число делителей можно узнать кол-во открытых коробок.

123 25 сен 2008 в 09:45

О, выше Nightday уже всё сказал.

coceg 25 сен 2008 в 09:47

открытыми остануться только коробки, которые открыли/закрыли четное кол-во раз, т.е. которые имеют четное кол-во разных делителей (не считая 1) и НЕЧЕТНОЕ, если 1 считать. Но любое число k, делящееся нацело на l, делится и на k/l тоже, т.е. разные делители входят парами. Исключение составляют квадраты целых, т.е. искомые номера коробок — квадраты целых, таких квадратов SQRT(N). Отсюда ответ SQRT(N) (с отброшенной дробной частью)

НЛО прилетело и опубликовало эту надпись здесь

cosmichorror 25 сен 2008 в 10:29

+1. я тоже пришел к такому решению.

Вообще, имхо, если можешь решить задачку — тебе нефиг делать в Гугле… Делай свой ГУГЛ!!! В смысле -стартап ;-)

НЛО прилетело и опубликовало эту надпись здесь

paratrooper5730 25 сен 2008 в 10:26

а вот и не все n^2 будут открыты. 36 например будет закрыта :)

НЛО прилетело и опубликовало эту надпись здесь

paratrooper5730 25 сен 2008 в 10:45

точно, ступил.
Вы правы

shai_xylyd 25 сен 2008 в 10:02

Ответ — количество простых чисел, не превосходящих N — функция Эйлера.

shai_xylyd 25 сен 2008 в 10:21

И ответ неправельный:)

paratrooper5730 25 сен 2008 в 10:07

Требуется отобрать коробки, которые будут затронуты четное кол-во раз.

это, как показывает опыт, квадраты, четрвертые, восьмые и т.д. степени простых чисел.

А возможно ли это для других?

Число можно разложить на простые. Если их n и они не повторяются, то количество комбинаций из них будет равно 2^n. То есть будет четным.
Если среди же мы добавим n+первое число, равное числу x из присутствующих n чисел, то добавится еще одна комбинация на каждую комбинацию, где есть x.
А остальных комбинаций, где x нет — их четное количество, так как они собраны из n-1 простых чисел!
То есть полюбому в сумме получаем четное число комбинаций

Значит, другие открытые ящики, кроме четных степеней простых чисел, невозможны.

paratrooper5730 25 сен 2008 в 10:10

поправлюсь, там где мы имеем четное кол-во комбинаций, нужно отбросить единицу, соответствующую случаю, когда не выбран ни один из множителей. Т.е. количество проходов будет четным

namor 25 сен 2008 в 10:08

может быть в такой ситуации лучше объяснить ситуацию и самому перезвонить им было?

НЛО прилетело и опубликовало эту надпись здесь

grokinn 25 сен 2008 в 10:14

я посреди улицы посчитал бы вслух итерации для 5 и 6 коробок и слелал бы какое то предположение насчет зависимости открытых коробок от N и его четности. Ну и если б знал математику наверное что то загнул бы про квадраты и эйлера быть может. Проверяется то не правильность решения а то растеряется ли ли человек и каким путем пойдет решение.

zuix 25 сен 2008 в 10:16

Ничего не напоминает?

moon4ik 25 сен 2008 в 10:23

Целая часть от корня числа N.

m2x 25 сен 2008 в 10:24

Многие что-то сложное пытаются придумать — понять четное или нечетное число делителей у числа, не считая единицу (что нам собственно и нужно), очень просто:

Если число не является квадратом, то все его делители идут парами: если a — делитель, то n/a — тоже делитель.
Если же является квадартом, то все делители идут парами, кроме собственно корня из n.

Но так как мы не берем в расчет единицу, то у всех чисел не являющихся точными квадратами нечетное число делителей, а у квадартов — четное.

Таким образом (как уже несколько раз написнао выше), ответ — количество точных квадратов до n, то есть floor(sqrt(n)).

123 26 сен 2008 в 06:45

Точнее — floor(sqrt(n))+1 (первая коробка всегда открыта) :)

m2x 26 сен 2008 в 06:53

И все же Вы не правы. Проверьте свой ответ хотя бы при n=1 и n=2.

iTon 25 сен 2008 в 10:24

ппц компания. ГееПидорги программисты. И Hr-ы с садистскими наклонностями :)

bagyr 25 сен 2008 в 10:36

Напомнило как сам в западную контору из-за разницы во времени собеседовался по телефону в 10 часов вечера.

re_agent 25 сен 2008 в 10:39

сумма (фунция эйлера(i) mod 2) по i от 1 до n?

eterevsky 25 сен 2008 в 10:46

По-моему, быть не может, чтобы ему предлагали пройти телефонное интервью без предварительного согласования с ним времени. В России так точно не делают. В других странах по идее тоже не должны, так как стандарты общие для всего гугла. Может, с ним договорились о времени собеседования, а он забыл?

Sinoptic 25 сен 2008 в 10:47

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

mrTempl 25 сен 2008 в 11:06

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

НЛО прилетело и опубликовало эту надпись здесь

Qbit 25 сен 2008 в 14:46

>А откуда гугл узнал что он на улице и так не кстати ему позвонил? Может он дома в тапочках, рядом столик ручка и бумага?
Может, он дома в тапочках, а рядом… компьютер, браузер и Гугл!

OmSoft 25 сен 2008 в 11:07

У меня здесь два варианта — либо Гуглю нужны математики-полугении ( ;) ), либо вопрос стоит в области психологии — сможете ли вы отказаться от чрезвычайно выгодного предложения (пусть на время, то есть — отложить рассмотрение этого предложения). Ну хорошо, человек на улице просто шел, а если бы он был на совещании, за рулем, решал иную задачу?…

НЛО прилетело и опубликовало эту надпись здесь

glider 25 сен 2008 в 21:27

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

НЛО прилетело и опубликовало эту надпись здесь

glider 26 сен 2008 в 06:23

Раз эти методы до сих пор применяются, есть подозрение, что они все-таки работают. И потом, в интернетах почему-то пишут только про заваленные собеседования — может, с теми, кто способен осилить задачки, уже говорят о том, какие они спецы?

re_agent 25 сен 2008 в 11:14

чорт! это реально количество квадратов, меньшее или равное N!

re_agent 25 сен 2008 в 11:15

это не факториал, а восклицательный знак.

timteka 25 сен 2008 в 11:30

а вот тут некто Макс Чубин изобразил флешку с экспериментом для наглядности :-)))
test.chubin.ru/task/

rubyrabbit 25 сен 2008 в 13:17

Ха-ха-ха… повеселили, спасибо! :-)

smartov 25 сен 2008 в 11:53

Решение верное, а объяснение неверное.
>>У всех чисел от 1 до N (кроме полных квадратов) есть четное (2k) количество делителей — то есть действие
>>«закрыл-открыл» происходит k раз и в результате всё равно коробка открыта остается
Для всех чисел кроме квадратов коробки как раз останутся закрытыми, потому что каждую первую мы никогда не закрывали. А открытыми останутся только квадраты.
Именно поэтому решением и является floor(sqrt(N)), как вы верно и сказали.

Спасибо за пост.

abushev 25 сен 2008 в 12:31

Для наглядности:

import sys
from math import sqrt

n = int(sys.argv[1])
data = [True for x in xrange(n)]
for i in xrange(2, n + 1):
for j in xrange(i, n + 1, i):
data[j-1] = not data[j-1]
print len(filter(lambda x: x, data))
print int(sqrt(n))

НЛО прилетело и опубликовало эту надпись здесь

Nulldevice 25 сен 2008 в 15:48

Я не совсем понял утверждение «нечетное число делителей имеют квадраты» — число 3*5*7=105 имеет три делителя, отличных от самого себя и единицы и не является квадратом
По самой задаче — если честно, в условиях, описанных автором, не решил. Но в целом вы идете правильным путем. Надо было сказать, что их будет столько, сколько чисел от 1 до N имеют нечетное количество делителей.

НЛО прилетело и опубликовало эту надпись здесь

Nulldevice 25 сен 2008 в 16:06

Извините. Теперь понял.

pymark 25 сен 2008 в 13:21

Автор топика дал не много информации, но по видимому это было стресс-интервью. Во-первых, не понятно в каком городе/стране интервьюировали человека. Судя по тому, что образование — 1 степень университет по Computer Sciences, это не Россия и не московский гугл, так что не пугайтесь раньше времени потенциальные соискатели. Во-вторых, не понятно на какую должность претендовал человек. Стресс-интервью проводят для должностей подразумевающих стрессовые перегрузки. Похоже это была должность программиста. На первый взгляд, для программиста стрессоустойчивость не ключевой параметр, но как отметил EaE, в условиях большого количества соискателей, логично брать тех, кого потом можно будет растить на другие должности, так называемый «кадровый резерв». Тот же программист потенциально может стать управляющим проектами, а там стрессоустойчивость важна.
тут все указывает на стресс-интервью, человеку звонят неожиданно, и дают задачу, практически не решимую за короткое время. HR-менеджеры тоже не идиоты и все понимают. Важно то, как среагирует кандидат, будет мямлить, предложит нестандартный выход или что-то еще

НЛО прилетело и опубликовало эту надпись здесь

kalyaka 25 сен 2008 в 14:39

Раз пошла такая пьянка, добавлю и свои пять копеек, которые навели на прав ответ:

public static void main(String[] args) {
// TODO code application logic here
int count = 50;
boolean[] items = new boolean[count];
for (int i = 0; i < count; ++i)
items[i] = false;
for (int i = 2; i <= count; ++i)
{
for (int j = i; j <= count; j+=i)
{
items[j-1] =! items[j-1];
}
}
for (int i = 0; i < count; ++i)
if (! items[i])
System.out.print(« „ + ++i);
System.out.println();
}

НЛО прилетело и опубликовало эту надпись здесь

lopanism 25 сен 2008 в 14:49

В какой офис гугла устраивался друг, если не секрет

srez 25 сен 2008 в 15:25

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

Nulldevice 25 сен 2008 в 15:53

> Я бы в любых условиях, спросонья и на улице решил бы эту задачку.

«Потому что до этого поросята видели волка только на картинке» — из детской сказки…

srez 25 сен 2008 в 15:59

Возможно и так. Но 10 лет надрочки маткружка врядли совсем уж бесследно для меня прошли.

avsmal 30 сен 2008 в 07:09

Зачем 10 лет — не понятно. Такую задачку обычно дают на кружке в пятом-шестом классе (первый год обучения) в теме делимость. Что-то вроде «Докажите, что если число является полным квадратом тогда и только тогда, когда количество его делителей нечётно».

bak1an 25 сен 2008 в 15:58

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

Snipe 25 сен 2008 в 16:13

Ну если человек не просто так отлично получал на физмате, например, то, думаю, он решит подобную задачу.

bak1an 25 сен 2008 в 16:35

учусь на прикладной математике. 90% из получающих отлично — тупо задроты, при виде задачи не описанной в учебниках уходят в глубокий даун. а вот участвующих в разных там acm-icpc и надо гуглам. так что «получать отлично на физмате» можно и не то чтобы просто так, но не особо напрягая извилины. в итоге получается очередной кодер, знающий пару шаблонов, да клепающий энтерпрайз проги по 5 штук в неделю. с отличным дипломом.

Snipe 26 сен 2008 в 06:25

Т.е. 3 и 4 никакого отношения не имеют к знаниям, трудолюбию/лени/силе воли, разносторонности человека?
Я согласен, иногда, особенно на последних курсах бывают ситуации, что оценки ставятся накатом, например студент откровенно сдал на 3 или 4, но в зачётке у него одни пятерки и преподу приходится ставить 5, но именно на этот случай я написал «не просто так».

В общем я считаю, что если человек учится на 5, и 5 соответствует знаниям, а не стечению обстоятельств — то он обязан решить такую задачку. =)

И опять же если человек решает подобную задачу, но учится на 3 и 4 — это говорит о том что он умен, но ленив, или ему неинтересен предмет (за редким исключением виноваты обстоятельства, в виде особо злобных преподов). Зачем Гуглу ленивые или не интересующиеся люди?

bak1an 26 сен 2008 в 14:32

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

Snipe 29 сен 2008 в 07:49

Если зубрить, то да, ерунда выйдет.
А, знания — это то что остается, когда вы все забудете =)

srez 25 сен 2008 в 16:25

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

Nulldevice 25 сен 2008 в 16:01

В городе N тоже решили провести телефонное интервью:
— Как к свехрурочным относишься? Хорошо?
— Хорошо
— А если надо, обжать кабель вместо админа сможешь?
— Смогу.
Ну ладно… Слушай задачу. К бассейну подведены две… а ну и фиг сней! Берем!

Nulldevice 25 сен 2008 в 16:35

А я с Гуглом не согласен. Я никто, а Гугл — великий, но все равно не согласен. Бог создал разных людей. Кто-то не стрессоустойчивый от природы, кто-то не умеет решать быстро, потому что глубоко копает, но все типы нужны и в какой-то ситуации могут играть решающую роль.

el777 25 сен 2008 в 17:27

Задача математическая на знание численных методов. Тут даже программировать не надо.

Вначале было N открытых коробок, затем стало N/2, потом N/2-N/3, таким образом после k-того шага открытых коробок будет:

M = N - N/2 + N/3 - N/4 + N/5 + ... — в сумме должно быть k членов.

Запишем это проще:

M = N * (1 - 1/2 + 1/3 - 1/4 + 1/5 + ...)
Ничего не напоминает? Это разложение в ряд Тейлора значения натурального логарифма 2. Кстати, тут один товарищ построил график этого логарифма :)
Но ln 2 из этого ряда получится только в случае бесконечного количества членов. Если же их конечно, и как мы знаем их ровно N, то мы получим какое-то приближение к значению логарифма. Давайте оценим насколько оно точное.
Легко видеть (а можно строго математически доказать), что ряд сходится к какой-то совершенно определённой величине. Более того, я имею смелость утверждать, что ошибка для ряда длинной k членов не превышает 1/k. Это очевидно, т.к. каждый следующий член меньше предыдущего и все они болтаются вверх-вниз относительно какого-то значения.
Для нашего случая при k=N получаем: ΔM = N * 1/N = 1. Замечательный вывод! Значит, при длине последовательности N ошибка будет всегда меньше 1! А раз дробных коробок не бывает, то мы подсчитываем значение с точностью до одной коробки. Это нас полне устроит.

Итак: Открытых коробок = N * ln 2

Самый главный вопрос в какую сторону округлить :)

el777 25 сен 2008 в 17:50

Пардон, поспешил…
я подсчитал кол-во коробок, которые изменят свое состояние, то есть будут закрыты.
Открытых соответственно будет N * (1 – ln 2) ~ 0.31 * N

НЛО прилетело и опубликовало эту надпись здесь

el777 25 сен 2008 в 19:48

Точно!
После корпоративки неверно прочитал условие задачи! :)
Я понял так, что коробки по очереди на одном шаге закрываются, а на следующем открываются. А они меняют состояние, в таком случае ряд будет совсем другой, навроде:
1/2 - 1/8 + 1/16 - 5/128 + ...
А это именно разложение sqrt(N)
Сорри, кого сбил с толку!

НЛО прилетело и опубликовало эту надпись здесь

el777 25 сен 2008 в 17:29

На самом деле вопрос совершенно не в этом.
А в том, что действительно не надо дергать человека посреди улицы.

el777 25 сен 2008 в 17:38

Извините за занудство, но UPD 2 неправильный — проверьте задачу при 10 коробках.

xpic99 25 сен 2008 в 22:53

Вроде работает:
Image and video hosting by TinyPic

Ответ: 3
Жирным шрифтом выделены изменения состояния.
Слева номера шагов.
Желтым выделены открытые коробки.

Rchernovol 25 сен 2008 в 18:29

да, печально.
можно было бы не растеряться, и сказать, мол, извините, сейчас не могу говорить (вдруг он ведет авто), перезвоните через n минут, или позвольте, я вам перезвоню.
Это нормальная ситуация, и нечего перед гуглем падать на колени и боготворить его.
Но это в идеале.

… И такой случай НЕ показывает высокую компетентность их эйчарников.

bruno 25 сен 2008 в 19:34

а 50 на 50? или з звонок другу? :)

tapin13 25 сен 2008 в 19:47

если звонят из Гугля, отвечаем «Извините это уже не актуально» :)

mkechinov 25 сен 2008 в 20:37

До меня только сейчас дошло, а жена после того, как я задал эту задачу, решила ее еще до того, как я конечный вопрос задал!

Задача:

Все коробки открыты. Проходим по КАЖДОЙ второй и закрываем ее. Проходим по КАЖДОЙ третьей и если она открыта, закрываем, если закрыта, открываем. Проходим по КАЖДОЙ четвертой…

Уберите слово «КАЖДОЙ».

Получится:

Все коробки открыты. Закрываем вторую. Закрываем третью. Закрываем четвертую. Закрываем пятую…

Необходимость закрывать КАЖДУЮ сбивает с толку.

Хотя вот сейчас сомнения закрались… завтра опыт поставлю.

namor 26 сен 2008 в 04:11

неправильно
Все коробки открыты. Закрываем вторую. Закрываем третью. ОТКРЫВАЕМ четвертую. Закрываем пятую…

mkechinov 26 сен 2008 в 04:25

Да. Уже осознал. А ответ казался таким заманчивым.

trisch 25 сен 2008 в 21:05

а я хотела бевербунг писать…
как-то страшно стало :)

НЛО прилетело и опубликовало эту надпись здесь

Snipe 26 сен 2008 в 06:00

Утром, на свежую голову задачка показалась гораздо проще чем во второй половине рабочего дня )
2 коробка нажимается один раз
3 — 1 (3)
4 — 2 (2, 4)
5 — 1 (5)
6 — 3 (2, 3, 6)
7 — 1 (7)
8 — 3 (2, 4, 8)
9 — 2 (3, 9)
и т.д.

Открытыми остаются коробки 1, 4, 9 подобный ряд предлагали дополнить в анкете в военкомат. =)

Snipe 26 сен 2008 в 06:13

В общем надо коробки открывать/закрывать в порядке не по условию задачи (сначала каждую вторую, потом каждую третью и т.д.), а именно производить все действия сразу над одной коробкой: сначала делаем со второй все действия, потом с третьей, с четвертой — так проще.

konopko 26 сен 2008 в 07:01

Похоже Гуглу нужны работники, которые рассчитывают маршрут до магазина и обратно в уме с помощью рядов Фурье. Представляете как должен выглядеть этот «кадр»? ;)

afi 26 сен 2008 в 08:24

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

rukavruku 26 сен 2008 в 08:35

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

Nuru 26 сен 2008 в 09:27

public class Boxes {

private int iterations = 39, from = 2;
private boolean[] box;

public void makeAction() {
box = new boolean[iterations];
//initial fill
for (int cr = 0; cr < iterations; cr++) {
box[cr] = true;
}

for (int outer = 1; outer <= iterations; outer++) {
System.out.print(outer + «)\t»);
for (int inner = 1; inner <= iterations; inner++) {
if (outer >= from) {
if (inner % outer == 0) {
box[inner — 1] =! box[inner — 1];
}
}
System.out.print((box[inner — 1]? «O»: «X») + « „);
}

System.out.println();
}
}

public static void main(String[] args) {
Boxes crb = new Boxes();
crb.makeAction();
}
}

Результат:

1) O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O
2) O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O
3) O X X X O O O X X X O O O X X X O O O X X X O O O X X X O O O X X X O O O X X
4) O X X O O O O O X X O X O X X O O O O O X X O X O X X O O O O O X X O X O X X
5) O X X O X O O O X O O X O X O O O O O X X X O X X X X O O X O O X X X X O X X
6) O X X O X X O O X O O O O X O O O X O X X X O O X X X O O O O O X X X O O X X
7) O X X O X X X O X O O O O O O O O X O X O X O O X X X X O O O O X X O O O X X
8) O X X O X X X X X O O O O O O X O X O X O X O X X X X X O O O X X X O O O X X
9) O X X O X X X X O O O O O O O X O O O X O X O X X X O X O O O X X X O X O X X
10) O X X O X X X X O X O O O O O X O O O O O X O X X X O X O X O X X X O X O X X
11) O X X O X X X X O X X O O O O X O O O O O O O X X X O X O X O X O X O X O X X
12) O X X O X X X X O X X X O O O X O O O O O O O O X X O X O X O X O X O O O X X
13) O X X O X X X X O X X X X O O X O O O O O O O O X O O X O X O X O X O O O X O
14) O X X O X X X X O X X X X X O X O O O O O O O O X O O O O X O X O X O O O X O
15) O X X O X X X X O X X X X X X X O O O O O O O O X O O O O O O X O X O O O X O
16) O X X O X X X X O X X X X X X O O O O O O O O O X O O O O O O O O X O O O X O
17) O X X O X X X X O X X X X X X O X O O O O O O O X O O O O O O O O O O O O X O
18) O X X O X X X X O X X X X X X O X X O O O O O O X O O O O O O O O O O X O X O
19) O X X O X X X X O X X X X X X O X X X O O O O O X O O O O O O O O O O X O O O
20) O X X O X X X X O X X X X X X O X X X X O O O O X O O O O O O O O O O X O O O
21) O X X O X X X X O X X X X X X O X X X X X O O O X O O O O O O O O O O X O O O
22) O X X O X X X X O X X X X X X O X X X X X X O O X O O O O O O O O O O X O O O
23) O X X O X X X X O X X X X X X O X X X X X X X O X O O O O O O O O O O X O O O
24) O X X O X X X X O X X X X X X O X X X X X X X X X O O O O O O O O O O X O O O
25) O X X O X X X X O X X X X X X O X X X X X X X X O O O O O O O O O O O X O O O
26) O X X O X X X X O X X X X X X O X X X X X X X X O X O O O O O O O O O X O O O
27) O X X O X X X X O X X X X X X O X X X X X X X X O X X O O O O O O O O X O O O
28) O X X O X X X X O X X X X X X O X X X X X X X X O X X X O O O O O O O X O O O
29) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X O O O O O O X O O O
30) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X O O O O O X O O O
31) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X O O O O X O O O
32) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X O O O X O O O
33) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X O O X O O O
34) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X O X O O O
35) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X X O O O
36) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X O O O O
37) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X O X O O
38) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X O X X O
39) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X O X X X

Nuru 26 сен 2008 в 09:28

если посмотреть на нижний ряд, то можно увидеть, что открытые ящики будут оставатся через n = n+2 ящиков

НЛО прилетело и опубликовало эту надпись здесь

Зарегистрируйтесь на Хабре, чтобы оставить комментарий