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

← →
MBo © (2007-01-26 08:15) [0]

1. Кот ловит мышку, которая прячется в одной из пяти норок.
Норки соединены между собой таким образом 0-0-0-0-0
Процесс ловли происходит следующим образом:
Кот сует лапу в одну из норок. Если мышь там - она поймана.
Если же нет - мышь перебегает в одну из соседних норок.
За какое минимальное количество ходов кот гарантированно ловит мышь?

2. Найти закономерность:
100 -> 2
981 -> 3
657 -> 1
123 -> 0
871 -> 2
256 -> 1
752 -> 0
376 -> 1
786 -> 3
739 -> 1
689 -> ?

3. Начальник отдела спецслужбы должен срочно встретиться с 4-мя агентами.
Он отдаёт распоряжение агентам, среди которых есть Джеймс,
прийти на встречу дождливым утром в 6, 7, 8 и 9 часов утра.
Они должны прийти на явку с зонтами разных цветов.
Однако вражеская спецслужба узнала о встрече и обладает следующей информацией:
1) Уилл придёт по той дороге, справа (при отсчете от перекрестка) от которой спустя час появится агент с зелёным зонтом.
2) У агента, который придёт в 9, не будет красного зонта, и он придет не с восточной, и не с западной стороны.
3) Джо и агент с голубым зонтом придут с разницей в час и приблизятся к месту встречи с противоположных сторон,
как и два других агента которые подойдут к месту встречи с разницей в час.
4) Агент с голубым зонтом, который придёт в парк на час раньше Бена,
появится не с западной стороны, он придёт по дороге, которая находится левее
той, по которой пришёл Бен.
5) У одного из агентов жёлтый зонт.
Необходимо определить с какой стороны, во сколько, кто и с каким зонтом
придёт на место встречи.

4. За 10 часов, сменяя друг друга, три землекопа выкопали яму. Каждый из них копал столько времени, сколько потребуется двум другим при их одновременной работе (имея две лопаты), чтобы выкопать половину ямы.
За какое время смогут выкопать яму эти землекопы, если у них будет три лопаты?

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

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

7. Числа Стирлинга 2 рода определяются так:
S(n,1) = 1
S(n,n) = 1
S(n,k) = S(n-1, k-1) + k*S(n-1,k)
По определению нетрудно составить рекурсивную функцию, но она будет довольно
медленной для больших аргументо (скажем, до миллиона). Как более эффективно вычислить S(n,k)?

8. Доказать, что в десятичной записи числа 2^99 по крайней мере 1 цифра
встречается по крайней мере 4 раза

9. Падишах решил проверить, стоит ли ему кормить своих 100 мудрецов,
или пришло время заменить. Он заказал шапки с помпончиками ста цветов,
по 200 каждого цвета, собрал мудрецов и сказал:
"У вас 3 часа на раздумье и договор. Вот вам каждому бумага, карандаш.
Завтра каждому наденут на голову шапку.
Какого цвета будет помпончик, вы знать каждый про себя не будете.
И покажут каждому всех других. И каждый должен написать,
какого цвета помпончик на нём. Если хоть один напишет правильно,
будете жить и продолжать служить. Нет - всем отрубят головы".
Могут ли мудрецы гарантированно сохранить свои головы и содержание?

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

← →
PZ (2007-01-26 08:24) [1]

2. Эта задача уже была здесь. Ответ известен.

← →
MBo © (2007-01-26 08:31) [2]

>2. Эта задача уже была здесь.
Пардон, забыл, значит...
Но наверняка найдутся те, кто не видел.

← →
PZ (2007-01-26 08:34) [3]

Я поэтому и не написал ответ

← →
MBo © (2007-01-26 08:41) [4]

Вот еще задачка на закономерность:

11. C удовольствием поменяю Новгород на Красноярск, Красноярск на Питер, Питер на Москву, Москву на Архангельск, Архангельск на Ярославль. А на что вы готовы поменять Ярославль?

← →
Брюнетка © (2007-01-26 08:43) [5]

>3.

6 часов - Джо, запад, красный зонт
7 часов - Уилл, восток, голубой
8 часов - Бен, север, зеленый
9 часов - Джеймс, юг, желтый

← →
SergP © (2007-01-26 08:59) [6]

5a ПроXORить все элементы массива и получим нужное число.

← →
Elen © (2007-01-26 09:04) [7]

> 10. Существуют ли такие 2^N, где число начинается с 7-ки.

Да. начиная с 2^46 и дальше их можно получить увеличивая степень на 6.

← →
Elen © (2007-01-26 09:04) [8]

> 10. Существуют ли такие 2^N, где число начинается с 7-ки.

Да. начиная с 2^46 и дальше их можно получить увеличивая степень на 10.

← →
Elen © (2007-01-26 09:05) [9]

От руки-крюки : [7] прошу считать опечаткой.

← →
Bless © (2007-01-26 09:13) [10]

А можно, я тоже добавлю?
Задачка для 8 класса:
пятизначное число x, деленное на произведение цифр этого числа дает 49.
Найти x

PS
эту задачку задали девочке в школе, которая попросила помощи у тети, которая попросила помощи у друга, который попросил помощи у меня.
:) Задачка несложная, но мое решение не слишком элегантно. Вдруг есть варианты получше?

← →
Elen © (2007-01-26 09:29) [11]

> 8. Доказать, что в десятичной записи числа 2^99 по крайней
> мере 1 цифра
> встречается по крайней мере 4 раза

Кажись решается так : Чтобы доказать что одно число повторяется хотя бы 1 раз нужно гарантированно иметь 10+1 знак в числе, значит 4-е раза число будет повторяться в 41-значном числе. Количество знаков я могу узнать по экспоненте :

2^2=8.0E+0 1-знак
3^2=6.4E+1 2-знака
4^2=1.0E+3 4-знака
5^2=3.3E+4 5-знаков
6^2=2.1E+6 7-знаков

Значит 2^99 - 100 знаков. т.е. числа гарантированно повторяются 4-е раза

Вроде так ;)

← →
Elen © (2007-01-26 09:30) [12]

Блин опять описка :

2^2=8.0E+0 1-знак
2^3=6.4E+1 2-знака
2^4=1.0E+3 4-знака
2^5=3.3E+4 5-знаков
2^6=2.1E+6 7-знаков

← →
MBo © (2007-01-26 09:40) [13]

>Брюнетка © (26.01.07 08:43) [5] >3.

Верно. Скользкий момент с понятием право-лево может поменять север и юг

>SergP © (26.01.07 08:59) [6] >5a
Ага, это классическая задача, а вот второй пункт похитрее

>Elen
Ну через 10 степеней - это нестабильно, т.к. 1024<>1000
А как можно объяснить, что семерка редко встречается?

>100 знаков. т.е. числа гарантированно повторяются 4-е раза
В десятичной записи - не 100 цифр.

← →
Elen © (2007-01-26 09:55) [14]

> В десятичной записи - не 100 цифр.

Ну точно больше 40.

← →
Брюнетка © (2007-01-26 09:56) [15]

>11. C удовольствием поменяю Новгород на Красноярск, Красноярск на Питер, Питер на Москву, Москву на Архангельск, Архангельск на Ярославль. А на что вы готовы поменять Ярославль?

На Хабаровск -)

← →
novill © (2007-01-26 10:00) [16]

8. в числе 2^99 тридцать один знак

← →
Elen © (2007-01-26 10:02) [17]

> Ну точно больше 40.

Не вру - не может 4 раза встретится.

← →
MBo © (2007-01-26 10:03) [18]

Брюнетка © (26.01.07 09:56) [15]
>11.
На Хабаровск -)

Точно ;)

← →
Alx2 © (2007-01-26 10:04) [19]

8. в 2^99 всего 30 знаков.
Если б каждой цифры было по три, то число делилось бы на 3, чего не наблюдается. Значит какая-то цифра встречается не менее 4 раз.

← →
MBo © (2007-01-26 10:04) [20]

>novill © (26.01.07 10:00) [16]
>8. в числе 2^99 тридцать один знак

Нет

← →
Alx2 © (2007-01-26 10:05) [21]

Вдогонку: кол-во знаков считаем как trunc(ln(n)/ln(10))+1 (8-й класс, кажется)

← →
MBo © (2007-01-26 10:05) [22]

Alx2 © (26.01.07 10:04) [19]
8. в 2^99 всего 30 знаков.
Если б каждой цифры было по три, то число делилось бы на 3

Верно.

← →
Elen © (2007-01-26 10:06) [23]

> novill

Да верно :

10=1.0E+3 4-знака
20=1.0E+6 7-знаков
30=1.1E+9 10-знаков
40=1.1E+12 13-знаков
50=1.1E+15 16-знаков
60=1.2E+18 19-знаков
70=1.3E+21 22-знака
80=1.3E+24 25-знаков
90=1.3E+27 28-знаков
100=1.3E+30 31-знак

Правильно 31 знак. Ну три раза точно повтор.
А калькуляторы врут ;)

← →
Elen © (2007-01-26 10:08) [24]

Ой. Опять руки-крюки. 31 знак для 100 - в общем Mith Busted!

← →
TUser © (2007-01-26 10:48) [25]

9. А жульничать мудрецы могут? Типа один подмигивает двум другим, значит на них одинаковые шапки.

← →
$Pl@Sh © (2007-01-26 11:36) [26]

> Кот ловит мышку

Кот Васи Пупкина ловит мышку :-)

← →
начинающий © (2007-01-26 11:42) [27]

> 11. C удовольствием поменяю Новгород на Красноярск, Красноярск
> на Питер, Питер на Москву, Москву на Архангельск, Архангельск
> на Ярославль. А на что вы готовы поменять Ярославль?

и где же тут закономерность? в самих названиях?

← →
Брюнетка © (2007-01-26 11:44) [28]

>начинающий ©

Купюры разного достоинства с изображением городов.

← →
начинающий © (2007-01-26 11:48) [29]

а я, наивный, будучи в Украине пытался её осилить... :)

← →
Думкин © (2007-01-26 11:49) [30]

Хабаровск на Кудрина.

← →
MBo © (2007-01-26 12:40) [31]

>TUser © (26.01.07 10:48) [25]
>9. А жульничать мудрецы могут? Типа один подмигивает двум другим, значит на них одинаковые шапки

Нет, только посмотреть и поразмыслить.

← →
Elen © (2007-01-26 12:57) [32]

> мышь перебегает в одну из соседних норок.

в любую свободную или в следующую по одному направлению? т.е. из 2-й в 3-ю, потом в 4-ю - или может возвращаться в предидущую?

← →
Vlad Oshin © (2007-01-26 12:57) [33]

по поводу 1., кот сует руку в нору и высовывает? т.е. мышь может перебежать в эту же нору при своем ходе?

> Могут ли мудрецы гарантированно сохранить свои головы и
> содержание?

а только содержание? :)

← →
MBo © (2007-01-26 13:02) [34]

кот вынимает лапу, после этого мыш непременно перебегает в соседнюю норку

← →
Elen © (2007-01-26 13:11) [35]

> перебегает в соседнюю норку

в любом направлении?

← →
MBo © (2007-01-26 13:23) [36]

>в любом направлении?
Да, кроме крайних норок, конечно.

← →
Vlad Oshin © (2007-01-26 13:23) [37]

1. - 8?

← →
b z (2007-01-26 13:24) [38]

1 - 10?

← →
SergP © (2007-01-26 13:24) [39]

> 1. Кот ловит мышку, которая прячется в одной из пяти норок.
> Норки соединены между собой таким образом 0-0-0-0-0
> Процесс ловли происходит следующим образом:
> Кот сует лапу в одну из норок. Если мышь там - она поймана.
> Если же нет - мышь перебегает в одну из соседних норок.
>
> За какое минимальное количество ходов кот гарантированно
> ловит мышь?

Пока нашел вариант с 6 ходами

← →
Vlad Oshin © (2007-01-26 13:27) [40]

> SergP © (26.01.07 13:24) [39]

это как?

> b z (26.01.07 13:24) [38]

9 уже очевидное решение
1-1-2-2-3-3-4-4-5

← →
SergP © (2007-01-26 13:30) [41]

> [39] SergP © (26.01.07 13:24)
> Пока нашел вариант с 6 ходами

О - норка где мышь может быть
Х - норка где мышь быть не может
Ш - лапа кота

Первоначальное состояние: О-О-О-О-О
1 ход: О-Ш-О-О-О
после вытягивания лапы: Х-О-О-О-О

2.
Х-О-Ш-О-О
О-Х-О-О-О
3.
О-Х-О-Ш-О
Х-О-Х-О-Х
4.
Х-О-Х-Ш-Х
О-Х-О-Х-Х
5.
О-Х-Ш-Х-Х
Х-О-Х-Х-Х
6.
Х-Ш-Х-Х-Х

← →
MBo © (2007-01-26 13:33) [42]

>SergP © (26.01.07 13:30) [41]
Да, верно. Четность норки с мышью каждый ход меняется, и крайние можно не проверять.

← →
SergP © (2007-01-26 13:34) [43]

> [40] Vlad Oshin © (26.01.07 13:27)
>
> 9 уже очевидное решение
> 1-1-2-2-3-3-4-4-5

Неа. так не поймаешь...
Пока 1-1-2-2-3 мышь перебегает из 4 в 5 и обратно
после второго раза 3 перебегает в 3, а далее в 2 и 1

← →
Elen © (2007-01-26 13:40) [44]

> SergP

А чего это после ходов норки исключаются, у кота вроде только две лапы, а по условию - вообще одна?

← →
Думкин © (2007-01-26 13:45) [45]

> Elen © (26.01.07 13:40) [44]

Из условия, что мышь не стоит на месте, если не поймана.

← →
Elen © (2007-01-26 13:45) [46]

> MBo

Если кот не поймал мышку она не может пропустить свой ход и остаться в той же норке?

← →
Elen © (2007-01-26 13:46) [47]

> Думкин

О ясно

← →
MBo © (2007-01-26 13:46) [48]

>она не может пропустить свой ход
нет. Мир жесток ;(

← →
Elen © (2007-01-26 13:47) [49]

> Думкин

Получается за 4 хода если кот начнет с краев приближаться к середине.

← →
Elen © (2007-01-26 13:47) [50]

> MBo

Или кот не начнет с краев?

← →
Vlad Oshin © (2007-01-26 13:48) [51]

1-1-2-2... - да, логично, попутал.

← →
Elen © (2007-01-26 13:48) [52]

> MBo

Ану спроси кота - я права?

← →
SergP © (2007-01-26 13:50) [53]

> [44] Elen © (26.01.07 13:40)
>
> > SergP
>
> А чего это после ходов норки исключаются, у кота вроде только
> две лапы, а по условию - вообще одна?

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

← →
Elen © (2007-01-26 13:50) [54]

> MBo

Его ходы : 1-5-2-4

← →
Elen © (2007-01-26 13:52) [55]

> SergP

По твоему решению коту проще сделать 5 ходов а не 6 : 1-2-3-4-5. Тогда точно обед будет ;)

← →
Vlad Oshin © (2007-01-26 13:55) [56]

ну да, кот сует лапу в первую норку с динамитом, а высовывает без динамита. Повторить с каждой норкой.

← →
SergP © (2007-01-26 13:56) [57]

> [55] Elen © (26.01.07 13:52)
>
> > SergP
>
> По твоему решению коту проще сделать 5 ходов а не 6 : 1-
> 2-3-4-5. Тогда точно обед будет ;)

это ничего не даст..
Ш-О-О-М-О
О-О-М-О-О

О-Ш-М-О-О
О-М-О-О-О

О-М-Ш-О-О
М-О-О-О-О

М-О-О-Ш-О
О-М-О-О-О

О-М-О-О-Ш и кот подохнет с голоду...

← →
Agent13 © (2007-01-26 13:56) [58]

В 9-й задаче: я так понимаю, что раз они пишут ответ, а не говорят вслух, значит никто не может узнать, кто как ответил?

← →
MBo © (2007-01-26 13:58) [59]

>Его ходы : 1-5-2-4
после третьего хода мышь может быть в 2 и 4

← →
SergP © (2007-01-26 13:59) [60]

> [56] Vlad Oshin © (26.01.07 13:55)
> ну да, кот сует лапу в первую норку с динамитом, а высовывает
> без динамита. Повторить с каждой норкой.

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

← →
MBo © (2007-01-26 13:59) [61]

>Agent13 значит никто не может узнать, кто как ответил?
Да

← →
SergP © (2007-01-26 14:01) [62]

← →
Elen © (2007-01-26 14:01) [63]

> после третьего хода мышь может быть в 2 и 4

Но именно после третьего хода когда кот будет в 2 или в 4 и следующих ход мышки будет в лапы ему.

← →
MBo © (2007-01-26 14:11) [64]

>А зачем аж по 200 штук?
А фиг его знает

>Но именно после третьего хода когда кот будет в 2 или в 4 и следующих ход мышки будет в лапы ему.

нет. После 1-5-2 мышка в 2 или 4, ты проверяешь 4, после чего мышка в 1,3 и лучше не стало

← →
Elen © (2007-01-26 14:20) [65]

> MBo

Тогда за 5 - гарантированно.

← →
Elen © (2007-01-26 14:23) [66]

> После 1-5-2 мышка в 2

Чего это в 2? Ей в 2 путь закрыт - там же лапа кота?

← →
MBo © (2007-01-26 14:32) [67]

>Ей в 2 путь закрыт - там же лапа кота?
см. [34]

← →
Elen © (2007-01-26 14:48) [68]

> MBo

Попробую описать :
1 ход : Кот опускает лапу в №1. Мышка перебегает в 2,3,4,5
2 ход : кот опускает лапу в №5. если мышь находилась во второй то ей два пути : в №1 или №3, но если она пойдет в №1 то при следующем ходе кота в №2 ей придется попасть к нему в лапы, т.к. она в краю. Предположим она пошла в №3.
3 ход : Кот опускает лапу в №2. Мышка может перейти только в №4, где и будет схвачена, если кот опустит 4-м ходом лапу в №4.

Итак 1-5-2-4
Иначе

Если мышка находится в №4 :
1 ход : Кот в №1, мышь пойдет в №3. Если пойдет в №5 то после следующего хода кота в №5 попадется.
2 ход : Кот в №5. Если мышь пойдет в №2 то на следующем ходе (кот в №2) попадется, значит пойдет в №4
3 ход : кот в №2. Если мышь пойдет в №5 то при следующем ходе кота (в №4)попадется, предположем пошла в №3
4 Ход : Кот пойдет в №4 и мышке придется пойти в №2, где она благополучно поймается котом пятым ходом.

Итак 5 ходов. 1-5-2-4-2

Вот.

← →
Elen © (2007-01-26 14:50) [69]

> MBo

...Если кот ходит первым ;)

← →
MBo © (2007-01-26 14:51) [70]

1 ход : Кот опускает лапу в №1. Мышка перебегает в 2,3,4,5

не так. Если мыши не было в 1, то она была в 2,3,4,5 и после перебегания может быть снова в любой из 1,2,3,4,5

← →
Elen © (2007-01-26 15:08) [71]

> MBo

А-а да! Мышка может после того как кот высунул лапу прыгнуть куда угодно.

← →
default © (2007-01-26 15:32) [72]

2. уже что-то было похожее
число кружков во всех цифрах
стало быть 689 -> 4

← →
SergP © (2007-01-26 16:09) [73]

> [71] Elen © (26.01.07 15:08)
>
> > MBo
>
> А-а да! Мышка может после того как кот высунул лапу прыгнуть
> куда угодно.

Не куда угодно, а в соседнюю дырку, в т.ч. и в ту где была лапа кота

← →
Elen © (2007-01-26 16:18) [74]

> SergP

Вот вот. И придется коту несколько раз бить одну и ту же дырку, вот только сколько раз? Ну похоже все таки за 9 ходов достанет, хотя....

← →
novill © (2007-01-26 16:51) [75]

> [0] MBo © (26.01.07 08:15)

Ты когда ответы будешь постить?

А то задачи повторяются, а ответов всё нет.

6 и 7 ты постил (22.12.06 14:08)

← →
ferr © (2007-01-26 17:24) [76]

> Ты когда ответы будешь постить?
>
> А то задачи повторяются, а ответов всё нет.
>
> 6 и 7 ты постил (22.12.06 14:08)

хм, 6 -- класическая задача Иосифа...
var arr : array of integer; i, n, m : integer; begin Readln(n, m); SetLength(arr, n + 1); arr[1] := 1; for i := 2 to n do arr[i] := (arr[i - 1] + m - 1) mod i + 1; writeln(arr[n]); end.

а 7-ое разве можно посчитать быстрее динамического программирования(таблички)?

← →
ferr © (2007-01-26 17:25) [77]

Массив в 6-ом конечно же не обязателен, просто так нагляднее как эти числа получаются ;-)

← →
default © (2007-01-26 18:11) [78]

4. вроде 4 4/9 часа

← →
oldman (2007-01-26 18:36) [79]

> Пятничные задачки. Вася Пупкин пока отдыхает

вася пупкин фарева!!!
хачу вася пупкин!!!
:)

← →
SergP © (2007-01-26 20:31) [80]

думал долго над 5б
пока ничего не придумал.
Хотелось бы знать мысли остальных по поводу него...

← →
default © (2007-01-26 20:33) [81]

SergP © (26.01.07 20:31) [80]
хочешь я решу?

← →
J_f_S (2007-01-26 20:39) [82]

> 9. Падишах решил проверить, стоит ли ему кормить своих 100
> мудрецов,
> или пришло время заменить. Он заказал шапки с помпончиками
> ста цветов,
> по 200 каждого цвета, собрал мудрецов и сказал:
> "У вас 3 часа на раздумье и договор. Вот вам каждому бумага,
> карандаш.
> Завтра каждому наденут на голову шапку.
> Какого цвета будет помпончик, вы знать каждый про себя не
> будете.
> И покажут каждому всех других. И каждый должен написать,
>
> какого цвета помпончик на нём. Если хоть один напишет правильно,
>
> будете жить и продолжать служить. Нет - всем отрубят головы".
>
> Могут ли мудрецы гарантированно сохранить свои головы и
> содержание?

1. Первый смотрит на кого-либо, и пишет цвет его.
2. Остальные тиражируют ответ первого
3. Сто пудофф - у одного совпадет.

← →
SergP © (2007-01-26 21:24) [83]

> 9. Падишах решил проверить, стоит ли ему кормить своих 100
> мудрецов,
> или пришло время заменить. Он заказал шапки с помпончиками
> ста цветов,
> по 200 каждого цвета, собрал мудрецов и сказал:
> "У вас 3 часа на раздумье и договор. Вот вам каждому бумага,
> карандаш.
> Завтра каждому наденут на голову шапку.
> Какого цвета будет помпончик, вы знать каждый про себя не
> будете.
> И покажут каждому всех других. И каждый должен написать,
>
> какого цвета помпончик на нём. Если хоть один напишет правильно,
>
> будете жить и продолжать служить. Нет - всем отрубят головы".
> Могут ли мудрецы гарантированно сохранить свои головы и
> содержание?

Не вижу возможности мудрецам гарантированно остаться живыми.
исключение составляет случай когда они могут обмениваться информацией друг с другом...
Например обмен информацией представляю себе так:
2 мудреца пишут ответ на бумаге. Но очередностью написания они передают 1 бит информации остальным.
В таком случае все без проблем могут гарантированно остаться живыми..

← →
default © (2007-01-26 22:37) [84]

5б
думал полтора часа
ничего не придумал
засомневался что решение есть

← →
Kedge © (2007-01-26 23:17) [85]

> 9. Падишах решил проверить, стоит ли ему кормить своих 100
> мудрецов,
> или пришло время заменить. Он заказал шапки с помпончиками
> ста цветов,
> по 200 каждого цвета, собрал мудрецов и сказал:
> "У вас 3 часа на раздумье и договор. Вот вам каждому бумага,
> карандаш.
> Завтра каждому наденут на голову шапку.
> Какого цвета будет помпончик, вы знать каждый про себя не
> будете.
> И покажут каждому всех других. И каждый должен написать,
>
> какого цвета помпончик на нём. Если хоть один напишет правильно,
>
> будете жить и продолжать служить. Нет - всем отрубят головы".
> Могут ли мудрецы гарантированно сохранить свои головы и
> содержание?

Пишем себе цвет, встречающийся более одного раза.
Если такого нет, то - недостающий.

← →
Kedge © (2007-01-26 23:21) [86]

Поторопился.
встречающийся максимальное число раз.
Если все по одному разу встречаются, то недостающий

← →
Alx2 © (2007-01-27 02:13) [87]

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

Вторая идея - разбиваем массив на две части. В левую переносим все элементы строго меньшие некоторого M. В правую - остальные. Смотрим xor-суммы обеих частей. Если обе суммы не ноль, то их значения есть значения непарных элементов. Если одна из сумм ноль - то рекурсивно повторяем описанное для той части, где сумма не ноль. Несмотря на рекурсию, время работы такого алгоритма линейно (если выбирать M так, чтобы массив делился примерно поровну), так как имеем дело со сходящейся геометрической прогрессией длин массива.

Для второй идеи ниже идет реализация "навскидку".
type TIntegerArray = array of integer; function Find(Start, Stop: Integer; var data: TIntegerArray): TPoint; var Median, k, l, tmp: Integer; Lxor, Rxor: Integer; begin tmp := Data[Start]; Median := Data[Start]; for k := Start+1 to Stop do begin if Median<Data[k] then Median := Data[k]; if tmp>Data[k] then tmp := Data[k]; end; Median := 1+(Median + tmp) div 2; // Можно брать Median случайно из массива, // но главное - не наступить на минимум. // К тому же полный проход не увеличивает здесь сложность k:=Start; l := Stop; Lxor := 0; Rxor := 0; repeat while (k < l) and (Data[k] < Median) do begin Lxor := Lxor xor Data[k]; inc(k); end; while (k < l) and (Data[l] >= Median) do begin Rxor := Rxor xor Data[l]; dec(l); end; if k < l then begin tmp := Data[k]; Data[k] := Data[l]; Lxor := Lxor xor Data[k]; Data[l] := tmp; Rxor := Rxor xor Data[l]; inc(k); dec(l); end; until k >= l; if Data[k]>=Median then dec(k) else LXor := LXor xor Data[k]; if Data[l]<Median then inc(l) else RXor := RXor xor Data[l]; if LXor = 0 then Result := Find(k+1, Stop, data) else if RXor = 0 then Result := Find(Start, k, data) else Result := Point(LXor, RXor); end;

Вызов:
Var Res : TPoint;
begin
Res := Find(0,Length(Data)-1, Data);
end;

← →
Alx2 © (2007-01-27 02:51) [88]

7.
Можно всопользоваться тождеством

s(m,n) = sum((-1)^(n-k)*k^m/(k!*(n-k)!), k = 0 .. n)

:)

← →
SergP © (2007-01-27 11:07) [89]

9. ИМХО у мудрецов нет гарантии остаться живыми.
Исключение составляет случай когда они могут обмениваться информацией.
Но о возможных способах такого обмена ничего не сказано.
Вобщем мудрецы пишут что-то на бумажке, а вот каким образом они сдают свои бумажки? Кто-то по очереди их у них забирает? Или они сами могут сделать так: написал и сдал написанное кому нужно? если да, то тогда не проблема.

вобщем ждем МВО для уточнения условия

Мудрецы не могут обмениваться информацией. Сам я эту задачу не решил, но решение имеется, и достаточно короткое.

> [91] MBo © (27.01.07 11:35)
> Мудрецы не могут обмениваться информацией. Сам я эту задачу
> не решил, но решение имеется, и достаточно короткое.

Если 100 цветов и по 200 штук каждого - это всего 20000 помпончиков.
сам факт того что помпончиков одного цвета больше чем самих мудрецов, говорит о том что не может существовать никакой зависимости цвета помпончика на конкретном мудреце от помпончиков на других мудрецах.
Поэтому при отсутствии возможности обмена информацией никакой гарантии того что хотя бы один угадает свой цвет не може быть.
Хотелось бы видеть решение.

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

[87] линейное время и константная память есть?
MBo, [87] верно?

>default
а [78] верно?

Нет

[87] верно?
Ну так можно, время кажется линейным, но с большой константой
Есть весьма простой способ, доступный каждому, кто может 5a решить.
Нужно ли давать наводку?

MBo © (27.01.07 13:46) [96]
пока, наверно, не стоит
а в 4 я решал при предположении что копать могу они с разнйо скоростью получилось что данных мало для решения и я взял что они копают одновременно и такое получилось

> что они копают одновременно

одинаково быстро

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

> делит по модулю НА общее

+ [99]
да, эвристика оказалась верной
идея очень великолепна в своей изящности

представим себе набор мудрецов
пусть первый мудрец имеет цвет X
тогда, исходя из алгоритма [99], очевидно, что найдётся такой номер мудреца, что если бы он имел шапку цвета X(цвета первого мудреца), то он вынужден был бы по алгоритму написать цвет той шапки которая находится на нём(в частном случае это может быть сам первый мудрец)
положим, что на мудреце с данной номером надета шапка цвета Y
номер цвета Y находится либо правее либо левее номера цвета X на каком-то расстоянии S, но это означает, что данный мудрец будет вынужден по алгоритму написать цвет с номером находящимся на расстоянии S влево или вправо от номера цвета X, а это будет номер цвета Y!, то есть этот мудрец напишет свой цвет!

это всё

[101] лучше не читать ибо бред
вообщем алгоритм вроде такой, а как доказать надо думать

> [96] MBo © (27.01.07 13:46)
> >default
> а [78] верно?
>
> Нет
>
> [87] верно?
> Ну так можно, время кажется линейным, но с большой константой
> Есть весьма простой способ, доступный каждому, кто может
> 5a решить.
> Нужно ли давать наводку?

неа. Что касается 5б - то на водку не нужно... самим интерестно...
а вот наводка к 9 (про падишахов и мудрецов) не помешала бы

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

> [102] default © (28.01.07 00:45)
> [101] лучше не читать ибо бред
> вообщем алгоритм вроде такой, а как доказать надо думать

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

>Второй мудрец ищет первого мудреца с номером больше,
>чем у него и цветом колпака не совпадающим с
>цветом колпака первого
Читать надо так:
Второй мудрец ищет первого мудреца с наименьшим номером больше,
чем у него и цветом колпака не совпадающим с
цветом колпака первого

ИМХО ответ будет таков:

> 9.
...
> Могут ли мудрецы гарантированно сохранить свои головы и
> содержание?

Не могут.

Про семерки случайно попалось решение. Вот тут, стр. 13 и далее. Правда 10 метров почти.
http://monkey.belozersky.msu.ru/~evgeniy/boltyansky_lects.djvu

5б. Отсортировать цифровой сортировкой, потом пройти по всему массиву. Или есть что-то более элегантное?

> [110] TUser © (29.01.07 23:24)
> 5б. Отсортировать цифровой сортировкой, потом пройти по
> всему массиву. Или есть что-то более элегантное?

была такая мысль
1. проХОRить все элементы.
a = M[1] xor m[2] xor m[3] .... в цикле конечно...
2. проXORить квадраты всех элементов
b = sqr(M[1]) xor sqr(m[2]) xor sqr(m[3]) .... в том же цикле...

Получим систему уравнений
a = x1 xor x2
b = sqr(x1) xor sqr(x2)

где x1 и x2 искомые элементы.

толко вот как решить такую "квадратно-арифметико-логическую" систему пока не придумал...

> a = x1 xor x2
> b = sqr(x1) xor sqr(x2)

a xor x2 = (x1 xor x2) xor x2 --> a xor x2= x1
b = sqr(a xor x2) xor sqr(x2)
a и b - известные числа
теперь пробегаемся по каждому числу и делаем проверку
b = sqr(a xor Number) xor sqr(Number)
если успешно(нашли x2), то находим по первому уравнению x1
только вот у меня уверенности нет что эта система уравнений определяет единственную пару корней

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

Про мудрецов вот что есть:

Занумеруем все цвета 0...N-1.
И всех мудрецов тоже.
Пусть надели набор помпонов {Xi}.
Тогде пусть они отвечают {Yi}
Yi = (i - SUMj!=i Xj) mod N

Величины Zi= (Yi-Xi) mod N очевидно принимают разные значения для разных i, но всего возможных значений N, значит ровно для одного мудреца Zi=0, то есть его ответ совпал с цветом его помпона.

P.S. подчеркнул про разные значения, поскольку мне не вполне очевидно

Наводка к 5б нужна или пока еще нет?

лично мне наводки не надо:) если буду думать, то без ней:)
а насчёт [114] - алгоримт очень похож на мой
мой дал осечку, думаю и этот должен где-то ложануться
а насчёт очевидно мне тоже нифига не очевидно

а какое там деление по модулю?
в языках программирования оно может принимать и отрицательные значения , а тут видимо только положительные
то есть -3 mod 3 = 1*(-3)+0, то есть в остатке может быть 0 и когда Xi<>Yi

а какое там деление по модулю?
в языках программирования оно может принимать и отрицательные значения , а тут видимо только неотрицательные
то есть -3 mod 3 = 3*(-1)+0, то есть в остатке может быть 0 и когда Xi<>Yi

> видимо только неотрицательные
Да

даааа объяснение никуда не годится...
могу такую наводку дать может кому поможет
пусть 100 мудрецов есть
возьмём какого-либо мудреца
число возможных комбинация цветов шапок на других мудрецах (100)^99=
10^198, на каждую такую комбинацию мудрец должен написать некий номер цвета(цвет) и только один цвет(то есть если никто из других мудрецов не угадал свой цвет, а этому мудрецу выпала шапка с цветом который он не пишет на данную комбинацию шапок вокруг него то пипец всем), понятно что каждый мудрец может максимум отсечь 10^198 комбинаций
и так рассматриваем каждого мудреца, то есть максимум(в случае непересечение отсекаемых комбинаций мудрецами) все они могут покрыть 100*(10^198)=10^200
всего же комбинаций цветов 100^100=10^200
то есть мы понимаем что в каждой комбинации цветов мы в лучшем случае будем иметь одно совпадение(при условии что задача решаема)
вот и надо пробовать придумать алгоритм чтобы каждый мудрец отсекал свою непересекающуюся с другими часть комбинаций цветов (10^198 комбинаций)

то есть по каждому алгоритму каждый мудрец будет отсекать 10^198 вариантов
а в правильном алгоритме эти отсекаемые варианты не должны пересекаться у разных мудрецов
отсутствие пересечения сводится к доказательству отсутствия случая когда имеется больше одного угадывания
про это и идёт речь в строках "Величины Zi= (Yi-Xi) mod N очевидно принимают разные значения для разных i,"
но это совсем там не доказано
и это условие следует пытаться доказывать для любого алгоритма поверяемого на правильность

Кстати, про кота и мышку:

Если знать, что мышка находится в четной норке, то ходы 2-3-4 ловят ее на раз.
Осталось узнать, когда мышка в четной норке...

На 1-й вопрос ответ 5.

Господа читайте внимательнее условие:

Процесс ловли происходит следующим образом:
Кот сует лапу в одну из норок.
1. Если мышь там - она поймана. (лапа в норке)
2. Если же нет - мышь перебегает в одну из соседних норок. (лапа в норке)

Таким образом, если начинать с первой норки:
М->2
Ш-М-О-О-О (ШАГ 1)
М->3
О-Ш-М-О-О (ШАГ 2)
М->4
О-О-Ш-М-О (ШАГ 3)
М->5
О-О-О-Ш-М (ШАГ 4)
дальше мышке деться некуда и опустив лапу в 5 кот ее накроет!

> MacroDenS © (30.01.07 17:53) [123]

Господин, читай внимательно условие...

1. Если мышь там - она поймана. (лапа в норке)
2. Если же нет - мышь перебегает в одну из соседних норок. (лапа в норке)

А вот "лапа в норке" ты где вычитал???

> [122] oldman © (30.01.07 17:52)
> Кстати, про кота и мышку:
>
> Если знать, что мышка находится в четной норке, то ходы
> 2-3-4 ловят ее на раз.
> Осталось узнать, когда мышка в четной норке...

а если в нечетной, то повторяем еще раз 2-3-4 и она ловится

> [126] MacroDenS © (31.01.07 14:18)
> to oldman © (30.01.07 18:01) [124]
>
> а ты еще по внимательнее почитай!!!

Там не написано "лапа в норке", но условие поставлено не совсем четко. Хотя насчет того что мышь перебегает уже после вытягивания лапы можно догадаться, ибо иначе возможны "патовые" ситуации.

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