n разбойников ограбили караван. Уговор у них такой: голосуют за то, чтобы убить самого младшего, если «за» больше половины–убивают и продолжают голосование за следующего по возрасту(у всех возраст разный). Если не больше половины–делят поровну добычу и расходятся. Каждый разбойник, во–первых, очень не хочет умирать, а во–вторых, хочет как можно больше денег. Сколько разбойников осталось?
GD Star Rating
loading...
loading...
2^k
Надо веса расставить, тогда можно както оценить. А без этого некорректно
Корректно все там.
а младший голосует или нет?
получается, что если разбойников больше трех, то никого убивать не будут, потому что кроме двух самых старших умрут все.
Неверно.
мм.. ну тогда объясни тупому. можно в личку.
если это мыслящие разбойники, тогда да, 2^k, поддерживаю
k это что?
а какие ещё бывают? там же сказано: на первом месте тяга к жизни, на втором к богатству
вроде при решении никаких неопределённостей не возникает
что такое k?
y = 2 * (n mod 2),
где mod операция целочисленного деления.
Теперь рассказ.
Рассмотрим, кто как будет голосовать, если у него есть голова на плечах, по старшинству. Самый старший будет всегда голосовать «за». Он бы, сука, всех поубивал, но этого не допустит №2. Если они останутся вдвоём, то против себя он голосовать не будет. Остальных же он может смело валить без зазрения совести. Немного сложнее третьему на него завистливо смотрят №1 и №2, поэтому, чтобы уравновесить их, ему нужен ещё 1 голос, соответственно он будет голосовать против убийства №4. Самому №4 привалила халява он понимает, что №3 не будет против него голосовать, поэтому можно смело отправлять расход всех, кто младше. Номер 5 выживет, если будут живы №№ 6, 7 и 8. № №№10, 11, 12, 13, 14, 15, 16. И так далее.
Теперь будем в первый столбик писать, сколько у нас есть разбойников, а во второй сколько их в таком случае выживет.
1 = 1
2 = 2
3 = 2
4 = 4
5 = 4
6 = 4
7 = 4
8 = 8
9 = 8
15 = 8
16 = 16
Эмпирическим путём понимаем, что число выживших будет равно максимальному 2^k, не превышающему n.
Помогите выразить решение функцией, потому что с целочисленным делением я протупил.
int maxsqr(int n)
{
int k = 1;
int r = 1;
if(n > 1)
{
while(r = 1)
{
k++;
if(pow(2, k + 1) > n)
{
r = pow(2, k);
}
}
}
return r;
}
Вот можно мне то же самое, но математической функцией?
целая часть от логарифма n по основанию 2
точно, логарифм! А «целая часть» можно както красиво математически написать? Хочется вот решение выразить одной лаконичной функцией, чтобы увидеть и кончить в трусы.
*=floor(log2(n))
y=2^k, k=max{log2(n), n
Z | log2(n) <= k}
я кончил, спасибо.
Ответ:
угу. но через floor() симпатичнее.
Исключение:
При n = 1 * = 1.
и здесь как бы нигде не сказано, что нужно взять целую часть от логарифма.
floor не совсем математически. Второй вариант предикат, и простейшая функция. Ну да, предикат не совсем правильный. Не n Э Z, а log2(n) Э Z.
Неверно. Верно вот так:
ещё лучше использовать сдвиг вместо возведения в степень и двоичный поиск(для 64х бит неплохая экономия). это если надо много раз считать максимальную степень двойки, не меньшей данного числа, а вообще, вроде бы, есть команда процессора такая даже.
почему, надо оба предиката.
Точно. Только от log2n надо взять целую часть.
Заминусуйте комментарий с неверным ответом, пожалуйста.
Эти скобочки с загогулинками внизу и означают «взять целую часть» то же что floor, только значками. Ты же очень просил чтобы значками
спасибо, буду знать!
Логичнее было бы убивать не младших, а слабейших.
Если n = 1, то 1, во всех остальных случаях двое. Потому что по заданному алгоритму «против» голосует только тот, чьё убийство сейчас реально обсуждают, а в этом случае поровну станет только на двоих — когда один будет за то, чтобы убить, а другой по ясной причине будет против этого.
Darth вопервых, выше есть правильный ответ
вовторых, рассмотрите n=4, особенно третьего участника и его рассуждения о том, что случится на следующем ходу, если четвёртого замочат
I wish I were smarter…
Ещё есть маза что 5 старших родились в один день, и тогда все формулы идут по пизде.
4 разбойника остались, потому что 2й и первый всегда выживают, а третий может спасти свою задницу только спасая четвертого. четвертый и выше спастись, защитив следующего не могут потому что остаются в меньшинстве с ним вдвоем. Например 5 и 6 голосуя за спасение шестого против 1 2 3 и 4.