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

@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. Я, собственно, так и сделал в своих эксперементах. В конце-концов, реализация длинки интересна зеленым новичкам, да еще в теор-числ исследованиях.

Не по теме:

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

Я спал.

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

Новые блоги и статьи Все статьи Все блоги /
тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .

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

	Игра "Перемещение" 18.05.2017, 07:11. Показов 2248. Ответов 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