Задача 199 (Психиатрична клиника)

[Lupus]

<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Аммм, до час-два очаквайте закачка.



<div align="right">Originally posted by InfiniteChaos*-*12/03/2005*:* 14:24:40</div id="right">

</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

А до тогава - по леглата! Че то както казва поговорката:

"Луд умора няма"[:D]

[Edin_Lud]

Точно това имах предвид като казах, че си спомням случката. Задачата е 1:1 с 154-та. Разликата е, че там всеки беше длъжен да превключва и затова е втория ключ - играе ролята на "съзерцаване".<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Иначе нашия план беше по-скоро като твоя първи, където преброителят има право само да гаси, с разликата че другите имат право да светват по два пъти и той дебне 2n-тото светване.</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

Ако ми позволиш лека поправка - на 2n-2-рото светване ще бъде сигурен. 2n-то светване няма да има никога - все пак този, който брои, не светва => светват само n-1 човека х 2 пъти = 2n-2 светвания общо [:D]

[Key]

<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Точно това имах предвид като казах, че си спомням случката. Задачата е 1:1 с 154-та. Разликата е, че там всеки беше длъжен да превключва и затова е втория ключ - играе ролята на "съзерцаване".<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Иначе нашия план беше по-скоро като твоя първи, където преброителят има право само да гаси, с разликата че другите имат право да светват по два пъти и той дебне 2n-тото светване.</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

Ако ми позволиш лека поправка - на 2n-2-рото светване ще бъде сигурен. 2n-то светване няма да има никога - все пак този, който брои, не светва => светват само n-1 човека х 2 пъти = 2n-2 светвания общо [:D]

</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">



Хммм.. ама ние май бяхме n+1 по настояване на онзи с шизофренията дето сега е в изолатора [:D]

[Bibi]

Имам възражения по решението.

Не, че е важно вече, ама ако на някой му се слуша, да ги кажа?



//EDIT

Всъщност при всички положения ще кажа.

Контрапример с трима луди, влизащи в ред 1-0-2-1-2-0:

Влиза Първи_Луд и запомня ON.

Влиза Преброителят и променя на OFF.

Влиза Втори_Луд и запомня OFF.

Влиза Първи_Луд, вижда промяна и се отчита - ON.

Влиза Втори_Луд, и за него има промяна - OFF.

Влиза Преброителят, не забелязва промяна и решава, че никой не е влизал междувременно. А "колегите" му нямат право повече да пипат ключа.



//Това горе не беше много доизпипано, но схванахте идеята.

Ако някой запомни едно състояние за начално, а друг - друго, тогава настава каша. Пробвайте с 0-1-0-2-1-2-0.

[Key]

@Биби



<s>

Целия съм в слух.



// btw на мен самия снощи ми я дадоха задачката и не претендирам да съм защитил докторат по нея.</s>



Мдаа май и тук анихилацията на смени минава. Жалко. Как процедираме в такъв случай? Ако няма против мисля най-добре хаоса да си дава следващата задача, а аз да отида да си посипвам главата с пепел и да пия валериан с бира.

[Edin_Lud]

Биби е права. Номерът със променянето не работи по този начин. Съществува като решение, но с по-голям брой промени (мисля че бяха 3n-1).

Най-простия, но не и най-сполучлив (бърз), план е всички без Брояча да изключват, а само Броячът да включва (или обратното). Тогава, при N човека + 1 Брояч, успехът е гарантиран при 2N манипулации на Брояча.

Има и още един метод, който съм срещал, но не можах да рабера напълно. Всички броят разделени на групи.