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

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

← →
SergP © (2007-01-27 11:08) [90]

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

← →
MBo © (2007-01-27 11:35) [91]

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

← →
SergP © (2007-01-27 12:29) [92]

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

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

← →
MBo © (2007-01-27 12:57) [93]

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

← →
default © (2007-01-27 13:00) [94]

MBo © (27.01.07 12:57) [93]
Борис, а [78] верно?

← →
default © (2007-01-27 13:10) [95]

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

← →
MBo © (2007-01-27 13:46) [96]

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

Нет

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

← →
default © (2007-01-27 13:57) [97]

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

← →
default © (2007-01-27 13:58) [98]

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

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

← →
default © (2007-01-27 19:54) [99]

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

← →
default © (2007-01-27 19:57) [100]

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

← →
default © (2007-01-27 23:54) [101]

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

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

это всё

← →
default © (2007-01-28 00:45) [102]

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

← →
SergP © (2007-01-28 04:00) [103]

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

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

← →
Riply © (2007-01-28 05:19) [104]

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

← →
SergP © (2007-01-28 05:20) [105]

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

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

← →
Riply © (2007-01-28 05:30) [106]

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

← →
SergP © (2007-01-28 05:48) [107]

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

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

Не могут.

← →
MBo © (2007-01-28 07:18) [108]

>default © (27.01.07 19:54) [99]
Похоже - то, что надо!

Про семерки случайно попалось решение. Вот тут, стр. 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 комбинаций)

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