Хотелось бы рассказать о частном случае пробы устройства на работу (сразу оговорюсь, действие происходит не в России).
Итак, мой друг (закончил 1-ую степень одно из университетов по специальности Computer Sciences) послал резюме в местное отделение Google. Чтобы они вообще пригласили кого-либо на собеседование, нужен средний бал не меньше 85 (считается отличником). У него, естественно средний бал выше (около 90, точно не помню). Есть опыт работы на Java.
Так вот, он послал резюме и вообще забыл про это. Недели через три, когда он шел куда-то по своим делам, ему звонят, представляются как Google, мол вы Такой-то Такой-то прислали нам резюме, всё хорошо, давайте проведем интервью. Он: естественно, давайте, давайте. Ему говорят: вот, решите задачку: (чтоб вы понимали, человек посреди шумного города, ни листика ни ручки. Сказать «перезвоните позже» он тоже не может (а вдруг не перезвонят), в общем, это шанс и за него надо хвататься):
Задача:
Есть N коробок. Все они открыты. Человек проходит и закрывает каждую вторую коробку. Затем проходит по каждой третей коробки, если она открыта закрывает, если закрыта открывает. Потом по каждой четвёртой и так до N. Сколько коробок останутся открытыми после всех этих действий.
Он в полном ступоре, потому как до сих пор не приходилось решать задачи для интервью на УЛИЦЕ!
Подумал немного, но решить так и не смог (слишком волновался, я думаю). Они его поблагодарили и отключились. Вот так вот. Хотя я думаю будь он у них в офисе, решил бы без проблем.
Вывод: либо не сильно хотели, либо слишком много желающих и надо было отсеить хотя бы половину вот таким «интервью». Ни от кого из моих знакомых я больше подобных случаев не слышал, так что похоже это были разовые меры.
P.S. Попробуйте решить задачу, если интересно, выложу решение.
UPD 2: Некто Макс Чубин сделал на флеше наглядное решение данной задачи.
Ссылка
UPD: Ответ:
Целая часть от (корень N)
Почему?
У всех чисел от 1 до N (кроме полных квадратов) есть четное (2k) количество делителей — то есть действие «закрыл-открыл» происходит k раз и в результате всё равно коробка открыта остается. А у полных квадратов нечетное количество делителей. Поэтому ответить на этот вопрос это все равно что посчитать сколько полных квадратов есть до N, то есть целая часть корень N.
Вроде правильно...
комментарии (260)
Небольшая книжечка, в которой рассказывется откуда ноги растут такой методики приёма на работу… поверьте, бывает и хуже =)
+ там много подобных и не очень задач и пояснения какими методами их решать. В частности эта задача там есть насколько я помню, только не с коробками а со шкафчиками в раздевалке.
ну и прочие задачки на теорию вероятности, комбинаторику и производительность алгоритмов
Там были еще вопросы по языку и API (java) и общие вопросы по технологиям (сети, SQL, скриптовые языки), но это всё достаточно традиционно для IT-собеседований
Вообще, по совокупности впечатлений от нескольких людей, собеседовавшихся в гугле, можно заключить, что там ценят в большей степени «академические» знания, чем практический опыт.
Уж не знаю, оправдано ли это их процессом разработки или это особенность тех людей, которые проводят собеседования.
Было бы интересно узнать, какие требования к людям у них были лет 6 назад.
В случае телефонного интервью условия должны быть аналогичные обычному интервью. А именно — нет отвлекающих факторов, возможность записать уловие и набросать решение на листе бумаги.
_ — отрыта
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
вообще м да, но где то в первом ошибка у меня
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_
И она как раз первая и будет
допустим, для простоты, что у нас 8 коробок
Будет сколько проходений человека, открывающего-закрывающего коробки? Правильно: 7, потому что он сначала он меняет состояние каждой 2-й коробки, потом каждой 3-й… потом каждой 8-й.
Получаем:
ОООООООО
ОЗОЗОЗОЗ
ОЗЗОЗООЗ
ОЗЗЗЗООО
ОЗЗЗЗЗОО
ОЗЗЗЗЗЗЗ
ОЗЗЗЗЗЗЗ
где:
О — открыто, З — закрыто
P.S.: В моноширинном шрифте нагляднее бы смотрелось))
Два менеджера по персоналу опытный и стажёр сидят в офисе и обсуждают
дела. Молодой достает огромную пачку резюме, штук 300: «Мы должны просмотреть
их все, чтобы подобрать кандидатов на эту вакансию». Опытный
хладнокровно берет у него пачку, делит ее пополам, одну часть на стол,
вторую в шреддер. У молодого глаза по пятаку: «А как же претенденты?!»
Опытный невозмутимо: «А зачем нам неудачники?»
$openboxes = floor(sqrt($n));
У предыдущего докладчика ошибка, там надо
$openboxes = n — floor(sqrt($n));
для 2-ки:
2^2 = 4
2^4 = 8
2^6 = 32
3-ка:
3^2 = 9
3^4 = 81
И т. д. Но нужно
1) доказать что они и только они
2) как-то выразить всю эту лабуду через N
oxxxoooxxxoooxxxoooxxxoo
oxxoooooxxoxoxxoooooxxox
oxxoxoooxooxoxoooooxxxox
oxxoxxooxooooxoooxoxxxoo
oxxoxxxoxooooooooxoxoxoo
oxxoxxxxxooooooxoxoxoxox
oxxoxxxxoooooooxoooxoxox
oxxoxxxxoxoooooxoooooxox
oxxoxxxxoxxooooxooooooox
oxxoxxxxoxxxoooxoooooooo
oxxoxxxxoxxxxooxoooooooo
oxxoxxxxoxxxxxoxoooooooo
oxxoxxxxoxxxxxxxoooooooo
oxxoxxxxoxxxxxxooooooooo
oxxoxxxxoxxxxxxoxooooooo
oxxoxxxxoxxxxxxoxxoooooo
oxxoxxxxoxxxxxxoxxxooooo
oxxoxxxxoxxxxxxoxxxxoooo
oxxoxxxxoxxxxxxoxxxxxooo
oxxoxxxxoxxxxxxoxxxxxxoo
oxxoxxxxoxxxxxxoxxxxxxxo
oxxoxxxxoxxxxxxoxxxxxxxx
Но решать такие задачки на улице без чего-нить под рукой, где даже не сконцентрируешься — нафик, нафик…
2 — закр
4 — откр
6 — закр
12 — откр
24 — закр.
Открытой останется первая коробка, потому как отсчет ведется от 2 до N, и поэтому каждая не первая коробка будет рано или поздно закрыта.
Мне кажется это был тест на личные качества, а не про коробки.
то на личные качества тест пройден, а теперь на умение решать подобные задачи?!
Человеку — человеческое.
А на точность вычислений пусть google арифметику тестирует.
Ответ = f(N)
f(N) =… <тут ответ>
открытыми останутся коробки в количестве равном округленному в меньшую сторону корню из N?
Понятно, что решение верное, но никак не могу понять этот переход.
Разобрался таки с решением. Опишу — вдруг кому также как и мне — «не очевидно».
Из вышестоящих ответов ясно, что коробка останется открытой, если у ее номера — числа М — будет четное количество делителей от 2 до М включительно (т.е. ее тронут четное количество раз).
Разложим число М на простые множители. Каждый из них будет в четной или нечетной степени.
пусть — i, j, k… и т.д. степени простых множителей. Каждый делитель нашего числа М состоит из всех его простых множителей в степенях от 0 до i (до j, до k и т.д.). Т.е. всего делителей будет Д = ((i+1)(j+1)(k+1)… — 1 ) вычитаем 1 т.к. вариант, когда все множители в степени 0 нам не нужен (1 не считаем делителем в нашем случае). Чтобы число делителей Д было четным, нам нужно, чтобы произведение было нечетным. Произведение чисел может быть нечетным тогда и только тогда, когда все они нечетные. Таким образом — все степени i, j, k… простых множителей должны быть четными. Если все степени простых множителей четные — то число является полным квадратом. чтд.
ps. не знаю, как это может быть очевидным… Уж тем более смутно представляю как такое можно провернуть в уме и по телефону.
F(N) = sum(1 — A(i) mod 2)
i=1… N
A(i) — количество простых множителей с учетом кратности.
Попроще не придумывается формулы…
Тоже пришел к такому-же результату.
Ответ пришел через 2 месяца, когда уже был, по сути, не нужен.
Тормоза.
Примерно так.
$M=floor(sqrt(N));
т.е. при любом значении N количество открытых коробок будет корень из N с округлением до меньшего целого.
По моему посчитать количество простых чисел на интервале и то проще ;/
Имхо, таким способом можно потерять кучу толковых ребят )
Если N коробок = 2, то открыто N/2 коробок
Если N коробок = 3, то открыто (N/2)-1 коробок
Если N коробок = 4, то открыто N/2 коробок
Если N коробок >= 5, то открыто (N/2)-1 коробок
тестировал только на маленьких значениях, но мне кажется что тенденция (N/2)-1 сохраняется
Т.е. для чётных N/2, а для нечётных (N-1)/2.
При четном количестве коробок — остается 2 открытых коробки
А при нечетном — 3 коробки открыты
Если с начала ряда, то открытой останется первая коробка, потому как отсчет ведется от 2 до N, и поэтому каждая не первая коробка будет рано или поздно закрыта.
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()а если ящиков больше 40? скажем 400?
Но самой логики ваших абстрактных рассуждений это не меняет.
Вы серьезным голосом скажите мой ответ 666.
А как я добивался возврата денег за самолет — это вообще песня, я прозрел от несоответствия всем тем красивым картинкам в интернете. С их конкурсом на место они действительно могут себе позволить и иногда позволяют неуважительное отношение к кандидатам. Погуглите «google job interview».
Надо был говорить «сейчас не могу, давайте позже».
Теперь по поводу решения задачи: тут сразу понятно, что все коробки с номером, которое является простым числом, будут закрыты, поскольку по ним можно пройти только один раз. Остальные же коробки будут закрыты или открыты в зависимости от количества простых делителей номера коробки и степеней их вхождения. В общем, какую-то универсальную формулу вывести довольно-таки сложно, тем более на ходу по телефону.
количество разных делителей будет равно ((2^k)-1)*n1*n2*n3...*nk. Если это число четное, то коробка будет открытой, нечетная — закрытой.
Ответ: Целая часть от корня числа N.
$boxes = array();
for ($i=0; $i<$n; $i++) {
$boxes[] = true;
}
for ($del = 2; $del <= $n; $del++) {
for ($num = ($del-1); $num <= ($n-1); $num += $del) {
if (isset($boxes[$num])) {
unset($boxes[$num]);
} else {
$boxes[$num] = true;
}
}
}
return count($boxes);
}
for ($i=1; $i<100; $i++) {
echo $i.':'.calcOpenBoxes($i).«\n»;
}
Результат:
1:1
2:1
3:1
4:2
5:2
6:2
7:2
8:2
9:3
10:3
11:3
12:3
13:3
14:3
15:3
16:4
17:4
18:4
19:4
20:4
21:4
22:4
23:4
24:4
25:5
26:5
27:5
28:5
29:5
30:5
31:5
32:5
33:5
34:5
35:5
36:6
37:6
38:6
39:6
40:6
41:6
42:6
43:6
44:6
45:6
46:6
47:6
48:6
49:7
50:7
51:7
52:7
53:7
54:7
55:7
56:7
57:7
58:7
59:7
60:7
61:7
62:7
63:7
64:8
65:8
66:8
67:8
68:8
69:8
70:8
71:8
72:8
73:8
74:8
75:8
76:8
77:8
78:8
79:8
80:8
81:9
82:9
83:9
84:9
85:9
86:9
87:9
88:9
89:9
90:9
91:9
92:9
93:9
94:9
95:9
96:9
97:9
98:9
99:9
На счёт сложности посчитать в уме… На сколько я помню, в вышке есть некий метод для примерного вычисления корня. И наверное, зная этот метод можно было бы, наверное, и догадаться.
— если число делителей четное, то коробка открыта;
— если число делителей нечетное — коробка закрыта.
Т.е. подсчитав кол-во чисел от 1 до N, имеющих четное число делителей можно узнать кол-во открытых коробок.
Вообще, имхо, если можешь решить задачку — тебе нефиг делать в Гугле… Делай свой ГУГЛ!!! В смысле -стартап ;-)
Вы правы
это, как показывает опыт, квадраты, четрвертые, восьмые и т.д. степени простых чисел.
А возможно ли это для других?
Число можно разложить на простые. Если их n и они не повторяются, то количество комбинаций из них будет равно 2^n. То есть будет четным.
Если среди же мы добавим n+первое число, равное числу x из присутствующих n чисел, то добавится еще одна комбинация на каждую комбинацию, где есть x.
А остальных комбинаций, где x нет — их четное количество, так как они собраны из n-1 простых чисел!
То есть полюбому в сумме получаем четное число комбинаций
Значит, другие открытые ящики, кроме четных степеней простых чисел, невозможны.
Если число не является квадратом, то все его делители идут парами: если a — делитель, то n/a — тоже делитель.
Если же является квадартом, то все делители идут парами, кроме собственно корня из n.
Но так как мы не берем в расчет единицу, то у всех чисел не являющихся точными квадратами нечетное число делителей, а у квадартов — четное.
Таким образом (как уже несколько раз написнао выше), ответ — количество точных квадратов до n, то есть floor(sqrt(n)).
Может, он дома в тапочках, а рядом… компьютер, браузер и Гугл!
Учитывая, что люди редко занимаются решением подобных задач, ибо их работка куда более приземленная и конкретная, сходу такую задачку мало кто решит. Ибо сходу подразумевает практически знание алгоритма.
Вот если бы человеку дали листок бумаги и ручку… посадили бы в тихом помещении, где бы на него никто не зырил и не мешал… то я думаю решили бы многие.
На практике же такие методы никакой пользы не приносят. Ибо программер — это специфика.
У меня знакомый есть который который на память помнит практически все ядро винды в асме. Может вам сказать что происходит когда вы файлик перетягиваете, или путь прописывает… Он возможно эту б задачу и не решил, но зато он такие трояны под винду пишут, который покупаются за бешенные деньги.
Нет если конечно ребятам нужен чел для решения задачек… то это канешно правельно, иначе же фигня.
Если нужно узнать насколько креативен человек, дайте ему обычное задание, где кратко описан результат, но не описан функционал. И посмотрите как человек это реализует. Если нужно глубже, дайте позаковырейтей задание, но по той же методе.
Вы получите достоверный результат который легко сравнивается. Тем самым можно сортировать людей по уровню. Что куда лучше методы решил/не решил, да еще и что то аморфное.
ЗЫ: из личного опыта меня поражало когда человеку давали на собеседовании такие задачки, а потом когда брали на работу давали обычные рутинные задачи, без возможности креатива.
Тут появляется вопрос… а нах они давали эти задачки?
ЗЫЫ: еще помню был момент, когда на такую задачку я человеку задавшему ее задал одну из простых которую можно решить на пальцах… за 15 мин он ее так и не решил. В итоге я сказал ему звонить мне когда решит… тогда прийду на собеседование. Вот есть логика в том что чел задает вопрос на который сам не знает ответ. Выходит что идиот оценивает умного. Что по сути бред.
Сомневаюсь, что гугл интересуется троянами под винду.
test.chubin.ru/task/
>>У всех чисел от 1 до N (кроме полных квадратов) есть четное (2k) количество делителей — то есть действие
>>«закрыл-открыл» происходит k раз и в результате всё равно коробка открыта остается
Для всех чисел кроме квадратов коробки как раз останутся закрытыми, потому что каждую первую мы никогда не закрывали. А открытыми останутся только квадраты.
Именно поэтому решением и является floor(sqrt(N)), как вы верно и сказали.
Спасибо за пост.
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))
Поставил на антиспам-бот в ICQ.
В прошлом году ходил к ним на собеседование — не взяли.
Жаль не объясняют почему.
Впрочем, у меня 2 варианта:
а) ужасный английский
б) мы не поняли друг друга со вторым человеком, который проводил собеседование
Рассмотрим коробку с номером X. Человек касается этой коробки на шагах i = 1… X таких, что X делится на i. После шага X человек этой коробки уже не касается и она остается открытой или закрытой.
Конечное состояние зависит, таким образом, от числа делителей X. Например, у 6 четыре делителя: 1, 2, 3, и 6. Соответственно человек коснется коробки номер 6 четыре раза, а раз мы начали с закрытого состояния (см. самое начало), то она и останется закрытой.
Очевидно, что нам не нужно знать все число делителей, а достаточно только знать четное оно или нечетное. Нечетное число делителей бывает только в том случае, если при делении получается тот же результат, т. е. у квадратов: 1, 4, 9, 16, 25 и т. д.
Таким образом, все коробки с данными номерами будут открыты, а все остальные закрыты.
(Ни за что бы не решил по телефону. Пойду почитаю, что другие написали.)
По самой задаче — если честно, в условиях, описанных автором, не решил. Но в целом вы идете правильным путем. Надо было сказать, что их будет столько, сколько чисел от 1 до N имеют нечетное количество делителей.
тут все указывает на стресс-интервью, человеку звонят неожиданно, и дают задачу, практически не решимую за короткое время. HR-менеджеры тоже не идиоты и все понимают. Важно то, как среагирует кандидат, будет мямлить, предложит нестандартный выход или что-то еще
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();
}
имхо на это способны либо люди которые решали эту задачу, либо гении (может только их на работу в гугл и надо)
Видимо, у них столько народу просится, что они могут искать не просто людей решаюзих таких задачки, но людей решающих такие задачки без напряга и походу. Когда я учился в институте, в моей группе человек 5 было, которые вполне способны были на такой трюк, я не про точный ответ, я про то, что сразу бы нашли правильный способ найти этот ответ. Это как правило те люди, что побеждали на олимпиадах по матиематике, физике или програмированию.
«Потому что до этого поросята видели волка только на картинке» — из детской сказки…
Я согласен, иногда, особенно на последних курсах бывают ситуации, что оценки ставятся накатом, например студент откровенно сдал на 3 или 4, но в зачётке у него одни пятерки и преподу приходится ставить 5, но именно на этот случай я написал «не просто так».
В общем я считаю, что если человек учится на 5, и 5 соответствует знаниям, а не стечению обстоятельств — то он обязан решить такую задачку. =)
И опять же если человек решает подобную задачу, но учится на 3 и 4 — это говорит о том что он умен, но ленив, или ему неинтересен предмет (за редким исключением виноваты обстоятельства, в виде особо злобных преподов). Зачем Гуглу ленивые или не интересующиеся люди?
как пример могу привести зазубривание теорем перед экзаменом. ведь можно понять как её доказать, что и сотворить при необходимости, а можно выучить доказательство как стишок да забыть через месяц. так вот многие из получающих пять очень любят второй метод. но ведь это не знания?
А, знания — это то что остается, когда вы все забудете =)
— Как к свехрурочным относишься? Хорошо?
— Хорошо
— А если надо, обжать кабель вместо админа сможешь?
— Смогу.
Ну ладно… Слушай задачу. К бассейну подведены две… а ну и фиг сней! Берем!
Вначале было 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
Самый главный вопрос в какую сторону округлить :)
я подсчитал кол-во коробок, которые изменят свое состояние, то есть будут закрыты.
Открытых соответственно будет N * (1 – ln 2) ~ 0.31 * N
После корпоративки неверно прочитал условие задачи! :)
Я понял так, что коробки по очереди на одном шаге закрываются, а на следующем открываются. А они меняют состояние, в таком случае ряд будет совсем другой, навроде:
1/2 - 1/8 + 1/16 - 5/128 + ...А это именно разложение sqrt(N)
Сорри, кого сбил с толку!
Задача легко решается итерацией: каждый номер проходится столько раз, сколько у него делителей, включая само число и исключая единицу. Следовательно только полные квадраты останутся открыты: они будут пройдены чётное число раз. Следовательно, правильный ответ: квадратный корень из N, округлённый вверх (не забывайте про первый ящик, что всегда открыт).
Открыты: 1 (он же первый квадрат), 2-й квадрат — 4, 3-й — 9 и т.д. сколько умещается, по скольку искомый номер, одновременно является корнем, то ответ — округлённый корень.
А в том, что действительно не надо дергать человека посреди улицы.
Ответ: 3
Жирным шрифтом выделены изменения состояния.
Слева номера шагов.
Желтым выделены открытые коробки.
можно было бы не растеряться, и сказать, мол, извините, сейчас не могу говорить (вдруг он ведет авто), перезвоните через n минут, или позвольте, я вам перезвоню.
Это нормальная ситуация, и нечего перед гуглем падать на колени и боготворить его.
Но это в идеале.
… И такой случай НЕ показывает высокую компетентность их эйчарников.
Задача:
Все коробки открыты. Проходим по КАЖДОЙ второй и закрываем ее. Проходим по КАЖДОЙ третьей и если она открыта, закрываем, если закрыта, открываем. Проходим по КАЖДОЙ четвертой…
Уберите слово «КАЖДОЙ».
Получится:
Все коробки открыты. Закрываем вторую. Закрываем третью. Закрываем четвертую. Закрываем пятую…
Необходимость закрывать КАЖДУЮ сбивает с толку.
Хотя вот сейчас сомнения закрались… завтра опыт поставлю.
Все коробки открыты. Закрываем вторую. Закрываем третью. ОТКРЫВАЕМ четвертую. Закрываем пятую…
как-то страшно стало :)
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 подобный ряд предлагали дополнить в анкете в военкомат. =)
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
Действительно, каждый следующий открытый ящик отстоит от предыдущего на два ящика больше, чем предшественник.