Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: Необычный турнир. Найти количество участников
СообщениеДобавлено: 04 сен 2021, 20:08 
Не в сети
Начинающий
Зарегистрирован:
04 сен 2021, 19:45
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Проводится условный турнир. Система проведения следующая:

На первом этапе команды делятся на пары и играют по одному бою на выбывание (ничья быть не может). Те команды, что остались, снова делятся на пары до тех пор, пока не останется нечетное количество команд. В этом этапе может не быть ни одного боя (если первоначальное количество команд
было нечетным).

На втором этапе, если осталось более одной команды (если осталась одна команда – она является победителем и больше боев не проводится), проводятся бои между всеми возможными парами команд и по их результатам определяют победителя.

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

Входные данные
В единственной строке записано целое число (1 ≤ N ≤ [math]10^{18}[/math]), количество боев, которое следует провести.

Выходные данные
Вывести все возможные количества команд, при которых будет проведено ровно N боев. Если это невозможно ни при каком количестве команд, вывести −1.

Пример

Входные данные: 3
Выходные данные: 3,4

Пример 2

Входные данные: 12
Выходные данные: 12

Примечание:

В первом примере 3 боя могут быть необходимыдля трех команд (на втором этапе три боя каждый с каждым) либо для четырех (на первом этапе два круга на выбывание – два полуфинала и финал). Во втором примере на первом этапе будет проведено 6 + 3 боя, после чего останется три команды, для которых нужно еще три боя на втором этапе.

P.S. Нужно составить легкий алгоритм для такой задачи. Понятно, как получить количество боев от количества участников, в обратную сторону неочень. Буду признателен за помощь.

Возможно ошибся разделом, первый раз тут :pardon:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Необычный турнир. Найти количество участников
СообщениеДобавлено: 04 сен 2021, 21:33 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
p0p1k0ff, зачем вам это?

p0p1k0ff писал(а):
Понятно, как получить количество боев от количества участников, в обратную сторону неочень.

Наверное, стоит начать не с "понятно как получить", а "получить" и потом уже думать что с этим делать?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Необычный турнир. Найти количество участников
СообщениеДобавлено: 04 сен 2021, 22:26 
Не в сети
Начинающий
Зарегистрирован:
04 сен 2021, 19:45
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
p0p1k0ff, зачем вам это?


Алгоритмическая задача по программированию. Такое вот условие у нее, нужно составить алгоритм

swan писал(а):
p0p1k0ff писал(а):
Понятно, как получить количество боев от количества участников, в обратную сторону неочень.

Наверное, стоит начать не с "понятно как получить", а "получить" и потом уже думать что с этим делать?


Я это сделал, давайте распишу (как получить количество боев, при известном количестве участников):

K = X + Y,
K - количество боев
X - первая часть вычисление ( рекурентная сумма, деления на 2)
Y - вторая часть вычисление ( после первого этапа получили нечетное число больше 1 )

x - число команд участников

X = [math]x\slash 2[/math] + [math]x\slash 4[/math] + ... + [math]x\slash 2^{n}[/math] - получили нечетное число больше 1 -> y

y = x - X - оставшееся нечетное количество команд-участников

Y = [math]y*(y-1)\slash 2[/math] - вычисляем количество боев по круговой системе (каждый с каждым)

X + Y - итоговое число боев.

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

Я здесь в тупике: есть число, которое состоит из суммы четной и нечетной части. Как их подобрать я не понимаю. Поэтому интересуюсь мнением людей, которые могут.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Необычный турнир. Найти количество участников
СообщениеДобавлено: 05 сен 2021, 00:49 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
p0p1k0ff писал(а):
Алгоритмическая задача по программированию


Я вижу что это задача по программированию. Вам зачем?

Представьте [math]x=2^kp[/math]. Получите значение встреч, затем обращайте

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
p0p1k0ff
 Заголовок сообщения: Re: Необычный турнир. Найти количество участников
СообщениеДобавлено: 06 сен 2021, 21:37 
Не в сети
Начинающий
Зарегистрирован:
04 сен 2021, 19:45
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
p0p1k0ff писал(а):
Алгоритмическая задача по программированию


Я вижу что это задача по программированию. Вам зачем?

Представьте [math]x=2^kp[/math]. Получите значение встреч, затем обращайте


Я нарешиваю задачи на алгоритмы, цели этого я думаю понятны :pardon: . С этим не справился, задача затянула - решил спросить здесь. Какой то материальной выгоды от выполненного решения для меня нет, если вы об этом.

С вашей помощью задача решена, поэтому Спасибо!

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 5 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Найти необычный предел

в форуме Пределы числовых последовательностей и функций, Исследования функций

korelina-e

5

257

27 дек 2015, 00:52

RoundRobin для 4 участников в матче

в форуме Дискуссионные математические проблемы

karabov

0

94

26 фев 2023, 07:31

Опрос: новая категория участников форума

в форуме Предложения, Замечания, Обратная связь

Alexdemath

52

2161

03 янв 2021, 17:40

Предлагаю аннулировать минусы от неактивных участников

в форуме Предложения, Замечания, Обратная связь

zer0

6

693

14 апр 2016, 15:33

Задачи на турнир

в форуме Задачи со школьных и студенческих олимпиад

boroda33

18

868

12 июл 2017, 15:56

Задачи на турнир

в форуме Задачи со школьных и студенческих олимпиад

boroda33

0

228

12 июл 2017, 15:18

Шахматный турнир

в форуме Задачи со школьных и студенческих олимпиад

boroda33

3

347

19 сен 2016, 16:08

Турнир по футболу

в форуме Теория вероятностей

koka0000

0

171

04 янв 2019, 09:19

Задачи на турнир

в форуме Задачи со школьных и студенческих олимпиад

boroda33

2

322

15 сен 2016, 16:30

Задача про турнир

в форуме Алгебра

kirill_medvedev

7

284

29 авг 2018, 14:14


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved