Задача 186 (индианци)

Индианско племе се приготвя за битка. Стягат бойните оръжия, барабаните бият с ритъма на сърцето...

Накрая шаманът слага на челото на всеки магически знак. На част от бойците - Х, на останалите - Y.

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

Но поверието гласяло, че ако някой се опита да подскаже на друг какъв знак вижда на челото му, това би било подигравка с боговете и двамата неминуемо ще загинат в предстоящата битка. Индианците уважавали боговете си, и въпреки това (а може точно поради това) успели да подредят безупречно колоната.

Как?

1. Застават двама индианци един до друг.

2. Идва трети, четвърти... и поглежда какво имат на челата. Ако всички имат еднакви символи, застава до тях. Ако са с различни символи, се нарежда м/у X и Y.

Снощи, като видях, че обичайните заподозрени сладко спят, реших да дам тази задача, за да се дореди някой по-боялив. Обаче Съдбата е неумолима, решила си беше още при предната задача да избере Edin_Lud и никакви номера не й минават! [:)]

<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">Снощи, като видях, че обичайните заподозрени сладко спят, реших да дам тази задача, за да се дореди някой по-боялив. Обаче Съдбата е неумолима, решила си беше още при предната задача да избере Edin_Lud и никакви номера не й минават! [:)]



<div align="right">Originally posted by Bibi - 25/02/2005 : 11:37:49</div id="right">

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



<s>Bibi, да разбирам ли, че това е верния отговор [?] ако е - разяснете, че не ми е ясно как ще проработи [8)]</s>



Оооо да! Видях го много ясно - работи като заклинание [:D]

С индукция [:P]

1. Колона от 1 човек винаги е правилно подредена, какъвто и да е знакът му.

2. Ако N от войните вече са заформили добре подредена колона:

Идваш ти (N+1-вия), не знаеш какъв е знакът на челото ти, оглеждаш я, виждаш, че до тук подредбата е добра и се мушкаш там, където е границата между двете групи. След теб пак нещата са нагласени както трябва, независимо дали си бил с X, или с Y.



Ако колоната, която виждаш е само от един вид индианци, "границата" между групите не се вижда, затова заставаш в някой от краищата. В този случай, ако твоят знак е бил различен от досегашните, на теб се пада честта да решиш дали тя да стане XY или YX (т.е. кои да са отляво и кои - отдясно). Поради това, ако шаманът смята, че това има значение за изхода от битката и държи примерно

X-войните да са отляво, ще трябва по-внимателно да мислиш кой от двата края да си избереш. Но както е формулирана задачата сега, това е без значение.

От всички тези разсъждения се вижда и друго - първият, който е с различен знак, след окончателното подреждане на бойния ред, "ще води хорото" в единия му край (ако използват описания метод).

Bibi,

много ми хареса задачката. Вярвам няма да ми се сърдиш ако я допълня ... с Z.



Как ще стане номера ако шамана нацапа с Z част от войните?

Че тогава има ли решение?

Виждам решение, но то е на съвсем друг принцип.

Ако prt знае някакъв метод, аналогичен на описания тук, ще изчакам, за да го науча. А моя няма да бързам да го кажа [:P]

Да си призная - решението, което си представях когато писах допълнението на задачата не работи - беше като емблемата на Мерцедес (три лъча), но в този случай ще си "подсказват" доста сериозно.



Измилих друго решение - дано е работещо.

Значи... Нека за по-лесно обяснениет приемем, че X и Y са с бяла боя написани, а Z с зелена.



Войните правят 2 последователни нареждания. При първото прилагат горната схема като се интересуват само от цвета на буквата. В края на наредбата ще имаме примерно:

XYXYXYXYXZZZZZZZZZZ



След това започват (от единия край на горната редичка/опашка) пак по познатата ни схема, но вече внимават само да се пъхнат между X и Y.

Да ама така тези които са със зелено ше разберат това при второто подреждане.



//Но ако са четри групи тогава става. <s>Даже може да се направи с едно подреждане</s>.. Ей не е истина какви простотии пиша като съм уморен



// А как ще реши най-крайния от белите че той трябва да почне втората подредба, а не този който е на другия край.

@prt,

Това, което казваш става, така че ще си запазя моята идея за по-натам [;)]

prt, но как последният, който се е вмъкнал в първата(цветовата) подредба, ще разбере дали е от белите(X или Y) или от зелените(Z)? А покакъв начин ще постигнат съгласие X и Y да са бели, а Z зелени? Дали няма да ги настигне проклятието на боговете?

@Yasen6275,

я обясни по-подробно какво имаш предвид?



@daley,

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

<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">@Yasen6275,я обясни по-подробно какво имаш предвид?



@daley,

След първата стъпка от метода на prt, всеки от колоната гледа хората, които са му съседни. Ако са двама с различни цветове или двама зелени, остава, ако са двама бели - маха се, за да участва във втората стъпка. Така в колоната остават всички зелени и единия бял.<div align="right">Originally posted by Bibi*-*25/02/2005*:* 14:57:28</div id="right"></td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote"><s> И оставайки само един бял и зелените в колоната като изключим двамата в края останали знаят какъв символ имат (единствения зелен). Ако са два зелени и два бели символа имаме едно подреждане първо по цветове. А след като приключи то двамата най-крайни почват подреждане по символи на същия принцип.</s>



/уффф пак простотия написах. Условието е да не си подсказват, а не да незнаят