LINUX.ORG.RU
ФорумTalks

задачка


0

1

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

1) Определите сколько игр будет сыграно в первом раунде.

2) Организаторы стараются сократить время первого раунда. К счастью, очень большое количество игр могут быть сыграны параллельно, учитывая, что каждый игрок может учавствовать макс в одной игре на каждом этапе раунда (всего 10 игр). Подразумевается, что все игры имеют одинаковое время.


Ответ на: комментарий от seed_stil

как предмет называется?

а какая разница ?

dada ★★★★★ ()

Определите сколько игр будет сыграно в первом раунде

В первом раунде 500 игр. Т.к каждый сыграет всего с одним оппонентом.

dada ★★★★★ ()

1. 1000/2 = кол-во одновременных партий, умножить на 10 - 5000 партий в 1 раунде.
второй вопрос не понял.

Komintern ★★★★★ ()
Ответ на: комментарий от Komintern

вот я тоже не понял :) и еще непонятно к чему там лотерея и «неожиданно большое количество».

Sonsee ()

2) Организаторы стараются сократить время первого раунда. К счастью, очень большое количество игр могут быть сыграны параллельно, учитывая, что каждый игрок может учавствовать макс в одной игре на каждом этапе раунда (всего 10 игр). Подразумевается, что все игры имеют одинаковое время.

максимальное паросочетание на графе, определенным лотереей.

Граф строим так: Игроки - узлы графа, Если между игроками, которые должны между собой играть по результатам в лотереи, то между узлами ребро

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dada

Определите сколько игр будет сыграно в первом раунде

В первом раунде 500 игр. Т.к каждый сыграет всего с одним оппонентом.

Это надо еще доказать.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dikiy

максимальное паросочетание на графе, определенным лотереей.

надо только доказать (если это действительно так), что в случае с 10-ругулярным графом (а у нас именно такой получается) выполняется теорема Тутта.

Тогда существует идеальное паросочетание => 500 игр может быть сыграно.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dikiy

да это понятно, и, мол, это число покажет сколько групп параллельных игр нужно сыграть минимум.

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

Sonsee ()
Ответ на: комментарий от dikiy

у нас 1000 игроков и 10 игр на каждого, там 5000 игр получается.

ну или 10 регулярный граф с 500 точками, суммируем градусы, тоже 5000.

или как ты хотел его моделировать?

Sonsee ()
Ответ на: комментарий от Sonsee

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

оценка сверху 11*время игры. Так как раз граф 10-регулярный, то его можно с уверенностью раскрасить в 11 цветов.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dikiy

пишут, по определению vertex-chromatic number (минимальное число цветов) меньше либо равно точке с макс градусом, т.е. <= 10.

Sonsee ()
Ответ на: комментарий от Sonsee

пишут, по определению vertex-chromatic number (минимальное число цветов) меньше либо равно точке с макс градусом, т.е. <= 10.

вот тебе контрпример - K₄ (полный граф о четырех вершинах), раз не веришь :)

У каждой точки градус 3, но хроматическое число этого графа очевидно 4.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от Sonsee

да это понятно, и, мол, это число покажет сколько групп параллельных игр нужно сыграть минимум.

но вообще я бы через паросочетание на 10-регулярном графе попробовал.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dikiy

я дико извиняюсь, ест-но:

χ( G ) ≤ ∆( G ) + 1.

блин, бошка уже не работает..

Sonsee ()

округли количество игроков до 1024 и реши уже задачку устно :(

arsi ★★★★★ ()
Ответ на: комментарий от dikiy

перепутал я :)

мы же считаем игры (т.е. соединения), а не игроков, поэтому ищем edge-chromatic число, а оно 10. Его можно же представить как bipartite граф, а в нем это число всегда равно макс градусу.

Sonsee ()

пределите сколько игр будет сыграно в первом раунде.

5000. Потому, что каждый сыграет 10 игр, но каждая игра содержит двух участников.

Организаторы стараются сократить время первого раунда.

Зря стараются. Время первого раунда определяется по времени самого медленного игрока, но поскольку количество и время игра одинаково, а надо сыграть 10 партий последовательно, время составит - 10(игр) * время_одной_игры.

Время в этой задаче не оптимизируется.

no-dashi ★★★★★ ()

1) Определите сколько игр будет сыграно в первом раунде.

СКОЛЬКО ДОСОК СТОЛЬКО И ИГР

vada ★★★★★ ()

Не знаю, как там в теории графов, но любой шахматный судья 1000 человек по швейцарке разрулит с завязанными глазами, так что 500 игр в каждом туре :D

redgremlin ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.