Задача 107 (Роботи)

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



[етикет:] Left

[етикет:] Right

[етикет:] Goto етикет

[етикет:] BGoto етикет



При изпълнение на оператора Left, робота прави стъпка вляво по линията, като се премества на число по-малко с единица. Оператора Right води до стъпка в другата посока. Операторa Goto е за безусловен преход в програмата към етикета указан след него. Оператора BGoto е за условен преход в програмата. Ако при изпълнение на този оператор робота се намира на точка с еднния от двата парашута, то само тогава се извършва преход към етикета след оператора, ако не се намира на точка с парашут се изпълнява слеващата команда от програмата. Изпълнението на всяка команда отнема една секунда, независимо дали е преместване по линията или преход в програмата. Роботите изпълняват командите едновременно.



Представете си трето нещо. Програмите на роботите са напълно еднакви.



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

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

Понеже ми се искаше да направя програма, която среща двамата след най-малко стъпки, стигнах до една, която мисля, че отговаря и на двете условия: има 5 реда код и е със сложност O(n), където n е разстоянието, на което са се приземили. По-точно, ако се движат по нея, ще се срещнат на стъпка 9n-6.

Няма да я казвам сега, за да не влияя на останалите. Ще ми се някой да измисли нещо по-късо.



/Ето един пример:

01: Left

02: Right

03: Goto 12

....

12: Left

13: BGoto 02

14: Right



Изпълняват се стъпки 01, 02, 03, 12 (безусловния преход в 03 ни води там), 13

Сега, ако роботчето е попаднало в точка с парашут, ще изпълни стъпка 02, ако точката е без парашут, ще продължи надолу със стъпка 14.

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

Не съм много на ТИ с програмирането, но като остана с малко повече време ще пробвам да измисля нещо на базата на четирите възможни оператора. [:o)]

Биби ви е дала хубав жокер - най-кратката програма е с 5 реда



@BerkStock

Не забравяй, че програмите им са еднакви :)

Хм... Доста интересна задачка.



Kодът по-долу изпълнява условието, тогава, когато двамата парашутисти са се приземили на две съседни точки:



1: left

2: bgoto 2

3: right

4: right

5: goto 1



Довечера ще помисля и за общо решение (ако има)...



<font color="blue">//offtopic

баси и ш***ния бейсик...[}:)]</font id="blue">

Има, има...

Здравейте,

Макар, че чета форума много отдавна чак сега се престраших да се проявя и като чукча-писател[:)]

Моето предложение е следното:



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

Реализацията:



01: LEFT

02: BGOTO 04

03: GOTO 01



04: LEFT

05: GOTO 04



LEFT спокойно може да се замени с RIGHT без това да промени нещата.

Първият цикъл (01:-03:) се изпълнява за 3 сек. и води до една стъпка на робота. При излизането от него (достигане на парашут) се влиза във втория (04:-05:), който се изпълнява за 2 сек. и води също до една стъпка на робота. От него вече излизане няма - роботите ще подскачат по линията докато им свършат батериите, но за това не се казва нищо в условието на задачата[:)]

Не ми се смята след колко време ще се "настигнат", но чакам Bibi с интерес...

<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">Не ми се смята след колко време ще се "настигнат", но чакам Bibi с интерес...



<div align="right">Originally posted by pimpirlit*-*08/12/2004*:* 17:45:58</div id="right">

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



Добре дошъл, pimpirlit :)!

Струва ми се вярно решението ти, вярно е също и че свежа кръв тук е винаги приятна изненада [:)]

Cvetanov е дал задачката, но щом ще чакаш 'каката'...[;)]

@pimpirlit,

Моето решение е съвсем същото! [:)]



В началото Цветанов беше формулирал задачата "да се намери най-кратката програма..." и аз не знаех какво търси - с най-малко оператори или за най-кратко време да се срещнат. Затова се заиграх и с двете и после ми стана интересно.



Не знам защо се изплашиха хората? Тази задача не е за програмисти!

Там най-трудното е да се запомнят операторите, останалото е само мислене.

А тук са ни дали само 4 действия...



Аз също приветствам новия войн на фронта на Мисълта! [;)]

А и това е първото вярно решение на днешната задача.

<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">

Cvetanov е дал задачката, но щом ще чакаш 'каката'...[;)]



<div align="right">Originally posted by Krusteva*-*08/12/2004*:* 17:05:48</div id="right">

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

Aми "каката" беше загадъчно-недоизказано-объркваща в първия си пост. [;)] Не можах да ги докарам тия 9n-6 и това си е [:(]

A иначе, естествено, че Cvetanov ще въздаде справедливост...

<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">A иначе, естествено, че Cvetanov ще въздаде справедливост...



<div align="right">Originally posted by pimpirlit*-*08/12/2004*:* 18:24:46</div id="right">

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



Шегувах се, имах предвид, че да чакаш 'кака'-та си е по-гот (мисля , че си мъж все пак [;)])

Не знам за какво говорите

някой ще напише ли ясно предложението си -да не си напрягам клетчиците си..........

ще ми трябват тези дни.......



01: LEFT

02: BGOTO 04

03: GOTO 01



ами тук единият си ходи наляво.....

или не ставам за програмист

@pimpirlit,

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

След 3n-2 стъпки, този, дето "догонва" другия, ще настъпи мотиката (пардон, парашута).

После за всеки 6 такта първия се премества с 2 точки, а втория - с 3. Разликата им се стопява с по една точка на всеки 6 секунди. Така след 6n-4 такта те ще се целунат.

Общо 9n-6.



@WIse,

И двамата работят по една и съща програма и ходят в еднаква посока.

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

Предният продължава да си марширува със старото темпо.

не отлепям..........

единият си ходи наляво до упор по този алгоритъм