Игра "Перемещение"

@devcpp · Регистрация: 04.02.2017

Студворк — интернет-сервис помощи студентам

Перемещение
Рассмотрим следующую странную игру. Есть доска размером 1×2n клеток, пронумерованных 1..2n слева направо. Изначально n фишек расположены в крайних правых позициях доски. Все другие клетки изначально свободны.
Алиса и Боб делают ходы по очереди: за один ход разрешено передвинуть любую фишку на соседнюю слева клетку, если эта клетка свободна. Игрок, который не смог сделать ход, считается проигравшим.
Сыграв не одну тысячу игр Алиса и Боб пришли к неожиданному выводу: результат игры зависит исключительно только от n. Но они не очень уверены в этом и поэтому решили экспериментально проверить свою гипотезу для некоторого n. Учитывая, что на каждую партию уходит 1 минута, Вы должны посчитать, сколько времени у Алисы и Боба займёт экспериментальная проверка их гипотезы.
Входные данные
В единственной строке задано целое число 1 ≤ n ≤ 30.
Выходные данные
Выведите одно число — время в минутах.

Лимит времени 1 секунда

Лимит использования памяти 64 MiB
Входные данные
2
Выходные данные
2

@Ромаха · 08.07.2017, 07:23

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{{n}^{2}!}{\prod_{k=0}^{2n} {k}^{n-|n-k|}}$

Теперь только засунуть в питон и сдать.
Но, если я это и сделаю, то только после сна

Байт · 08.07.2017, 11:27

Подставляю n = 2
В числителе 4! = 24
В знаменателе 0⁰(как понять?)*1¹*2⁰*3¹*4⁰
Ладно, будем считать, что первого сомножителя (k=0) нет.
Тогда получим 24/3 = 6. А в самом деле - 2

n = 3. Числитель 6! = 720
Внизу 1¹*2²*3⁰*4²*5¹*6⁰ = 320
720 / 320 - вообще не целое число (должно быть 42)

Кто-то из нас ошибается.. Не исключено, что и я. Особенно при подстановке значений в вашу формулу (с арифметикой с детства туговато). Но в ответах - вряд ли.

Но все равно интересно, как вы к этой формуле пришли...

@Ромаха · 08.07.2017, 12:59

n = 2
n^2 = 4
(n^2)! = 2*3*4

k = 2, показатель = 2-|2-2| = 2, итог 2^2 = 4
k = 3, показатель = 2-|2-3| = 1, итог 3^1 = 3
k = 4, показатель = 2-|2-4| = 0, итог 4^0 = 1

Итог.
2*3*4/3/4 = 2

Добавлено через 4 минуты
n = 3
n^2 = 9
(n^2)! = 2*3*4*5*6*7*8*9

k = 2, показатель = 3-|3-2| = 2, итог 2^2 = 4
k = 3, показатель = 3-|3-3| = 3, итог 3^3
k = 4, показатель = 3-|3-4| = 2, итог 4^2
k = 5, показатель = 3-|3-5| = 1, итог 5^1

Итог. 2*3*4*5*6*7*8*9/5 = 2*3*4*6*7*8*9
2*3*4*6*7*8*9/4^2 = 4*3*6*7*9
4*3*6*7*9/3^3 = 4*6*7
4*6*7/4 = 6*7 = 42

Байт · 08.07.2017, 13:08

Ромаха, Да, прошу прощения. Опять трудное детство виновато

Но остается вопрос

Сообщение от Байт

как вы к этой формуле пришли...

И пробовали ли вы подсчитать для бОльших значений n? Программно, конечно...
Но если вам не с руки, могу попробовать это сделать сам...

@Ромаха · 08.07.2017, 14:34

Сообщение от Байт

И пробовали ли вы подсчитать для бОльших значений n?

Неа.
Я спал..
Да и тут длинка нужна. А яву-питон-или найти свою длину - мне очень лень.
А "мой человек", которому почему-то не лень, куда-то убежал.. Вот. Ждем-с.

Сообщение от Байт

как вы к этой формуле пришли...

Когда-нибудь.. мы соберемся. И под кружечку чего-нить горячительного, я все-таки поведую Вам эту историю..

На самом деле я сначала хочу дождаться результата.

Добавлено через 54 минуты

Code
1
2
3
4
5
6
from math import factorial
n = int(input())
p = 1
for k in range(1, 2*n):
    p *= k**(n-abs(n-k))
print(factorial(n*n) // p)

сдал.

Байт · 08.07.2017, 14:37

Сообщение от Ромаха

Да и тут длинка нужна.

Для проверки формулы можно обойтись double. Я, собственно, так и сделал в своих эксперементах. В конце-концов, реализация длинки интересна зеленым новичкам, да еще в теор-числ исследованиях.

Не по теме:

Сообщение от Ромаха

Я спал.

Занятие и полезное, и облагораживающее, особенно в такую дождливую погоду:)

Новые блоги и статьи Все статьи Все блоги /
Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .	Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .
Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .	Цена ошибки DevAlt 23.08.2026 Человек я беспокойный и потому заинтересовался OCaml, в чате форсили функторы модулей как суперфичу. Пытаясь отдуплить концепт, наткнулся на тутор с простым примером. А главный принцип обучения от. . .

@devcpp 2 / 2 / 1 Регистрация: 04.02.2017 Сообщений: 31

	Игра "Перемещение" 18.05.2017, 07:11. Показов 2271. Ответов 25 Метки нет (Все метки) Перемещение Рассмотрим следующую странную игру. Есть доска размером 1×2n клеток, пронумерованных 1..2n слева направо. Изначально n фишек расположены в крайних правых позициях доски. Все другие клетки изначально свободны. Алиса и Боб делают ходы по очереди: за один ход разрешено передвинуть любую фишку на соседнюю слева клетку, если эта клетка свободна. Игрок, который не смог сделать ход, считается проигравшим. Сыграв не одну тысячу игр Алиса и Боб пришли к неожиданному выводу: результат игры зависит исключительно только от n. Но они не очень уверены в этом и поэтому решили экспериментально проверить свою гипотезу для некоторого n. Учитывая, что на каждую партию уходит 1 минута, Вы должны посчитать, сколько времени у Алисы и Боба займёт экспериментальная проверка их гипотезы. Входные данные В единственной строке задано целое число 1 ≤ n ≤ 30. Выходные данные Выведите одно число — время в минутах.  Лимит времени 1 секунда  Лимит использования памяти 64 MiB Входные данные 2 Выходные данные 2 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	08.07.2017, 07:23
	$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{{n}^{2}!}{\prod_{k=0}^{2n} {k}^{n-\|n-k\|}}$ Теперь только засунуть в питон и сдать. Но, если я это и сделаю, то только после сна 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	08.07.2017, 11:27
	Подставляю n = 2 В числителе 4! = 24 В знаменателе 0⁰(как понять?)1¹2⁰3¹4⁰ Ладно, будем считать, что первого сомножителя (k=0) нет. Тогда получим 24/3 = 6. А в самом деле - 2 n = 3. Числитель 6! = 720 Внизу 1¹2²3⁰4²5¹*6⁰ = 320 720 / 320 - вообще не целое число (должно быть 42) Кто-то из нас ошибается.. Не исключено, что и я. Особенно при подстановке значений в вашу формулу (с арифметикой с детства туговато). Но в ответах - вряд ли. Но все равно интересно, как вы к этой формуле пришли... 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	08.07.2017, 12:59
	n = 2 n^2 = 4 (n^2)! = 234 k = 2, показатель = 2-\|2-2\| = 2, итог 2^2 = 4 k = 3, показатель = 2-\|2-3\| = 1, итог 3^1 = 3 k = 4, показатель = 2-\|2-4\| = 0, итог 4^0 = 1 Итог. 234/3/4 = 2 Добавлено через 4 минуты n = 3 n^2 = 9 (n^2)! = 23456789 k = 2, показатель = 3-\|3-2\| = 2, итог 2^2 = 4 k = 3, показатель = 3-\|3-3\| = 3, итог 3^3 k = 4, показатель = 3-\|3-4\| = 2, итог 4^2 k = 5, показатель = 3-\|3-5\| = 1, итог 5^1 Итог. 23456789/5 = 2346789 2346789/4^2 = 43679 43679/3^3 = 467 467/4 = 6*7 = 42 1

Опции темы