2. я правильно понял, что в массиве содержатся числа только из диапазона 0-(N-1)? n-битная переменная учета встреч (один бит на каждое число) - это много памяти? =) Можно посчитать сумму элементов Q. Тогда Q-(n-1)*(n-2)/2=повторяющееся число, но получается сложность 2*N.
Третью не понял. В первой кажется, что для утки все безнадежно, но быстро доказать не получается.
О результатах собеседования напишешь (тьфу-тьфу, стук-стук)?
Про сумму не поняла. Для утри все не безнадежно, это я знаю. На этом собеседовании у меня не было шансов.
Бензоколонки стоят по кругу. Мы знаем сколько на каждой бензина и сколько от нее до следующей км. Ехать можно только по кругу. Надо придумать алгоритм определения с какой нужно ехать. Чтобы доехать до конца.
утка да, может. ей сначала надо по полокружности радиусом 1/8 от радиуса пруда проплыть (в то время лиса пробежит четверть своего круга). а потом напрямик до берега. но это скорее геометрическая задачка..
2.целые или целые больше нуля? что такое много памяти??
3.ну я бы сделала массив из чисел (сколько в бензоколонке бензина - на сколько его хватит). если сумма отрицательная - вообще ничего не выйдет, а если нет, но дальше его надо уменьшать, схлопывая плюсики с минусиками и сохраняя номер самой левой бензоколонки каждый раз. когда останутся одни плюсики - начинать с любого. сложность что-то вроде 2N должна получиться
1.чтоб лиса пробежала как можно большее расстояние по периметру круга, утка должна заворачивать)) от прямой (ну, самый изначальный вариант), но так, чтобы лиса не подумала, что ей быстрее с другой стороны - т.е. утка должна находиться всегда на диаметре большого круга (пруда). это и получается полуокружность (ну там теорема об угле между касательной и хордой), а учитывая отношение скоростей, радиус полукруга должен быть равен 1/8r. тогда, когда лиса пробежит четверть пруда, утка окажется там где надо - на расстоянии 3/4 от края когда лиса на противоположенном берегу.. и тогда лисе остается pi*r, а утке 3/4*r. 3r утка успевает.. ну, как-то запутанно объяснять словами))
Comments 11
Можно посчитать сумму элементов Q. Тогда Q-(n-1)*(n-2)/2=повторяющееся число, но получается сложность 2*N.
Третью не понял. В первой кажется, что для утки все безнадежно, но быстро доказать не получается.
О результатах собеседования напишешь (тьфу-тьфу, стук-стук)?
Reply
Бензоколонки стоят по кругу. Мы знаем сколько на каждой бензина и сколько от нее до следующей км. Ехать можно только по кругу. Надо придумать алгоритм определения с какой нужно ехать. Чтобы доехать до конца.
Reply
2.целые или целые больше нуля? что такое много памяти??
3.ну я бы сделала массив из чисел (сколько в бензоколонке бензина - на сколько его хватит). если сумма отрицательная - вообще ничего не выйдет, а если нет, но дальше его надо уменьшать, схлопывая плюсики с минусиками и сохраняя номер самой левой бензоколонки каждый раз. когда останутся одни плюсики - начинать с любого. сложность что-то вроде 2N должна получиться
спасибо за задачки)
Reply
2. Целые больше нуля. Там было написано что-то вроде, что можно создать несколько переменных в стеке.
3. Есть более изящное решение.
Reply
утка успевает.. ну, как-то запутанно объяснять словами))
ну 2-ю и 3-ю потом расскажешь как-нить..
Reply
Reply
Leave a comment