[Август]

Хоть и боян, но интересный Если кто-то уже знает ответ - не спешите хвастаццо, дайте другим подумать Также желательно решать головой, а не Гуглом или Яндехом
В тюрьму прибыли 17 преступничгов. Начальник тюрьмы сказал им, что завтра их посадят в изолированные камеры, они не смогут общаться друг с другом. Время от времени стражник будет кого-то из них отводить в специальную комнату. В этой комнате есть два выключателя, на одном написано "А", на другом - "В". Каждый из выключателей имеет два положения - вкл и выкл. Урик должен будет изменить положение только одного выключателя. Стражник может выбирать преступничгов в стихийном порядке, но наступит такой момент, когда каждый уголовничег побывает в комнате, может и не один раз.

Если ко мне подойдет один из преступничгов и скажет, что все мы, все 17 человек, уже побывали в комнате, я тотчас отпущу всех, в случае, если это правда. Если же нет, то всех вас немедленно кознят. Никто кроме вас не будет посещать комнату с выключателями. В каком положении выключатели находятся сейчас, я не помню. Итак, у вас есть сегодняшний день для обдумывания вашего положения. Завтра вас уже разведут по камерам. С этими словами начальнег ушел.
Предложите стратегию позволяющую уголовничгам НАВЕРНЯКА выиграть, считая, что они будут жить достаточно долго, чтобы побывать в этой комнате как угодно много раз каждый.

ибо так и не ответили ...

[Ferox]

обязательно менять положение выключателя?

[Ferox]

В общем надо или знать начальное положение выключателей или иметь право не щелкать выключателем.

[Август]

Да, менять положение выключателя - надо ...
Знать положение до входа первого в комнату и не обязательно ...

[Ferox]

Тогда хотя бы тот, кто войдет первым должен знать что он первый.

[Август]

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

[Ferox]

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

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

[Dimoks]

КРАК незримо с нами... :(

что я или совсем отупел... я даже не понял задание :(
ну предположем пусть клацают только один левый выключатель. через 50 дней скажут что уже 17 человек побывали там. никогда и никак надзиратель не вычилист говорят они правду или нет (могу поспорить) т.к. там всего 4 положения:
A:On, B:On
A:On, B:Off
A:Off, B:On
A:Off, B:Off
плюс надзиратель незнает начального положения.

Пусть начальное значение A:On, B:On (надзиратель его незнает)
1 A:On, B:On - первый пришел увидел и переключил.
2 A:Off, B:On - второй пришел
3 A:On, B:On - третий
.......
48 A:Off, B:On - может опять первый пришел (неважно)
49 A:On, B:On - может опять пришел второй (неважно)
50 A:Off, B:On

И говорят что все там были. А несколько человек из 17 никогда там не были. Ну и........... ? :D
Ну и как надзиратель догадается если он даже начального значения не знал?

[Август]

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

Ну он и так всегда знает что он первый, т.е. первый раз в комнате, а следовательно дальше можно строить теории ...
Опиши алгоритм ...

КРАК незримо с нами...

что я или совсем отупел... я даже не понял задание
ну предположем пусть клацают только один левый выключатель. через 50 дней скажут что уже 17 человек побывали там. никогда и никак надзиратель не вычилист говорят они правду или нет (могу поспорить) т.к. там всего 4 положения:
A:On, B:On
A:On, B:Off
A:Off, B:On
A:Off, B:Off
плюс надзиратель незнает начального положения.

Пусть начальное значение A:On, B:On (надзиратель его незнает)
1 A:On, B:On - первый пришел увидел и переключил.
2 A:Off, B:On - второй пришел
3 A:On, B:On - третий
.......
48 A:Off, B:On - может опять первый пришел (неважно)
49 A:On, B:On - может опять пришел второй (неважно)
50 A:Off, B:On

И говорят что все там были. А несколько человек из 17 никогда там не были. Ну и........... ?
Ну и как надзиратель догадается если он даже начального значения не знал?

Надзератель знает кого он пускал/не пускал в комнату, иначе зачем он нужен?, он по сути генератор случайных чисел, но это не имеет отношение к вопросу, так комментарий, бандитам дают ночь чтобы они решили кто будет тот о котором говорит Ферокс, тут смысл не столько в выключателях сколько в логичке подсчета ...

[Ferox]

Ну он и так всегда знает что он первый, т.е. первый раз в комнате, а следовательно дальше можно строить теории ...
Опиши алгоритм ...

Нет. Мне нужно чтобы он знал, что он вообще первый, а не первый раз лично он в комнате.

Алгоритм очень простой - первый кого заводят в комнату - назначается счетчиком - он переводит выключатель А в положение "вверх" (а если он уже там, то просто клацает вторым выключателем).

Каждый заключенный кроме счетчика приходя в камеру первый раз, если выключатель А в положении "вверх" - клацает его "вниз", в противном случае клацает Б.

Приходя в комнату второй и последующие разы в любом случае клацает "Б".

Счетчик приходя в камеру, если А - "вниз" - клацает его, в противном случае - Б.

Счетчик считает число раз, которые ему пришлось клацнуть выключатель А. Когда клацнет 16 раз не считая первого - все заключенные побывали в камере.

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

[voller]

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

[Dimoks]

Надзератель знает кого он пускал/не пускал в комнату, иначе зачем он нужен?, он :confused: :confused: :confused: :confused: :confused:
так если надзиратель такой с идеальной памятью и помнит кого пускал, а кого нет - то его обмануть нальзя.

я по прежнему тупо не понимаю задачу. :)

[Dimoks]

Нет. Мне нужно чтобы он знал, что он вообще первый, а не первый раз лично он в комнате.

Алгоритм очень простой - первый кого заводят в комнату - назначается счетчиком - он переводит выключатель А в положение "вверх" (а если он уже там, то просто клацает вторым выключателем).

Каждый заключенный кроме счетчика приходя в камеру первый раз, если выключатель А в положении "вверх" - клацает его "вниз", в противном случае клацает Б.

Приходя в комнату второй и последующие разы в любом случае клацает "Б".

Счетчик приходя в камеру, если А - "вниз" - клацает его, в противном случае - Б.

Счетчик считает число раз, которые ему пришлось клацнуть выключатель А. Когда клацнет 16 раз не считая первого - все заключенные побывали в камере.

бред какойто... :)
Так тут вот Ferox пишет что у начальника память кто был там а кто нет.


Счетчик считает число раз, которые ему пришлось клацнуть выключатель А. Когда клацнет 16 раз не считая первого - все заключенные побывали в камере.Даже если "человек-счётчик" наклацает сам на первым выключателе 100000000 раз это не говорит о том что в комнате побывали все ;)

[Октябренок]

Комбинация идиотская,жутко длительная,но гарантированная...
"Счетчик",заходя в камеру переводит 1-й выключатель в положение скажем "выкл."
Каждый последующий,если он впервые в комнате переводит 1-й выключатель в положение "вкл."-"я здесь был..."
Делает он это только при соблюдении 2-х условий:1.Он здесь впервые. 2.1-й выключатель в положении "выкл." Во всех иных случаях переключает 2-й!!!
Задача "счетчика": каждый свой приход в камеру переключать 1-й выключатель в положение "выкл."(если он включен,в противном случае дергать 2-й.) И считать сколько на его веку встретиться положений "вкл."
Будет 16 положений "вкл."- докладывать начальству...
Не зря там уточнение: "они будут жить достаточно долго, чтобы побывать в этой комнате как угодно много раз каждый."
Думаю лет эдак в 150 поместятся...

[Октябренок]

:-) Сорри,повторил то-же что и Ferox. :пиво:

[borisd]

Чтобы обойти неопределенность в начальном положении выключателей, все заключенные вместо одного должны клацнуть по 2 раза, тогда знаком того, что все заключенные побывали в камере, хотя бы один раз, будет 2*(n-1) изменений выключателя А, насчитанных счетчиком.

[Ferox]

О! borisd голова!!!

[ANTIpоd]

а в чём прикол? при чём тут выключатели? от их полождения состояние уголовников не изменяется, только от того побывали все 17 в камере или нет.
при чём тут выключатели?

[Октябренок]

Чтобы обойти неопределенность в начальном положении выключателей, все заключенные вместо одного должны клацнуть по 2 раза, тогда знаком того, что все заключенные побывали в камере, хотя бы один раз, будет 2*(n-1) изменений выключателя А, насчитанных счетчиком.

Них... не понял:confused: Какая неопределенность?:confused:

Итак, у вас есть сегодняшний день для обдумывания вашего положения.
Преступники договариваются,кто завтра пойдет,тот и счечик.
На следующий день,зайдя в комнату он: если первый выключатель в положении "вкл." переводит его в "выкл."; если первый выключатель в положении "выкл.", дергает 2-й... и ВСЕ... начинает отсчет... 16 положений "вкл.":класс:

[borisd]

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



Преступники договариваются,кто завтра пойдет,тот и счечик.

Преступники не знают кто завтра пойдет и пойдет ли вообще.


На следующий день,зайдя в комнату он: если первый выключатель в положении "вкл." переводит его в "выкл."; если первый выключатель в положении "выкл.", дергает 2-й... и ВСЕ... начинает отсчет... 16 положений "вкл."

Не зная кто счетчик, каждый может считать себя первым и сбрасывать выключатель А.

[Октябренок]

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

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

:-) :-) :-) Бля!!! Крек, ты где??? Прийди и рассуди!!!:-) :-) :-)

[Dimoks]

Преступники не знают кто завтра пойдет и пойдет ли вообще.я по прежнему ничего не понял :) можно на пальцах?
только исходя из того что заключенные сидят по камерам и не общаются между собой. и незнают кто из них пошел первым. т.е. они незнают кто из них "счётчик". получается человек думает что он "счётчик" клацает что-то... приходит второй думает что он "счётчик" опять клацает.

[Октябренок]

Димокс,прочитай постом выше.:пиво:
Заключенные, по условию задачи ИМЕЮТ ПОСЛЕДНИЙ ВЕЧЕР НА ОБДУМЫВАНИЕ,СОВЕЩАНИЕ!
Они решают,сегодня,пока вместе,кто "счетчик"...
А уж когда счетчик зайдет в комнату это неважно. Как зайдет,так и начнет свой отсчет:yahoo: :yahoo: :yahoo:

[Ferox]

я по прежнему ничего не понял :) можно на пальцах?
только исходя из того что заключенные сидят по камерам и не общаются между собой. и незнают кто из них пошел первым. т.е. они незнают кто из них "счётчик". получается человек думает что он "счётчик" клацает что-то... приходит второй думает что он "счётчик" опять клацает.

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

[talex]

Что тут не понятного в этой задаче :)

По условию, есть один вечер на обсуждение, т.е. выбирается счетчик (конкретный человек и все это знают) от него все зависит + начальное условие, что, например, выключатель "А" в положении "вкл" - начало отсчета и это положение никто не трогает дважды! (т.е. если один раз нажал в других заходах, то все...)а вторым клацайте (неважно когда это произойдет). Даже если изначально оно таковое, то при первом попадании счетчик его отбрасывает и ставит "выкл" и считает, что следующее "вкл" - это один чел. побывал. (17+1 для верности, т.к. он незнает при своем первом посещении "вкл" кто-то нажал или нет).
Неважно когда он попадет в комнату, каждый раз будет сбрасывать и плюсовать одного человека, пока не настанет 17 раз :).

Все. Я кончил :). Вопросы?

[Dimoks]

"не понятнооооооооо" (с) бабка из Камеди Клаб :D

Блин мне идея понятна... реализация не понятна.
Идея такая - Назнчить одного человека "счётчиком". Только он может трогать скажем первый (левый) выключатель? Правильно?

Плиз расспешите по пунктам :) Скажем для 5 человек. Счётчик. Начальное значение. Случайный выбор людей. Результат.

[talex]

[QUOTE=DimoksИдея такая - Назнчить одного человека "счётчиком". Только он может трогать скажем первый (левый) выключатель? Правильно?
[/QUOTE]
:) ДА.

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

Например:
Заходит 1, (левый "вкл") клацает правым и уходит.
Заходит счетчик, (левый "вкл"), он его "выкл".
Заходит 2, (левый уже "выкл"), клацает его "вкл" (что значит для счетчика, что ктото был).
Заходит 3, например, (см. п.1).
Заходит счетчик, (Левый "вкл"), он его "выкл".
Заходит 1 опять, (т.к он его еще ниразу не "вкл", то он его таки "вкл" :)).
Заходит 2, снова, (см.п.1)...
И т.д.

Это пример из 3 чел и счетчика, также и для другого любого кол-ва. ;)

[borisd]

Все верно за исключением

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

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

[talex]

Все верно за исключением

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

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

Зачем? :) Тогда счетчик не поймет кто один раз был, а кто два!!!
ИМЕННО 1 РАЗ!!!

[Andrej2006]

Форумчане решили переквалифицироваться в великих ЗНАТОКОВ.:)

[toroktyki]

Люди, тама вроде фраза есть в условии, типа "никто, окромя преступников, не будет иметь честь входить в комнату"? Если так, то почему бы им не оставлят следы своего пребывания на стенах или еще где(церепнуть там, еще чего)? Если пришел во второй (N-й раз), то не рисовать ничего? Тогда 17-й легко поймет, что были в комнате уже все. А выключатели... Та дергай, скока хошь!

[Dimoks]

:) ДА.

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

Например:
Заходит 1, (левый "вкл") клацает правым и уходит.
Заходит счетчик, (левый "вкл"), он его "выкл".
Заходит 2, (левый уже "выкл"), клацает его "вкл" (что значит для счетчика, что ктото был).
Заходит 3, например, (см. п.1).
Заходит счетчик, (Левый "вкл"), он его "выкл".
Заходит 1 опять, (т.к он его еще ниразу не "вкл", то он его таки "вкл" :)).
Заходит 2, снова, (см.п.1)...
И т.д.

Это пример из 3 чел и счетчика, также и для другого любого кол-ва. ;)
С таким алгоритмом 17 человек реально годами будут клацать. И не ясно быстрей срок закончится или такой алгоритм пройти :).
Т.к. "человек-счётчик" один и он может раз в 100 заходов поподать. А всё это время будет включен.

[borisd]

To talex:
Зачем? Тогда счетчик не поймет кто один раз был, а кто два!!!
ИМЕННО 1 РАЗ!!!

Исходя из каких условий задачи сделан такой вывод? Т.к. охранник каждый раз случайным образом выбирает заключенного, который пойдет кдацать выключатели, то некоторые заключенные могут побывать в камере больше, чем ИМЕННО 1 РАЗ!!!. Поэтому фразы из условия

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

и

"...что все мы, все 17 человек, уже побывали в комнате, я тотчас отпущу всех..."

можно трактовать, как все заключенные побывали в камере с выключателями ХОТЯ БЫ ОДИН РАЗ.;)


To Dimoks:

С таким алгоритмом 17 человек реально годами будут клацать. И не ясно быстрей срок закончится или такой алгоритм пройти .
Т.к. "человек-счётчик" один и он может раз в 100 заходов поподать. А всё это время будет включен.


Обратите внимание на пункт условия

"...Предложите стратегию позволяющую уголовничгам НАВЕРНЯКА выиграть, считая, что они будут жить достаточно долго, чтобы побывать в этой комнате как угодно много раз каждый..."

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

[Dimoks]

я слишком сильно абстрагировался :( не могу сосредоточиться на выключателях :)

мне непонятна ситуация - когда в комнату подряд войдут, к примеру, три человека которые там были первый раз.

каким образом они передадут "счётчкику" информацию что к=к+3 ?

что должен увидеть "счётчик" на выклчательях чтобы вкурить что было только что 3 "новых" человека ?

[borisd]

каким образом они передадут "счётчкику" информацию что к=к+3 ?

может так будет понятнее:


static void Main(string[] args)
{
int n = 17; //количество зеков
Random rnd = new Random(); //метод доступа у зекам
int[] prisoners = new int[n]; //статистика нажатий зеком выключателя А

int counterIndex = rnd.Next(n); //номер заключенного который является счетчиком

bool A = rnd.Next(2) == 1 ? true : false; // начальное положение выключателя A
bool B = rnd.Next(2) == 1 ? true : false; // начальное положение выключателя B
//положение А == true, является знаком того что обычный зек включил этот выключатель

while (true)
{
int currentPrisoner = rnd.Next(n);

if (currentPrisoner == counterIndex) //если зашел счетчик
{
if (A)
{
prisoners[currentPrisoner]++;
A = !A; //клацаем по А
}
else
B = !B; //клацаем по B

//Условие по кторому счетчик может определить,
//что все были в камере, хотя бы один раз
if(prisoners[currentPrisoner] == 2*(n-1))
break;
}
else //если зашел обычный зек
{
//условие когда обычный зэк может трогать выключатель А
if (prisoners[currentPrisoner] < 2 && !A)
{
prisoners[currentPrisoner]++;
A = !A; //клацаем по А
}
else
B = !B; //клацаем по B
}

}

Console.WriteLine("Done");
Console.ReadLine();
}

[Ferox]

я слишком сильно абстрагировался :( не могу сосредоточиться на выключателях :)

мне непонятна ситуация - когда в комнату подряд войдут, к примеру, три человека которые там были первый раз.

каким образом они передадут "счётчкику" информацию что к=к+3 ?

что должен увидеть "счётчик" на выклчательях чтобы вкурить что было только что 3 "новых" человека ?

Передаст информацию только первый из трех. Остальные будут ждать пока их сосчитают до следующего раза...

[Grau OL]

http://www.xoxma.com.ua/cgi-bin/pub/plain.pl?main=id141823

Другой вариант. :-)

[talex]

Обратите внимание на пункт условия

"...Предложите стратегию позволяющую уголовничгам НАВЕРНЯКА выиграть, считая, что они будут жить достаточно долго, чтобы побывать в этой комнате как угодно много раз каждый..."

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

Ответ правильный.

А по поводу
Исходя из каких условий задачи сделан такой вывод? Т.к. охранник каждый раз случайным образом выбирает заключенного, который пойдет кдацать выключатели, то некоторые заключенные могут побывать в камере больше, чем ИМЕННО 1 РАЗ!!!. Поэтому фразы из условия

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

и

"...что все мы, все 17 человек, уже побывали в комнате, я тотчас отпущу всех..."

можно трактовать, как все заключенные побывали в камере с выключателями ХОТЯ БЫ ОДИН РАЗ.

Что неясно? :) Каждый может побывать сколько угодно раз, но отметиться, что именно он был ("вкл" левый выключатель) ТОЛЬКО ОДИН РАЗ!!! за все свои визиты.

[talex]

[A href="http://www.xoxma.com.ua/cgi-bin/pub/plain.pl?main=id141823" [/A]

Другой вариант.

Тут либо не все начальные условия, либо не может быть решена такая задача. :)

Пораскинте !!!

В холле тюрьмы ( бывает же такое..) - 100 заключенных. Все имеют пожизненный срок. Начальник тюрьмы сообщает им, что через час всех разведут в одиночные камеры и они больше никогда не увидятся и не смогут общаться. Ежедневно компьютер будет выбирать случайным образом несколько(иногда 0 выбирает компьютер) заключенных. Их по очереди будут выводить из камеры в комнату. В ней ничего нет, кроме лампочки и выключателя, которым заключенный может пользоваться (лампочку не трогать).Начальное состояние лампочки: выключенна.Любой из заключенных, в определенный момент времени может сказать, что в этой комнате побывали ВСЕ! ( не важно, по разу или несколько раз) заключенные. Если он прав- то всех отпускают. Нет- казнят. У заключенных есть час на выработку алгоритма спасения.

Как освободить заключенных???


Как любой может сказать, что все побывали, имея данные лишь включена лампа или нет...

Бред...

[borisd]

Что неясно? :) Каждый может побывать сколько угодно раз, но отметиться, что именно он был ("вкл" левый выключатель) ТОЛЬКО ОДИН РАЗ!!! за все свои визиты.

Ок, тогда назовите до скольки должен считать счетчик, другими словами когда он может сказать, что все заключенные уже побывали? Пусть заключенных будет, как в оригинальном условии 17.

[borisd]

Тут либо не все начальные условия, либо не может быть решена такая задача. :)

Пораскинте !!!

В холле тюрьмы ( бывает же такое..) - 100 заключенных. Все имеют пожизненный срок. Начальник тюрьмы сообщает им, что через час всех разведут в одиночные камеры и они больше никогда не увидятся и не смогут общаться. Ежедневно компьютер будет выбирать случайным образом несколько(иногда 0 выбирает компьютер) заключенных. Их по очереди будут выводить из камеры в комнату. В ней ничего нет, кроме лампочки и выключателя, которым заключенный может пользоваться (лампочку не трогать).Начальное состояние лампочки: выключенна.Любой из заключенных, в определенный момент времени может сказать, что в этой комнате побывали ВСЕ! ( не важно, по разу или несколько раз) заключенные. Если он прав- то всех отпускают. Нет- казнят. У заключенных есть час на выработку алгоритма спасения.

Как освободить заключенных???


Как любой может сказать, что все побывали, имея данные лишь включена лампа или нет...

Бред...

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

[talex]

Ок, тогда назовите до скольки должен считать счетчик, другими словами когда он может сказать, что все заключенные уже побывали? Пусть заключенных будет, как в оригинальном условии 17.

До 17 :))))) (+1 как я писал выше для верности ;))

[talex]

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

Читаем внимательно условия "компьютер случайным образом выбирает несколько", без наличия человека-счетчика, как в предыдущей задаче - это не реально :)

[talex]

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

[borisd]

Читаем внимательно условия "компьютер случайным образом выбирает несколько", без наличия человека-счетчика, как в предыдущей задаче - это не реально :)

Внимательно прочитал условие...

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


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

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

[borisd]

До 17 :))))) (+1 как я писал выше для верности ;))

Наверное, Вы оговорились и хотели написать до 16, т.к. заключенных которые могут включить А, ослаось 17 - один счетчик = 16 и (+1 как вы написали выше для верности).

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


существует четыре возможности развития событий в начале

1.а) первым зашел обычный зек и А=выкл
1.б) первым зашел обычный зек и А=вкл
2.а) первым зашел счетчик и А=выкл
2.б) первым зашел счетчик и А=вкл

Счетчик считая до 16 в случае
1.а)считает верно и всех отпускают
1.б)считает неверно, если за все время побывали в камере все кроме одного зека
2.а)считает верно и всех отпускают
2.б)считает неверно, если за все время побывали в камере все кроме одного зека

Счетчик считая до 16 и используя +1 (для верности) в случае
1.а)вечно ждет 17-ое нажатие
1.б)считает верно
2.а)вечно ждет 17-ое нажатие
2.б)считает верно

Как Вы думаете, этот метод удовлетворяет условию задачи требующему выработать стратегию, позволяющую НАВЕРНЯКА освободиться?

[talex]

Насчет "вечно ждет", то в условии сказано: "считая, что они будут жить достаточно долго, чтобы побывать в этой комнате как угодно много раз каждый. "
То есть лимита по времени нет.

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

[borisd]

"вечно ждет" не от того, что кто то еще не щелкнул, а от того, что все кто мог щелкнуть по разу уже щелкнули и 17 нажатия просто не будет.

Ваше решение, в некоторрых случаях, противоречит условию НАВЕРНЯКА освободится. Именно поэтому заключенные вместо одного раза должны включить выключатель по 2 раза. Это позволит им именно НАВЕРНЯКА освободится в не зависимости от начального положения выключателей и порядка заходов в камеру.

З.Ы. Я предлагаю прекратить флуд в этой ветке, т.к. правильное решение было найдено, Вас же переубеждать никто целью не ставит.

[Expert]

Альтернативный вариант: все расчитываются по порядку и заходя в комнату пишут (ногтем, кровью, га..ном или еще чем..) свой номер, когда ряд из чисел заполнен знач все ок. А выключатели можно просто поклацать :)

[DorFF]

Начальное условие - выключатель А в положении ВЫКЛ.

Например, кто приходит в камеру первый раз включает выкл А (если он выключен). Если в камере он уже был, либо выключатель А включен, то дергает выключатель Б.

Счетчик, видя что выкл А включен, выключает его (и начинает считать), если выключен, то дергает выключатель Б.

И того, когда счетчик 16 раз выключит выключатель А - все 17 побывали в камере.

Но тут возникает запарка, если вначале выкл А стоит включенный, то 16-й раз он его выключет, когда последний его еще не щелкнул. Т.е. есть шанс не дождацца одного чела, которого заведут в камеру.

[Евгений]

народ, мне кажется, что вобще не должно быть счетчика-зека, ведь его могут в эту камнату пустить только один раз. А нам нужно чтоб решение задачи было НАВЕРНЯКА, т.е. любой зашедший в комнату может понять что уже все 17 зеков здесь побывали. хм...