Задача 323 (ламята и роботите)

[MitkoS]

Тук първоначално трябваше да пише нещо за три сърдити каки, които вървяли по кръгъл коридор. Освен това не можели да се понасят и всеки път, когато две от тях се срещали в коридора, се обръщали кръгом и продължавали да вървят. Да, ама нещо не ми харесва такъв сюжет. И без това каките са дефицит - няма нужда да ги подтискаме допълнително.

Затова, сюжета е такъв:
В един идеално полусферичен хълм имало пещера и в нея живеела една ламя, която периодично тормозела селяните в близкото селце. Около хълма имало път, който бил идеална окръжност. От пътя към пещерата можело да се влезе през три входа (врати). Те били неравномерно разположени една от друга. Освен това, всеки вход си имал особеност: малко по-навътре след първата врата имало водно препиятствие, след втората имало огнено препятствие, а след третата имало каменно препятствие (падали камъни).
От селото периодично изпращали юнаци да убият ламята, но те обикновено не се справяли с препятствията. Тези които все пак се справяли с препятствията, ламята набързо ги излапвала още преди да си извадят мечовете. Накрая в селото не останали юнаци.
Обаче местния гуру, бил също така и IT-гуру (или поне така си въобразявал, както ще се види по-надолу). Разбрал вече, че няма да се справи с ламята с конвенционални средства и взел че изобретил робот-юнак, който да преплува водното препятствие. Обаче гуруто допуснал софтуерен бъг в модула "влизай" и робота влязъл през входа с огъня и изгорял. Гуруто направил втори робот, завел го под ръка до точната врата и го пуснал вътре да убие ламята. Обаче робота бил малко бавен и ламята го смачкала.
Гуруто не се отчаял, отчел всички грешки до момента и генерално променил подхода. Създал три нови версии - по един робот-юнак за всяко от препятствията, (// т.е. робот от първата версия може да се справи с водното препятствие, но не и с огъня или камъните, съответно от втората версия може да се справи с огъня ... и т.н.), с идеята трите робота да влязат едновременно през трите врати и така по-лесно да могат да се справят с ламята. За да не стават грешки с вратите, създал и съответен датчик за всяка врата, който да се разпознава само от съответния робот за този вход.

Пренаписал модула "влизай" на роботите. Вътре в алгоритъма вмъкнал следните правила:
1. Тръгвам към моята врата. Ако изгубя връзка с датчика, продължавам напред по пътя в същата посока
2. Ако възстановя изгубена връзка с датчика, продължавам в същата посока (гуруто не си падал по оптимизации и разчитал на това, че пътя е окръжност)
3. Като стигна до вратата, пускам сигнал до другите два робота, че съм пред моята врата.
4. Ако получа от тях сигнали, че и те са пред техните врати в същия момент, то ВЛИЗАМ. Ако не получа, то продължавам напред по пътя в същата посока (Това последното, е очевиден бъг на гуруто, ама какво да се прави: copy-paste и малко бързане и недоглеждане от негова страна. Трябвало е да напише "спирам пред вратата, пускам сигнали и чакам сигнал от другите двама")
5. Ако срещна друг робот докато се движа напред, то обръщам се на 180 градуса и продължавам напред по пътя (Това гуруто го сложил без много да мисли. Изглеждало му като някаква застраховка)

В една бурна нощ, докато ламята спяла, гуруто наредил датчиците на вратите, разположил роботите на разстояние всеки на три метра от неговата врата. Понеже бил напълно уверен в алгоритъма "влизай", разположил роботите малко безразборно - един от ляво на три метра от неговата врата, друг от дясно на три метра от неговата врата.
Завъртял се три пъти, преплюл три пъти през лявото рамо, после три пъти през дясното рамо, подскочил три пъти и после самоуверено натиснал бутона СТАРТ на дистанционното. Роботите тръгнали към вратите, но точно когато били на един метър всеки от своята врата, изтряскала гръмотевица която повредила всичките датчици и роботите подминали вратите.
Гурото до такава степен бил самоуверен, че бил направил единствено бутон СТАРТ. Нямало СТОП, нито нищо друго с което да спре и постави роботите в изходно положение. Единственото което можел да направи, е да подмени датчиците на вратите. Междувременно, роботите спазвали алгоритъма "влизай" и обикаляли около хълма и всеки път, когато два от тях се
срещнели, то тия двамата се обръщали и продължавали напред по пътя в обратна посока, съгласно правило 5. от модула "влизай".

Пита се:
1. Въпреки кривия алгоритъм на гурото, ще има ли момент, в който всеки от роботите ще е пред своята врата и съответно тримата ще разменят сигнали едновременно и ще влязат едновременно?
2. Ще има ли момент, при който всеки от роботите ще е в изходно положение на три метра от неговата врата и текущата му посока на движение ще е към вратата му. (От което автоматично следва и 1.)

Знае се, че роботите се придвижват с еднаква скорост. Също така, гуруто успешно подменил датчиците, но това му отнело известно време. Също така, може да се счита, че времето през което робота пуска сигнал "пред вратата съм" и чака обратен сигнал от другите двама е нула, т.е. робота не спира в момента в който праща сигнала.

[Ludaka]

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

A третия робот да не е бил право срещо неговата врата и да е забил на едно място(да не е знаел на каде да тръгне)?
Ако е така задачата после има просто решение.

[MitkoS]

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

[IvO™]

Честно казано - мозъка ми стана на окръжност...

[MitkoS]

Честно казано, за тая задача се изискват "задълбочени познания по елементарна математика", което в превод означава 9-ти клас.

[kamenf]

Естествено, че ако всички роботи се движат в една посока, те ще се окажат в начално положение след една обиколка.
В другия случай един от роботите се движи обратно на останалите два. Ще се окажат в начално положение след като всеки робот измине път равен на три пъти дължината на окръжността.
За по-лесно може да си представим, че роботите не си проментят посоката, а си сменят идентификацията когато се срещнат - така може да си представим, че всеки робот ще се върти по окръжността в еднаква посока и само си променя да речем цвета. Така "преработеният" различен (този дето се движи наопаки на останалите два) робот се среща 4 пъти с другите за една своя обиколка, т.е. си сменя ИД-то 4 пъти, което значи, че на всяка трета среща ще си е с първоначалното ИД. след 3 обиколки това се е случило 12 пъти, което ще рече че всеки си е с оригиналното ИД и то в изходна позиция.

[MitkoS]

Онзи ден, докато съставях задачата, стигнах до извода, че след 12 срещи, се стига до изходно положение. Само че при моите разсъждения се получи далеч-далеч по-дълго решение. Даже и Excel ползвах.

kamenf, поздравления,
Великолепно обяснение. Направо съм във възторг.

[kamenf]

Митко!!!

Мдаааа... всичко е много хубаво, само дето не съобразих, че може и да се наложи да давам задачка, а нямам готова...
Нищо де - тия дни все ще спретна нещо... ммм... лесничко.

[IvO™]

...Даже и Excel ползвах...

О, даа, Мите, "задълбочени познания по елементарна математика"...

[MitkoS]

Иво,
В моето решение имаше разни еретични неща като pi, 2*pi, (d1+d2)/2
Excel-а го ползвах най-накрая, за да съм сигурен, че няма да пусна крива задача.

НОК - "най-малко общо кратно".
Както виждаш, НОК е единствения математически прийом, който се използва в решението на Камен. Останалото е желязна логика. Най-ценното в случая е, че решението на Камен лесно може да се обобщи за N = m+n на брой робота, където m робота вървят наляво, а n робота вървят надясно. При моето решение, това обобщение практически няма как да стане.

Ако искаш, може да се пробваш за N=n+m робота.
Ако трябва да бъдем съвсем честни, НОК по-скоро е от "задълбочените познания по елементарна аритметика", което е най-много 6-ти клас.

[IvO™]

Няма проблем, Мите.
Аз се въртях в собствени орбити...

[Slero]

Ако трябва да бъдем съвсем честни, НОК по-скоро е от "задълбочените познания по елементарна аритметика", което е най-много 6-ти клас.

И добре развито логическо мислене, с каквото много (повечето) хора не се сдобиват и до края на дните си, ако и да имат по две или повече научни степени...