• Zero tolerance mode in effect!

Задачи, головоломки, загадки


Весы наклонятся вправо.

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

А в правой чаше это не компенсируется. Сила действующая на правую чашу больше на ту величину на которую меньше натяжение нити на котором шарик висит.

Другой способ посмотреть на задачу: шарик погружённый в стакан воды приводит к повышению уровня воды, а т.к. давление воды линейно зависит от высоты, то, следовательно, давление на дно чаши растёт. Но на левую чашу также действует сила натяжения нити (вверх).
Следовательно но правую чашу действует бОльшая сила.
 
Так, скоро пятница, а значит пора закинуть вам задачку. Вот придумал специально для вас дорогие представители программеров, алгоритмистов, архитекторов и прочих кодеров (включая с приставкой быдло-).

1. Есть неизменяемый (read-only) массив целых чисел длиною N, в котором есть все числа от 1 до N+1 кроме одного. За один проход нужно найти отсутствующее число не выделяя места под новый массив. Это известная задача для начинающих быдлокодеров в экипаже. Может даже и в этой теме попадалась.

А вот вариация для продвинутых членов экипажа носящих городое имя Кодер.

Все то же, только в массиве сидят все числа от 1 до N+2 кроме двух! Нужно за один проход найти недостающие числа (опять же не выделяя отдельного массива).
 
Так, скоро пятница, а значит пора закинуть вам задачку. Вот придумал специально для вас дорогие представители программеров, алгоритмистов, архитекторов и прочих кодеров (включая с приставкой быдло-).

1. Есть неизменяемый (read-only) массив целых чисел длиною N, в котором есть все числа от 1 до N+1 кроме одного. За один проход нужно найти отсутствующее число не выделяя места под новый массив. Это известная задача для начинающих быдлокодеров в экипаже. Может даже и в этой теме попадалась.

А вот вариация для продвинутых членов экипажа носящих городое имя Кодер.

Все то же, только в массиве сидят все числа от 1 до N+2 кроме двух! Нужно за один проход найти недостающие числа (опять же не выделяя отдельного массива).

(1) - это классика жанра (xor)

(2) Здесь принцип такой, высчитываем две величины: сумму всех элементов, и сумму нелинейной функции всех элементов.
Например, квадратов (т.е. тумма квадратов всех элементов).

Если бы не было пропусков, то обе суммы были равны "каноническим" значениям (т.е. сумме от 1 до N+2, и сумме квадратов).
Отнимая из канонических сумм полученные мы получаем соответственно X = a+b и Y = a^2 + b^2 (имеется ввиду что a,b - пропущенные элементы).

Пропущенные значения получаем по формуле: a,b = [ X +/- (2Y - X^2)^(1/2) ] / 2
 
(1) - это классика жанра (xor)

(2) Здесь принцип такой, высчитываем две величины: сумму всех элементов, и сумму нелинейной функции всех элементов.
Например, квадратов (т.е. тумма квадратов всех элементов).

Если бы не было пропусков, то обе суммы были равны "каноническим" значениям (т.е. сумме от 1 до N+2, и сумме квадратов).
Отнимая из канонических сумм полученные мы получаем соответственно X = a+b и Y = a^2 + b^2 (имеется ввиду что a,b - пропущенные элементы).

Пропущенные значения получаем по формуле: a,b = [ X +/- (2Y - X^2)^(1/2) ] / 2
Отлично! Есть порох в пороховницах. Я так же решал, вернее именно под это решение задачу подобрал. Хотя можно было и вторую через xor решить.
На интревью можно задать доп. вопрос - как обойтись целыми?Квадраты могут не влезть в int, и тогда надо решать через xor, что менее очевидно.
 
Последнее редактирование:
Первая задача прекрасно решается без xor по той же самой канонической формуле.
 
Отлично! Есть порох в пороховницах. Я так же решал, вернее именно под это решение задачу подобрал. Хотя можно было и вторую через xor решить.
На интревью можно задать доп. вопрос - как обойтись целыми?Квадраты могут не влезть в int, и тогда надо решать через xor, что менее очевидно.

Разумеется это надо решать через целые числа, это не вопрос. И - да, в целые должно поместиться аж N^3 (сумма квадратов), а в процессе решения там возникает даже N^4. Следовательно это должен быть "целый" тип размером в 4 исходных типа.
Но это всё решается. Можно создать синтетический тип любого размера (просто массив int-ов) и эмулировать арифметические действия, это несложно.
Там надо извлечь квадратный корень - для этого на вскидку берётся старший ненулевой бит и сдвигается на половину, а затем уточняется медианным поиском (т.е. всякий раз возводим в квадрат и проверяем перебор/недобор).
 
Разумеется это надо решать через целые числа, это не вопрос. И - да, в целые должно поместиться аж N^3 (сумма квадратов), а в процессе решения там возникает даже N^4. Следовательно это должен быть "целый" тип размером в 4 исходных типа.
Но это всё решается. Можно создать синтетический тип любого размера (просто массив int-ов) и эмулировать арифметические действия, это несложно.
Там надо извлечь квадратный корень - для этого на вскидку берётся старший ненулевой бит и сдвигается на половину, а затем уточняется медианным поиском (т.е. всякий раз возводим в квадрат и проверяем перебор/недобор).

ОК. А теперь усложним немного. Допустим N столь велико, что для представления целых величиной до N требуется log N битов. Тогда для вычисления квадрата числа потребуется (log N)^2 операций если вычислять по школьному в столбик. Можно и быстрее но, все способы быстрого умножения больших чисел все равно медленнее чем log N. (Операция возведения в квадрат эквивалентна по сложности умножению - Почему? - доказать в качестве домашнего задания). Значит общая сложность алгоритма использующего суммы квадратов будет не лучше чем O(N * log N * log log N).

Теперь задача: найти алгоритм для поиска двух отсутствующих целых за ассимтотическое время в O (N * log N).
 
Решил привести один прикол от Айсека Асимова. Это не для того, чтобы insult your intelligence (ибо здесь эту задачку решат за считанные секунды), а просто делюсь шуткой юмора. Ингода задаю ее и получаю незамедлительно исключительно неверные ответы :)

Ситуация: два техника обслуживающие сверхмощный AI по имени Мозг споpят о чем-то, не могут договориться и наконец задают Мозгу вопрос:

Если 1,5 куры снесут за 1,5 дня 1,5 яиц, то сколько яиц снесут 9 кур за 9 дней?
 
Последнее редактирование:
ОК. А теперь усложним немного. Допустим N столь велико, что для представления целых величиной до N требуется log N битов. Тогда для вычисления квадрата числа потребуется (log N)^2 операций если вычислять по школьному в столбик. Можно и быстрее но, все способы быстрого умножения больших чисел все равно медленнее чем log N. (Операция возведения в квадрат эквивалентна по сложности умножению - Почему? - доказать в качестве домашнего задания). Значит общая сложность алгоритма использующего суммы квадратов будет не лучше чем O(N * log N * log log N).

Теперь задача: найти алгоритм для поиска двух отсутствующих целых за ассимтотическое время в O (N * log N).
Ну чо, не разочаровывают тебя супер-кодеры?

PS. Тока этта, по-моему, достаточно O(N) плюс O(1) доп памяти или я чота пропустил?
 
Ась? О чем это вы, парни? Любое число N в бинарном виде записывается (в твоей терминологии "состоит из") n=[log2(N)]+1 битами, где [] - целая часть. И шо дальше? Я реально чего-то не догоняю...
 
Ась? О чем это вы, парни? Любое число N в бинарном виде записывается (в твоей терминологии "состоит из") n=[log2(N)]+1 битами, где [] - целая часть. И шо дальше? Я реально чего-то не догоняю...

Имеется ввиду что когда мы работаем с "ordinal types" (int32/64), то операция с такими типами - это одна процесорная комманда. И при этом процессор совершает одновременно операции со всеми битами.

А теперь предположим что N настолько большой что не влезает в регистр (точнее - не влезают какие-то вспомогательные переменные которые надо высчитывать по ходу работы алгоритма).
В этом случае решение есть: надо представить наши переменные в качестве массивов достаточного размера, и самим "в столбик" эмулировать арифметические действия.
Так вот, в этом случае кол-во операций которое нам надо сделать зависит от размера нашего типа, т.е. от log(N).
 
А-а, вы про числа, которые не влазят в самое длинное слово. Ну, ладно, предположим. Только "числа длиной лог(Н)" тут по-прежнему ни при чем.

И какие арифметические действия надо эмулировать? Все решается ксорами.
 
Назад
Сверху Снизу