Пятничные задачки. Вася Пупкин еще жив ;)

← →
MBo © (2007-11-16 09:00) [0]

1. Васе Пупкину поручили организовать сообщение с резидентом разведки в некой
стране. У Васи имеется микросейф с двумя замками A и B и два ключа от замка A.
У резидента есть два ключа от замка B. Сейф с документами будет пересылаться
обычной почтой. Как застраховаться от утечки информации при пересылке сейфа туда-сюда?

2. Вася Пупкин в полдень посадил на секундную стрелку часов муху и стал за ней
наблюдать, причем он заметил, что поведение мухи таково:
Если муха обгоняет какую-то стрелку, или ее обгоняет какая-то стрелка
(кроме секундной, у часов есть часовая и минутная стрелки),
то муха переползает на эту стрелку.
Чтобы это занятие не было пустым времяпрепровождением,
он почти по совету Козьмы Пруткова стал считать, сколько она проедет кругов.
Так сколько кругов проедет муха в течение часа?

3. Опять про муху ;)
Летела муха со скоростью метр в секунду.
И вдруг начала ускоряться по такому принципу:
каждый раз, пролетая еще один метр, она удваивала скорость.
Оцените время облета вокруг земного шара по экватору,
считая с того самого момента, когда Муха начала ускоряться.
З.Ы. пусть скорость света равна бесконечности

4. Вася Пупкин лег спать между 23 и 24 часами, а встал между 8 и 9 часами.
Сколько времени (точно) он проспал, если минутная и часовая стрелки в
момент начала и конца сна поменялись местами?

5. а) Дан массив целых чисел, в котором все числа встречаются дважды,
а одно не имеет пары, например, (2,3,4,3,2)
Найти это число за линейное время с использованием лишь O(1) памяти
б) А теперь в массиве два непарных числа, например, (1,2,3,1).
Можно ли при тех же ограничениях найти оба числа?

(Alx2 нашел хорошее решение с использованием QuickSort-подобного алгоритма,
однако существует и более простой метод)

6. Многие знают навскидку степени двойки до 2^32 ;)
Может, заметили, что в десятичной системе среди них ни одно число не начинается
с 7-ки. Существуют ли такие 2^N и если да, то как часто встречаются по сравнению с другими начальными цифрами.

7. Дан массив A[0.. 2 * M - 1] of Integer.
Нужно эффективно переставить элементы так, чтобы элементы с четными индексами находились
в начале, с нечетными - в конце, и относительны порядок сохранился
Пример: 0 1 2 3 4 5 6 7 - > 0 2 4 6 1 3 5 7

← →
Юрий Зотов © (2007-11-16 09:07) [1]

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

← →
MBo © (2007-11-16 09:15) [2]

>Первый раз Вася посылает резиденту сейф с одним ключом A, второй ключ А оставляет себе. Резидент возвращает ему сейф с одним ключом

если сейф закрыт на A, то резидент не сможет достать ключ из сейфа и положить свой

← →
Юрий Зотов © (2007-11-16 09:17) [3]

> MBo © (16.11.07 09:15) [2]

А ключ при пересылке должен быть обязательно внутри сейфа?

← →
MBo © (2007-11-16 09:18) [4]

>А ключ при пересылке должен быть обязательно внутри сейфа?
Да, иначе почтальоны скопируют

← →
J_f_S (2007-11-16 09:21) [5]

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

← →
Bless © (2007-11-16 09:30) [6]

1) Ложим ключ А в сейф, закрываем на замок А, шлем резиденту.
2) резидент закрывает сейф на замок В, шлет обратно.
3) Открываем замок А (В по-прежнему закрыт), отсылаем обратно резиденту.
4) Резидент открывает замок В, от которого у него есть ключ, и достает ключ А из сейфа, имея полный комплект.

P.S.
Долгих лет жизни Василию!

← →
БарЛог (2007-11-16 09:32) [7]

Первый раз посылаем закрытым только на Б, второй раз - только на А :)
Недостающие ключи - внутри сейфа.

← →
MBo © (2007-11-16 09:43) [8]

>Bless © (16.11.07 09:30) [6]
Верно.
Подобным же образом можно и второй ключ Васе переслать, если возникнет желание.

← →
Anatoly Podgoretsky © (2007-11-16 09:44) [9]

> Bless (16.11.2007 09:30:06) [6]

> Долгих лет жизни Василию!

И как он только не свихнется, каждую неделю такой стресс, все не как у нормальных людей.

← →
KSergey © (2007-11-16 09:52) [10]

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

У него одно отделение, доступ в которое из 2-х различных дверец? У него одна дверца с двумя замками (открывается только когда оба замка открыты)? у него у него 2 отделения и в каждое своя дверца?

отсюда и ответы слишком разные, т.к. каждый функционирование сейфа понимает по-своему.

← →
KSergey © (2007-11-16 09:56) [11]

> KSergey © (16.11.07 09:52) [10]

лана, если ответ верный есть - то понятно.

← →
oldman © (2007-11-16 09:57) [12]

4.
Лег спать в 23.14
Встал в 8.56
Спал 9 часов 42 минуты.

Плюс-минус несколько минут. Лень точно углы считать.

← →
oldman © (2007-11-16 10:01) [13]

7. По очереди нечетные элементы переставляем в конец списка.
Просто в конец, сдвигая все остальные вверх.
Прикольно, что в цикле надо переставлять элементы 2,3,4,5,6 и т.д...
То есть, в начальном списке 1 занимает второе место, 3 - четвертое, но после перестановки 3 занимает третье место :)))

← →
oldman © (2007-11-16 10:04) [14]

> Bless © (16.11.07 09:30) [6]

То есть четыре раза сейф напрасно катается туда-сюда.
А документы внутри резиденту по фигу?

← →
oldman © (2007-11-16 10:07) [15]

А если ключи есть только у Васи и у резидента на фига ДВА замка???
:))))))))))

← →
palva © (2007-11-16 10:09) [16]

3. Первый метр муха пролетела за одну секунду, второй за 1/2, третий за 1/4, потом будет 1/8 1/16 ... 1/(2^n). Если мы суммируем все эти времена, то получим 2. То есть двух секунд мухе будет достаточно, чтобы пролететь как угодно большое расстояние.

← →
oldman © (2007-11-16 10:11) [17]

> palva © (16.11.07 10:09) [16]

Если ответ правильный, то класс!!!
:)

← →
Jeer © (2007-11-16 10:12) [18]

3. Муха покроет любое расстояние не более чем за 1.3(3) сек.

← →
TUser © (2007-11-16 10:17) [19]

6 было уже. Да, встречаются, статистически столь же часто, как и все остальные.

← →
MBo © (2007-11-16 10:18) [20]

> oldman © (16.11.07 09:57) [12]
14 минут и 8 часов - стрелки не совпадают

>palva © (16.11.07 10:09) [16]
>То есть двух секунд мухе будет достаточно, чтобы пролететь как угодно большое расстояние
точно ;)

>oldman © (16.11.07 10:01) [13]
Придется много раз сдвигать одни и те же элементы.
Быстрее всего, конечно, использовать еще один такой же массив, и скопировать элементы на свои места. Но это расточительно по памяти.
Твой способ передвигает на месте, но имеет квадратичную сложность.
Интересно было бы найти метод перепаковки с минимальным потреблением памяти и как можно быстрее (линейный)

← →
MBo © (2007-11-16 10:19) [21]

> статистически столь же часто, как и все остальные
неверно

← →
oldman © (2007-11-16 10:21) [22]

> MBo © (16.11.07 09:00)
> 7. Дан массив A[0.. 2 * M - 1] of Integer.

Сдается мне, что 0 ... 2*М-1 это массив нечетных чисел.
Или, а что тогда такое М?

← →
MBo © (2007-11-16 10:21) [23]

>Сдается мне, что 0 ... 2*М-1 это массив нечетных чисел.
>Или, а что тогда такое М?
Имеется в виду массив четной длины.

← →
Колхоз (2007-11-16 10:22) [24]

Еще задачки:

> Васе Пупкину поручили организовать сообщение с резидентом
> разведки в некой
> стране.

Как он до "организации сообщения" связался с резедентом, дабы пояснить алгоритм этого самого сообщения ?

> У Васи имеется микросейф с двумя замками A и B и два ключа
> от замка A.

Микро это -6 степень, какимиже должны быть ключи ?

> У резидента есть два ключа от замка B.

Кто передал ключи резеденту ?

> Сейф с документами будет пересылаться
> обычной почтой.

Какова цена документов, если резедент не сможет их прочесть, т.к., сейф -6 степень ?

> Как застраховаться от утечки информации при пересылке сейфа
> туда-сюда?

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

← →
oldman © (2007-11-16 10:23) [25]

> MBo © (16.11.07 10:18) [20]
> > oldman © (16.11.07 09:57) [12]
> 14 минут и 8 часов - стрелки не совпадают

А где будет часовая стрелка в 8:56?

← →
oldman © (2007-11-16 10:32) [26]

7. Можно так:
Для k=1,3,5,...,2*М-3 меняем местами элементы k и k+1
Повторяем, меняя границы...

Пример:
0(12)(34)(56)7
02(14)(36)57
024(16)357
02461357

(ij) - пары перестановок

← →
Bless © (2007-11-16 10:33) [27]

4-я задача.
Вася спал 9 часов , 13 минут плюс 11/13 минуты :)

← →
palva © (2007-11-16 10:33) [28]

> Как он до "организации сообщения" связался с резедентом, дабы пояснить алгоритм этого самого сообщения ?

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

Условие границ неправильно написал... :(

> MBo © (16.11.07 10:19) [21]
> > статистически столь же часто, как и все остальные неверно

?

7*10^k<=2^n<8*10^k
ld7+k*ld10<=n<3+k*ld10

Рассмотрим окружность радиуса ld10. Числа из обозначенных интервалов все занимают некоторый участок такой окружности. Шагая по окружности с шагом 1 мы обязательно будем попадать в этот интервал (длина окружности иррациональна). Причем столь же часто, как и во все остальные. Потому что, если мы реже попадаем в этот интервал, чем в среднем, то мы реже попадаем и в интервал с границами, сдвинутыми на единицу, и на 2 и т.д., а в силу иррациональности длины окружности, мы реже попадаем в любую точку окружности, чем в среднем, чего быть не может.

> palva © (16.11.07 10:09) [16]

> 3. Первый метр муха пролетела за одну секунду, второй за
> 1/2,

> MBo © (16.11.07 10:18) [20]

> точно ;)

Я исходил из равномерного ускорения мухи в пределах метра, что естественно для "обычной" физической мухи, а изменение скорости скачком в конце каждого метра посчитал для нее не выполнимым:))

В этом случае:

Первый метр муха пролетит не за 1 сек, т.к. в начале этого метра она имела скорость 1 м/с, а в конце этого метра уже 2 м/c
Следовательно, средняя скорость мухи на первом метре равна (1 + 2)/2 = 1.5 м/с
Отсюда очевидно, что время пролета первого метра dT = S/Vср = 1/1.5 = 2/3 с

Рассуждая аналогично определим, что на втором метре средняя скорость равна Vср = (2 + 4)/2 = 3 м/c и время dT = 1/3 = 2/6

И так далее.

Т.е. мы имеем прогрессию T = 2/3 + 2/6 + 2/12 + ... которая имеет пределом именно 1.3(3)

> Jeer © (16.11.07 10:40) [31]

Читаем условие:

> каждый раз, пролетая еще один метр, она удваивала скорость.

Видимо таки скачком...
:)))

> palva © (16.11.07 10:42) [32]
> Jeer © (16.11.07 10:40) [31]
> Ну да, принцип тот же, только цифры немного другие.

Твой-то ответ тоже правильный.
При пределе1,3(3) двух секунд ей за глаза, чтоб пролететь сколько хочет...

> oldman © (16.11.07 10:44) [33]
>
>

> Читаем условие:
>
>
> > каждый раз, пролетая еще один метр, она удваивала скорость.
>

Условие скачка нечетко выражено.

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

Здесь нет вопросов.

"Богат могучим русский языка"

1.
послали сейф - 1
не послали - 0
и так передать все что надо сказать. А ключи выкинуть нафиг

5. а)

function FindUnmatched(const A: array of Integer): Integer; var I := 0; begin Result := 0; for I := Low(A) to High(A) do begin if Result > A[I] then Result := Result - A[I] else Result := Result + A[I]; end; end;

PS: Интересно, скомпилится ли вообще, давно на Delphi не писал и сейчас проверить не на чём.

> [39] Sha © (16.11.07 11:35)

Точно, не подумал.
Зато так будет работать и с Double :)

> var I := 0;

конечно же
var I: Integer;

Пятничные задачки. Вася Пупкин еще жив ;) Найти похожие ветки