@FaTaLcheG

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

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

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

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

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

я вроде разобрался как вычислять количество игр на основе количества команд, но не могу понять как сделать обратное, вычислить количество команд на основе количества игр
  • Вопрос задан
  • 272 просмотра
Решения вопроса 2
Lynn
@Lynn
nginx, js, css
Пусть у вас количество команд равно p * 2k, где p — нечётное.
Тогда всего игр будет p*(2k - 1) + p*(p - 1)/2 и это равно n — входному параметру.
Вам нужно найти такие p и k что бы выполнялось это равенство.

Из формулы видно, что n должен делиться на p, так что просто перебираем все делители n, вычисляем k и проверяем что k получается целым числом.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Однозначного решения тут нет, одно и то же количество игр может быть при различном количестве команд.
Например, 3 и 4 команды дадут по 3 игры, 18 и 40 команд - по 45 игр.
Количество команд можно представить как k = 2xy, где x - целое неотрицательное число, y - нечётное положительное число.
Тогда количество игр будет n = (2x - 1)y + (y - 1)y/2 = 2xy - 3y/2 + y2/2
Отсюда можно получить
2x+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
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы