Крадец 2

[vladob]

За задачата со две лица во една келија.

Зошто никој не ја разгледува можноста за бинарно пребарување.
Пример:
Првиот ден сокелиецот нуди 50 и ако чуварот не прифати јас нудам 75. Ако прифати 75 не плаќам и останувам за следниот ден.
Следниот ден сокелиецот нуди средна вредност од 50 и 75 (63). Ако чуварот прифати јас нудам средина од 50 и 63, односно 57. И двајцата не плаќаме и остануваме за следниот ден без разлика дали е прифатена понудата.

На овој начин четвртиот или петтиот ден и двајцата ќе ја знаеме точната цена.
Значи за најкраток временски период и со најмала можна вредност ќе излеземе двајцата.

Или можеби јас не сум го разбрал условот на задачата добро ?

[Реклама]

[martosss]

не е така, защото ако офертата е печеливша, то затворникът не може да се откаже от нея, той е длъжен да я приеме. Така ако дадеш 50 и тарифата на надзирателя е 49, то той ще изкара единият съкилийник и другият ще трябва да провери всички числа от 1 до 49, което ще му отнеме твърде много време Затова и схемата е толкова сложна. А това с трите затворника беше добро продължение на задачата.

[dgs]

martosss,
В решението си от 11 дни не спазваш принципа "всеки загубен ден от първия затворник трябва да може да се компенсира от размерите на оставащите интервали".
И затова не си стигнал до минималното решение от 10 дни.

Така както си ги подредил интервалите определени от първия затворник, прилича на налучкване.

[martosss]

ох, да, наистина не съм смятал за оптимален вариант за разпределение на дните при оставащи двама завторници, а всъщност при 3-ма отговорът наистина е 10, а първият ден 3-тият затворник може да каже цели 38! Оставям на другите форумци да се досетят какви ще са следващите залози

[dgs]

Не е ли 37 ?
Ако тарифата е точно 38, и първия затворник излезе, то после с останалите двама, не можеш с 9 опита да провериш интервала от 1 до 38. Но с 9 опита можеш да провериш интервала от 1 до 37.

ПП.
Хайде оттук нататък, вместо за "дни", да говорим за "опити за подкуп". Съответно ще търсим минималния брой "опити", а не минималния брой "дни".
Така ще се избегне двусмислието което имаме сега - колко подкупа на ден може да приема надзирателя.

[martosss]

Опа, наистина е 37, пак прекалих