Как определить число на основе результата?

Question

[FaTaLcheG]

Нужно написать функцию которая принимает на вход n число игр и на выходе отдает количество команд при которых будет проведено ровно n игр

вход: n - проведенных игр
выход: n - команд которые провели ровно n - игр

игры проходят в 2 этапа:
1 - команды делятся на пары и играют на выбывание пока не останется нечетное количество команд (может быть не одной игры)
// тут просто делим на 2 пока не останется нечетное количество команд

2 - если осталось более 1 команды нужно провести игры между всеми возможными парами команд
// формула n(n - 1) / 2

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

Comments

[Alexandroppolus]

Если количество команд нечетное, то одна из команд не участвует в первом этапе?

[Lynn «Кофеман»]

Alexandroppolus, думаю просто сразу переходим ко второму этапу.

[Alexandroppolus]

Lynn «Кофеман», точно. "может быть не одной игры". Протупил.

[FaTaLcheG]

Lynn «Кофеман», верно

Answer 1

[Lynn «Кофеман»]

Пусть у вас количество команд равно p * 2^k, где p — нечётное.
Тогда всего игр будет p*(2^k - 1) + p*(p - 1)/2 и это равно n — входному параметру.
Вам нужно найти такие p и k что бы выполнялось это равенство.

Из формулы видно, что n должен делиться на p, так что просто перебираем все делители n, вычисляем k и проверяем что k получается целым числом.

Comments

[Alexandroppolus]

вычисляем k и проверяем что k получается целым числом.

можно взять 2^k - 1 = n/p - (p - 1)/2
то есть для каждого нечетного делителя n вычисляем X = n/p - (p - 1)/2,
и проверяем, что X xor (X + 1) === 0

Answer 2

[Rsa97]

Однозначного решения тут нет, одно и то же количество игр может быть при различном количестве команд.
Например, 3 и 4 команды дадут по 3 игры, 18 и 40 команд - по 45 игр.
Количество команд можно представить как k = 2^xy, где x - целое неотрицательное число, y - нечётное положительное число.
Тогда количество игр будет n = (2^x - 1)y + (y - 1)y/2 = 2^xy - 3y/2 + y²/2
Отсюда можно получить
2^x+1 = 3 - y + 2n/y
Поскольку решение нужно в целых числах, то y - один из делителей числа 2n.
Значит, перебирая делители мы должны найти такой нечётный делитель, при котором правая часть уравнения даст в результате степень двойки.
Например, n = 171
2n = 342
Нечётные делители: 1, 3, 9, 19, 57, 171
Значения правой части: 344, 114, 32, 2, -48, -166
Степени двойки: 32, 2
Соответствующие значения x: 4, 0
Количество команд: 144, 19