Задача 337 (корупция)

[Bibi]

Попаднали сте в затвора след обир. В двойна килия.
Съкилийникът ви въвежда в обстановката и ви казва, че се носи слух, че Началникът на затвора е подкупен и е склонен да урежда бягства. Но не се знае каква му е тарифата. Знае се само, че не е повече от 100 жълтици.
Всяка сутрин Началникът минава на проверка по килиите. Така че можете да му отправяте по едно предложение на ден.

Каква схема на предложенията за подкупи ще измислите, за да научите точната му тарифа и при това да се измъкнете колкото може по-скоро?

(без Google...)

[MitkoS]

Ей така на пръв поглед (без Google), си мисля за следните неща:

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

3. И тъй като трябва да открием точната тарифа ... например аз ще започна да подкупвам от 1, а съкилийника - моето+2
На следващия ден, аз ще предложа сумата на съкилийника от предишния ден + 1, а той пак моето +2
При такъв алгоритъм, дневно се проверяват три последователни числа и в най-лошия случай, след малко повече от месец (33-34дни), ще знаем точната тарифа (и ще се извъкнем и двамата)

ПП. По-добре съкилийника да предлага моето +3
И след като той се измъкне, аз ще се измъкна най-много два дни по-късно.
Но пък при тоя алгоритъм се проверяват по 4 последователни числа дневно, което гарантира 24-25 дни

ПП2 Може да се подобрява още - по-малко от 20 дни.
Съкилийника предлага моето +10 ...

[Bibi]

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

Иначе си на прав път с разсъжденията.

[MitkoS]

Добре, след тия доуточнения по условието, най-доброто за което се сещам в момента е такова:

Той ще започне от 10 със стъпка 10 (10,20,30,...)
И когато излезе, аз ще почна от неговото предпосдедно предложение със стъпка 1
Така че, пак сме най-много 19 дни (или май са 20).

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

[Bibi]

До тук чудесно!

Кофтито в случая е, че след около 15 дена се чува, че ще те местят в друг затвор. А там може и да няма подкупни надзиратели.
Но, ако се напънеш още мъничко, до тогава ще си вън.

[MitkoS]

Хайде да ги направим 16 дни

Съкилийника започва от 15 и всеки ден добавя с едно по-малко
15
15+14
15+14+13
15+14+13+12
На деветия ден той е стигнал 99
15+14+13+12+11+10+9+8+7=99

И ако още не е излязъл на 9-тия ден, на 10-тия ден аз казвам 100
Ако е излязъл по-рано на N-тия ден, то аз имам да проверя няколко числа - общия им брой на тия "няколко" числа е 15-(N-1)
Съответно максималния общ брой дни и за двамата е:
N+15-(N-1)=16 дни

ПП. По-горе съм се престарал с тая "минус единица в скобите".
След като съкилийника излезе на N-тия ден, то общия брой на тия числата които трябва да проверя е най-много 15-N
И съответно максималния общ брой дни и за двамата е:
N+(15-N)=15 дни

[Bibi]

Да, горе-долу това е най-икономичното решение.
Може да се спести още един ден, ако се започне от 14, 14+13,..., при което на 11-тия ден се достига до 99.
Останалото е същото, както при теб.

Ето източникът: http://tr.im/HuGT
Има и други интересни.
Тази я взех от задачата с яйцата, които падат от 100-етажна сграда. Нарочно опитах да я преразкажа с друг пример.

[MitkoS]

Всъщност това което съм предложил става за 16, но не за 15

[dedis]

Не може ли да се измисли формула - сума на ред - и да се търси минимум?
Респективно - с индукция - да се разсъждава от малко число и да се върви към 100.

[MitkoS]

Според мен, лесно ще се докаже с допускане на противното, че това което е предложила Bibi е минималното.

Искате ли да разгледаме варианта с тройна килия и двама съквартиранти (общо трима в килията) ?

[pimpirlit]

Аз ги изкарвам 10 дни.

Третия, допълнителен апаш "дели" тарифата от 100 жълтици на приблизителни 3 равни части, т.е. предлага подкуп от 33 и после 66. После прилагаме метода на MitkoS върху съответния интервал. Така задачата се свежда до намиране на минималния брой дни, за които можем да нацелим точния подкуп от max. 34, което правим с начална стъпка 8 жълтици.

PS: Май може да са 9 дните ако могат да бягат по двама наведнъж, но не съм го доогледал окончателно.

[MitkoS]

Аз ги изкарвам 10 дни. ...

Май си много самоуверен и смел.
Първо, за да провериш интервал от 33 жълтици, са ти необходими 9 дни (както сам казваш, за такъв интервал трябва да се започне със стъпка 8)
И второ, представи си, че тарифата е 99 - имаш три загубени дни за да уцелиш интервала с първия затворник и след това още 9 ===> станаха 12

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


... Според мен, трябва да е нещо такова (четири интервала):
1-ви затворник
37,
37+29,
37+29+22,
37+29+22+11 = 99
На последния ред, най-дясното събираемо трябваше да е 16, но излизаме над 100, което показва, че за същия брой дни бихме могли да отгатнем точната тарифа дори и ако тя беше в интервала от 1 до 105, а не от 1 до 100

Съответно, (след като първия затворник излезе):
за 9 дни можем да проверим (максимален) интервал от 37=2+2+3+4+5+6+7+8
за 8 дни можем да проверим (максимален) интервал от 29=2+2+3+4+5+6+7
за 7 дни можем да проверим (максимален) интервал от 22=2+2+3+4+5+6
за 5 дни можем да проверим (максимален) интервал от 11=2+2+3+4

Т.е., максималния брой дни при тия четири интервала е 10. И както се вижда, при тоя алгоритъм пак за 10 дни можем да проверим интервала от 1 до 105


ПП. Докато го писах това, проумях как може да се спести (поне) още един ден. Но ще си затрая засега, за да е интересно и на другите решаващи.

[Bibi]

Мисля, че за 9 дена с трима затворници могат да се проверят 121 стойности.
Първият трябва да се цели последователно в числата: 36, 64, 85, 100, (110, 116, 119, 120).

[MitkoS]

Мисля, че за 9 дена с трима затворници могат да се проверят 121 стойности.
Първият трябва да се цели последователно в числата: 36, 64, 85, 100, (110, 116, 119, 120).

И как точно ще го направиш, например ако тарифата е 8 ?
ден1 : първи затворник казва 36 и излиза
ден2 : втори затворник казва 8 и излиза
ден3 : трети затворник казва 1 и не излиза
ден4 : трети затворник казва 2 и не излиза
ден5 : трети затворник казва 3 и не излиза
ден6 : трети затворник казва 4 и не излиза
ден7 : трети затворник казва 5 и не излиза
ден8 : трети затворник казва 6 и не излиза
ден9 : трети затворник казва 7 и не излиза
ден10 : трети затворник казва 8 излиза при точна тарифа

И другото в което ми се струва, че се разминаваме е дали да е 36 или 37 (съответно дали да е 28 или 29 и т.н.). Няма полза последния интервал в редицата да е 1. По-точно, съвсем спокойно може последния интервал да е със същия размер като предпоследния интервал. Това горе-долу е обяснението:
Нека горната граница да е N, а търсената тарифа да е по-малка или равна на N.
Нека
пред-предпоследното казано от предишния затворник да е N-2-2-3,
нека предпоследното да е N-2-2
и нека последното да е N-2.
Ако тоя затворник излезе чак при N-2, то аз трябва да проверя N-2-1 и N-2 (т.е., проверявам две числа)
Ако тоя затворник НЕ излезе и при N-2, то аз трябва да проверя N-1 и N (т.е., пак проверявам две числа)
Затова считам че е по-оптимално да говорим за 37, а не за 36

[Bibi]

И как точно ще го направиш, например ако тарифата е 8 ?

По същия начин както в задачата с двама, ако тарифата е 14, аз научавам този факт на 14-тия ден, но излизам чак на 15-тия.

За 37 и аз си мислех, но не го доразгледах. Утре на свежа глава отново ще помисля.

Някакви логаритми ми се въртят в подсъзнанието, но за сега не им хващам цаката.