Помогите решить пожалуйста

[TiPo]

Здравствуйте, что-то не могу решить задачу. Пишите пожалуйста предположения и советы. Но если вы напишете решение, то пожалуйста поместите его в спойлер, т.к. задачу хочу всё таки решить сам(или почти сам).

Вот само условие:

В давние времена Золотая Орда ежегодно собирала дань золотыми монетами. Известный крымский

хан Гирей решил схитрить: выплачивая дань из N золотых монет, он подложил среди них одну

фальшивую – более легкую монету. Об этом донесли казначею Золотой Орды. Для обнаружения подделки

он решил использовать магические весы, работающие на урюке.

На чаши магических весов кладутся две кучи монет. Весы устанавливают, совпадает или

различается вес этих куч. При этом, если кучи имеют разный вес, то весы указывают, какая из куч легче.

При совпадении веса обеих куч весы требуют R плодов урюка, а при несовпадении – U плодов.

Казначей, сам любитель урюка, хочет и фальшивую монету обнаружить, и сэкономить на урюке.

Требуется написать программу, которая по заданному количеству монет N, при условии, что только

одна из них легче других, укажет минимальное количество урюка, с помощью которого эта фальшивая

монета гарантированно будет обнаружена.

Формат входных данных

Во входном файле в единственной строке находятся три целых числа N, R и U (2 ≤ N ≤ 1 000 000,

1 ≤ R, U ≤ 1 000 000), где N – количество монет, R – количество плодов урюка, затрачиваемых в случае

совпадения веса куч монет, U – количество плодов урюка, затрачиваемых в случае их различия. Все числа

разделены пробелом.

Формат выходных данных

Выходной файл должен содержать одно число – минимальное количество урюка, с помощью

которого гарантированно будет обнаружена фальшивая монета

Примеры:

Входные данные | Выходные данные

• [*:4d07042b65]4 3 1 | 2
  [*:4d07042b65]3 3 1 | 3
  [*:4d07042b65]15 2 3 | 8
  [*:4d07042b65]10 2 1 |3

[_delphin_]

В любом случае требуется минимальное количество сравнений.

При решении задачи в лоб нам понадобиться количесво взвещиваний (сложность) max = N-1. это вариант неприемлем.

Улучненный вариант с делением монет на кучи. Он подходит при N>4

тогда делим N div 2 и взвешиваем. сложность задачи будет max N div 2 while n>5

пока все))...

[promises]

разве N-1? мы же по 2 монеты сравнивать будем, если в лоб, вроде как получится N/2. Пока что деление пополам выглядит наиболее разумным.

кстати, не совсем понял зачем дано кол-во урюка R, т.е. можно как то эту задачу решить от противного?

p.s. сейчас что-то голова не особо варит, завтра еще раз гляну

[TiPo]

Кстати, я вчера "состряпал" следующее, но это решение я считаю неверным:

n,r,u:integer;
procedure ChetN;
var
Shet:integer;
begin
Shet:=0;
repeat
n:=n div 2;
Shet:=Shet+u;
until n=1;
writeln(Shet);
end;
procedure NechetN;
var
Shet:integer;
begin
if n=3 then begin Shet:=u*3; writeln(Shet); exit; end;
Shet:=u*2+r;
writeln(Shet);
end;
begin
readln(n,r,u);
if n mod 2=0 then ChetN
else NechetN;
readln;
end.

var

[TiPo]

Если решили, то проверьте своё решение здесь: http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=4908&chapterid=111223

[TiPo]

По-моему что-то не так с нечётными числами:

var
        n,r,u,Shet:integer;
begin
        readln(n, r, u);
        Shet:=0;
        if n=3 then Shet:=Shet+r
                else repeat
                        n:=n div 2;
                        if n=3 then Shet:=Shet+r
                                else Shet:=Shet+u;
                until n=1;
        writeln(Shet);
        readln;
end.

[ArtyomK]

Все не так тривиально)

N = 10;
R = 1;
U = 1 000 000;

[danger]

Стандартная задача. Ищите тернарным поиском, а не бинарным.

[ArtyomK]

danger

Разве это решает проблему в случае с большими по сравнению с R значениями U?

[piecemaker]

В бинарном всегда неравенства (за исключением нечетного множества, когда отбрасываемая единица оказывается искомой). В тернарном возможны равенства. В случае одинакового количества сравнений, если U больше R, тернарный поиск будет более эффективен.

[ArtyomK]

piecemaker

Более эффективен, тут и спорить не о чем. Но задачу решить не поможет, насколько я понимаю) Потому что нужно не более эффективное решение, а самое эффективное)

Да и к тому же:

минимальное количество урюка, с помощью которого эта фальшивая

монета гарантированно будет обнаружена.

То есть нужно брать оценку сверху. И при оценке затрат на тренарный поиск нужно рассматривать случай, когда все сравнения закончились худшим результатом.

[piecemaker]

при худшем результате тернарный поиск вырождается в бинарный просто. так что, если хотя бы одно сравнение будет равное, тернарный поиск будет эффективнее.

[_delphin_]

Пока ход мыслей правильный. В зависимости от входных данных меняем метод сравнения.

[ArtyomK]

Пока ход мыслей правильный. В зависимости от входных данных меняем метод сравнения.

Ну так вопрос дня: как определить метод сравнения, не решая очень неприятную экстремальную задачу) Или как ее решить таки)

[_delphin_]

Тк надо будет реализовывать ОБА метода, то ответ на поверхности)))