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

← →
default © (2007-01-30 14:34) [120]

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

← →
default © (2007-01-30 15:05) [121]

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

← →
oldman © (2007-01-30 17:52) [122]

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

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

← →
MacroDenS © (2007-01-30 17:53) [123]

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

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

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

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

← →
oldman © (2007-01-30 18:01) [124]

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

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

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

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

← →
SergP © (2007-01-31 11:24) [125]

> [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]
>
> а ты еще по внимательнее почитай!!!

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

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