Пользователь
0,0
рейтинг
17 октября 2012 в 00:00

Разработка → Разбор задач 1 тура школы программистов HeadHunter tutorial

Прошел первый раунд отбора участников в школу программистов HeadHunter, анонс на хабре
Где после заполнения анкеты предлагалось решить 5 задачек

В анкете просили заполнить следующие поля:
  • ФИО
  • дату рождения
  • электронную почту
  • город
  • ВУЗ
  • факультет
  • год окончания
  • специальность
  • тему последней курсовой или диплома
  • какие из прослушанных предметов больше всего вам понравились
  • место работы и должность для работающих
  • на каких языках программируете
  • описать опыт разработки
  • участие в олимпиадах и сертификаты
  • почему Вас заинтересовала программа, ожидания от участия


Задача 1


Условие

Для скольки n и k, при условии 1<=n<132, 1<=k<n число сочетаний C(n,k)>1000000?
Полный принтскрин задания


Думаем

Над чем тут думать? 132 это очень мало, подойдет полный перебор, реализуем его на Питоне.
Реализацию числа сочетаний возьмем из пакета SciPy — во многих смыслах это опен-сорс Matlab
Решаем

from scipy.misc import * # отсюда возьмем число сочетаний
total = 0
for n in range(1,133):
	for k in range(1,n):
		if comb(n,k)>1000000:
			total=total+1
print "Answer: ",total

Запустим, замеряя время выполнения:
#:~/hh$ time python 1.py 
Answer:  7579

real	0m0.530s
user	0m0.504s
sys	0m0.020s
#:~/hh$ 

Нашли ошибку?
ограничения из условия в программу перенесены неправильно


Задача 2:


Условие

В мешке находится 1 красный и 1 синий диск. Во время игры игрок за ход берет случайный диск из мешка, его цвет записывают. После каждого хода взятый диск возвращают в мешок и добавляют туда еще один красный диск.
Игрок платит 1 евро за игру и выигрывает, если в конце игры он достал больше синих дисков, чем красных. Если игра длится 4 хода, вероятность выигрыша равна 11/120, таким образом, максимальный приз, который ведущий игры может назначить за выигрыш в этой игре составляет 10 евро, иначе он начнет нести убытки.
Обратите внимание, что это целое число и оно включает в себя первоначальную оплату участия, таким образом, игрок реально выигрывает 9 евро.
Найдите максимальную целую сумму приза, не делающую игру невыгодной ведущему в игре из 30 ходов?
То же задание принтскрином


Понимаем условие

В процессе игры количество красных шаров увеличивается, значит падает вероятность достать единственный синий. Чтобы выиграть, нужно достать больше половины синих. За первый раз угадать синий вероятность 1/2 за второй раз 1/3, за n-ный раз вероятность достать синий равна 1/(n+1).
Разбираем пример из условия

Если длительность игры равна 4 ходам, получаются вероятности 1/2, 1/3, 1/4, 1/5. Чтобы выиграть, можно ошибиться только 1 раз. Причем в какой из попыток мы ошиблись неважно. Посчитаем, какова вероятность успеха: 1/60+1/40+1/30+1/24+1/120=15/120
Думаем

Факториал 30 число маленькое, опять используем полный перебор. Генератор числа сочетаний возьмем из встроенного в питон пакета itertools
Решаем

import itertools
game=30
comb=[]
resb=1
for t in range(2,game+2):
        comb.append(t)
        resb=resb*t # считаем знаменатель дроби
print comb
resa=0
for q in range(game/2+1,game+1): # вытащить нужно больше половины синих
        print q,resa,resb # промежуточные результаты
        for t in itertools.combinations(comb,q): # перебираем все комбинации
                ca=1
                cb=1          
                for x in t:
                        cb=cb*x
                tdiv=resb/cb
                resa=resa+tdiv*ca          
print game/2+1
print resa,resb # числитель и знаменатель дроби результирующей вероятности выиграть


#:~/hh/article$ time python 2.p
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
16 0 8222838654177922817725562880000000
17 6014558687904548121004575 8222838654177922817725562880000000
18 6363613319405364461146200 8222838654177922817725562880000000
19 6381128687025974988156255 8222838654177922817725562880000000
20 6381886877953385972148180 8222838654177922817725562880000000
21 6381915085555093961253855 8222838654177922817725562880000000
22 6381915982709887260743580 8222838654177922817725562880000000
23 6381916006925362413306495 8222838654177922817725562880000000
24 6381916007474554489499970 8222838654177922817725562880000000
25 6381916007484879987901695 8222838654177922817725562880000000
26 6381916007485037971122090 8222838654177922817725562880000000
27 6381916007485039887292479 8222838654177922817725562880000000
28 6381916007485039905011334 8222838654177922817725562880000000
29 6381916007485039905128639 8222838654177922817725562880000000
30 6381916007485039905129134 8222838654177922817725562880000000
16
6381916007485039905129135 8222838654177922817725562880000000

real	23m2.424s
user	23m0.238s
sys	0m0.168s
#:~/hh/article$

Пока считает 23 минуты решаем другие задачи.
дробь нужно перевести в максимальный выигрыш — делим знаменатель на числитель, получаем размер выигрыша «самоокупаемости».
#:~/hh/article$ bc -l
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'. 
8222838654177922817725562880000000/6381916007485039905129135
1288459240.85082818135254719839
^C
(interrupt) use quit to exit.
#:~/hh/article$ 

Нам нужен максимальный предудыщий, в ответ записываем целую часть, т.е. 1288459240
Нашли ошибку?
Здесь мы считали не те вероятности. При подсчете нужно не только выбирать синий из многих красных, но и выбирать один красный из многих. Поэтому меняем программу:
from datetime import datetime
import itertools
game=30
comb=[]
resb=1
for t in range(2,game+2):
        comb.append(t)
        resb=resb*t
print comb
resa=0
st=datetime.now()
for q in range(0,game/2): # для выигрыша нужно вытаскивать красных шаров меньше половины
    ct=datetime.now()
    
    print q, ct-st
    st=ct
        for t in itertools.combinations(comb,q): # все варианты вытаскивания q красных шаров в разных раундах
        ta=1
        for x in t:
            ta=ta*(x-1) #вытаскивая синий мы не меняем числитель (домнажаем на 1) а красных много - на один меньше числа шаров в текущем ходе, которое записано в списке последовательностей, сгенерированных itertools.combinations и вытаскиваемом поштучно в переменной x
        resa=resa+ta
print resa,resb

ответ получается через 15 минут после запуска


Задача 3:


Если в числе все цифры не меньше стоящих слева от них, оно называется увеличивающимся. Пример — 133456. Соответственно, если числа не меньше стоящих справа, оно называется убывающим. Пример: 66420.
Числа, которые не являются ни возрастающими, ни убывающими мы будем называть прыгающими.
Сколько существует пыргающих чисел, меньше 10^75?
Принтскрин задания


Думаем:

Полный перебор долго, а индукция применяется отлично (динамическое программирование)
Действительно, к любому увеличивающемуся числу слева можно приписать от 1 до первой цифры числа включительно, а к любому убывающему справа можно приписать от нуля до последней цифры числа включительно.
Решаем:


# объявляем словари индукции
a={} # храним увеличивающиеся
b={} # для убывающих
for t in range(0,11):
	a[1,t]=1 # Первый ключ - длина числа, второй ключ - левая(правая) цифра. Значение - количество таких чисел
	b[1,t]=1
def snext(tail):
	global a,b
	tvar=0
	btvar=0
	for d in range(0,11): # объявляем для чисел новой длины
		a[tail,d]=0
		b[tail,d]=0
	for d in range(1,10): # приписываем слева цифры
		var=0
		bvar=0
		t=a[tail-1,d]
		tb=b[tail-1,d]
		for q in range(1,d+1):
			var=var+t
			a[tail,q]=a[tail,q]+t#var
		tvar=tvar+var
	for d in range(0,10): # приписываем справа цифры
		bvar=0
		tb=b[tail-1,d]
                for q in range(d,10):
                        bvar=bvar+tb
                        b[tail,q]=b[tail,q]+tb
		btvar=btvar+bvar	
	btvar=btvar-1
	print tail,tvar,btvar
	return [tvar,btvar]	
start=0
for q in range(2,76):
	[pa,pb]=snext(q)
	start=start-pa-pb-9 # т.к. числа состаящие из одних единиц, двоек, ...., девяток учитываем дважды - вычитаем лишние 9
start=start-10 # вычитаем лишние однозначные числа
print "10^75", start

Длинный вывод программы
#:~/hh/article$ time python 3.py 
2 45 54
3 165 219
4 495 714
5 1287 2001
6 3003 5004
7 6435 11439
8 12870 24309
9 24310 48619
10 43758 92377
11 75582 167959
12 125970 293929
13 203490 497419
14 319770 817189
15 490314 1307503
16 735471 2042974
17 1081575 3124549
18 1562275 4686824
19 2220075 6906899
20 3108105 10015004
21 4292145 14307149
22 5852925 20160074
23 7888725 28048799
24 10518300 38567099
25 13884156 52451255
26 18156204 70607459
27 23535820 94143279
28 30260340 124403619
29 38608020 163011639
30 48903492 211915131
31 61523748 273438879
32 76904685 350343564
33 95548245 445891809
34 118030185 563921994
35 145008513 708930507
36 177232627 886163134
37 215553195 1101716329
38 260932815 1362649144
39 314457495 1677106639
40 377348994 2054455633
41 450978066 2505433699
42 536878650 3042312349
43 636763050 3679075399
44 752538150 4431613549
45 886322710 5317936259
46 1040465790 6358402049
47 1217566350 7575968399
48 1420494075 8996462474
49 1652411475 10648873949
50 1916797311 12565671260
51 2217471399 14783142659
52 2558620845 17341763504
53 2944827765 20286591269
54 3381098545 23667689814
55 3872894697 27540584511
56 4426165368 31966749879
57 5047381560 37014131439
58 5743572120 42757703559
59 6522361560 49280065119
60 7392009768 56672074887
61 8361453672 65033528559
62 9440350920 74473879479
63 10639125640 85113005119
64 11969016345 97082021464
65 13442126049 110524147513
66 15071474661 125595622174
67 16871053725 142466675899
68 18855883575 161322559474
69 21042072975 182364632449
70 23446881315 205811513764
71 26088783435 231900297199
72 28987537150 260887834349
73 32164253550 293052087899
74 35641470150 328693558049
75 39443226966 368136785015
10^75 -3497299458233

real	0m0.070s
user	0m0.044s
sys	0m0.020s
#:~/hh/article$ 


Нашли ошибку?
Решим аналитически:
Найдем число возрастающих чисел, число убывающих и вычтем количество зеркальных чисел.

Число возрастающих чисел ищется из соображений:
если дано несколько цифр из множества {0,1,2,3,4,5,6,7,8,9} их можно расставить в порядке возрастания. Получаем урновую схему выборки с возвращением и без учета порядка

С убывающими автоматически расставить не получится — нули пойдут всегда в конец числа, а могут быть и вначале. Значит будем выбирать из цифр {1,2,3,4,5,6,7,8,9} а нули расставлять дополнительно на пустые места. Пустые места могут быть только перед или после всех цифр, иначе получается прыгающее число. N нулей мы можем расставить N+1 способом
import sys
from scipy.misc import *
game = int(sys.argv[1])# 75

def czero(game,fill):

	sort=long(round(comb(fill+8,fill),0)) # выборка fill чисел от 1 до 9
	return sort*(game-fill+1)                  # распределение нулей увеличивает количество комбинаций
def nzero(game):
	return long(round(comb(game+9,game),0)) # выборка цифр от 0 до 9
zans=0
nans=nzero(game)
for fill in range(1,game+1):
	zans=zans+czero(game,fill)	
zans=zans+1
print nans, zans
ans=nans+zans-(game-1)*9-10
print 10**game-ans



Задача 4:


Найдите номер такого члена последовательности Фиббоначи, что число цифр в нем равно 1369
Полный принтскрин задания


Думаем:

Будем считать числа Фиббоначи, переводить в строковое представление и смотреть на длину.
Решаем:

mlen=1369
a1=1
a2=1
ct=2
while len(str(a1+a2))<mlen:
	a3=a1+a2
	a1=a2
	a2=a3
	ct=ct+1
ct=ct+1
print a3,len(str(a3)),ct

#:~/hh$ time python 4.py
780900524347766560369409601397283583731565781613263766310753171005772816606447127796238704640229315255837674837377848165134157698160368949544530968794502543368882016531029514678028439260706408177729197487662072465572674876642154084378757480925617839826591149409430192878644658489021494500819466317586441937981822347486163565795152808072012368235080216554272512192800729666417669829763531411213108494418913118518602993302492226514346776633151914463050060224509695982703686755416142840706010623006936874524452187722869551681108749361294810695099504076646550576016809634068421557376832617580999236289371413151899566524614973575753248715742472176747459972608155732634727630330527033718278452846765174770728172912921167441008174546335351766020470707921356776862494695433732667044761786181261729619777198918422157071750747357444434612359278543575242617905368425489288524399123583290845306893000730480723867599367964989977241039149647013546967023147867695604450552374936008874557855435456223434642380936719467687026632615769316496835506366896848050379321482973448206502401722698140500374496142639625192381119796460488752404250147189479846363428957348179528030884277109256778540767915891043086029025915629061548978311433769206291930634863662192108026152395440631585079728836245987908191549472234398723916120832401441793104897541209034633661071095358336193091746252749026143573 1368 6548

real	0m0.183s
user	0m0.164s
sys	0m0.012s
#:~/hh$ 

Нашли ошибку?
Вроде нету :)

Задача 5:


Найдите 10 последних цифр в конечной сумме ряда, 1^1+2^2+3^3+...+1145^1145
Полный принтскрин задания


Думаем:

Число 1145 в 1145 степени действительно большое. В задании просят только последнии 10 цифр, значит воспользуемся преимуществами модульной арифметики — сразу будем считать все по модулю.
Решаем:

Для вычисления степени по модулю воспользуемся пакетом http://userpages.umbc.edu/~rcampbel/Computers/Python/numbthy.html
Качаем http://userpages.umbc.edu/~rcampbel/Computers/Python/lib/numbthy.py и кладем в папку с программой:
import numbthy as np
t=0
for i in range(1,1146):
	t=t+np.powmod(i,i,1000000000000000000000)
print t % 10000000000


#:~/hh$ time python 5.py
7110603381

real	0m0.029s
user	0m0.020s
sys	0m0.004s
#:~/hh$ 



Нашли ошибку?
Вроде нету :)


Говорят, что правильно решены 2 задачи из 5. Одну ошибку знаю, а где другие?
Дмитрий @Talismanium
карма
4,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (44)

  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Не могу понять, увы, в чем в первом примере ошибка? Неверно считаются комбинации?
      • 0
        В тексте программы написано 133 вместо 132. Лишнего вычислили.
        • +1
          Так вроде:

          >>> range(5, 10)
          [5, 6, 7, 8, 9]
          
          • 0
            По условию задачи 1<=n<132
            • 0
              Сорри, теперь понял.
  • –2
    У вас везде результаты совпадают с теми, что в условиях ответа. Значит все правильно?

    Тут конечно python не заменим. А то многие бы на длинной арифметике рухнули.

    1. Собственно первую задачу можно решить и без нее:
    Нужна функция подсчета количества перестановок, которая бы останавливала вычисления, когда уйдет за нужную границу. И нет смысла для каждого n и k. Нужно для каждого n прекращать нитрирование по к, после того как найдется k для которой количество перестановок вылезло за предел.

    2. Почему в условии 11/120, а у вас 15/120. У меня тоже 15/120 получается. Кто и где ошибся?

    5. Зачем степень по модулю 1000000000000000000000? 10^10 было бы достаточно…
    Это 30! число маленькое??!!! И опять неэффективности тонна. Можно было 2^30 вариантов рассмотреть, было бы достаточно. 2^30 все возможные варианты где он и что достал.
    Можно было даже меньше, например рекурсией с отсечением, если уже известно что проиграл.
    • –2
      Вы можете обьяснить, что именно считается здесь 1/60+1/40+1/30+1/24+1/120=15/120?

      Если следовать данной логике, мы придем вот к чему:

      Инвертируем постановку задачи и посчитаем шанс выпадения 3 или больше синих дисков.

      Вероятности выбора синего диска на каждом из 4 шагов, соответственно, 1/2 2/3 3/4 4/5

      По указанной в решении формуле считаем как бы «вероятность успеха»
      24/120 (все синие) + 6/24(без четвертого) + 8/30 (без третьего) + 12/40(без второго) + 24/60 (без первого) = (24 + 30 + 32 + 36 + 48) = 170/120 — надежная игра выходит!

      Налицо явное непонимание вероятностей.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Я бы просто оставил ссылку на описание урновых схем, а не разжевывал частный случай.
          • НЛО прилетело и опубликовало эту надпись здесь
            • –1
              круто, что вероятность >1 вас все же смутила)
              я пытался добиться от автора и комментатора, что они данным образом хотели посчитать и явно показать на примере, что подход неправильный.

              Хорошо, в следующий раз буду писать явнее <irony/>, хотя, я надеялся, в этом случае последняя строчка все же это покажет.
              • НЛО прилетело и опубликовало эту надпись здесь
                • 0
                  Да, с инвертированием не заметил. Красные надо было. Увлекся получением прекрасной оценки вероятности > 1.
      • 0
        Я брал сумму несовместных событий:
        Вероятность того, что выпадет синий на 1 первом и только на первом, вероятность что на втором и только на втором, вероятность что на третьем и только на третьем и вероятность того что не выпадет совсем. Вероятность суммы равна сумма вероятностей для несовместных событий. И того:
        1/2 * 1/3 * 1/4 * 1/5 +
        1/2 * 1/3 * 1/4 * 1/5 +
        1/2 * 2/3 * 1/4 * 1/5 +
        1/2 * 1/3 * 3/4 * 1/5 +
        1/2 * 1/3 * 1/4 * 4/5 = 1 / 120 + 1 / 120 + 2 / 120 + 3 / 120 + 4 /120 = 11 / 120.
        А то, что у меня раннее вышло 15/120 — глупые арифметические ошибки.
        Будьте уверены, непонимания теории вероятности и математической статистике у меня отсутствует.

        1 / 120 + 2 / 120 + 3 / 120 + 4 / 120 + 5 /120 у меня вышло в первый раз, не извольте судить.
        • 0
          *красный.
          • 0
            Щаз мона каменты ридактировать если чо

            Комментарии можно редактировать с октября 2012.
            • 0
              Знаю, но в 3 минуты не успеваю.
        • –2
          Если вдруг, кто-то сомневается в истинности моих слов, у меня в профиле весит статья, которая всем своим видом указывает на то, что:
          1. Я что-то понимаю в теор.вере.
          2. Люблю делать глупые ошибки и опечатки на ровном месте.
          • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Касательно полного перебора от автора поста
      Факториал 30 число маленькое, опять используем полный перебор.

      Это все равно, что играть за Pudge и не качать Meat Hook. Facepalm, одним словом.

      Можно было 2^30 вариантов рассмотреть, было бы достаточно.

      Можно и без перебора решать — при помощи динамического программирования можно найти ответ за O(N^3 * log(N)) для игры из N ходов (см. спойлер).
      Подробнее
      А именно: пронумеруем все красные шары на каждом ходу. Тогда у нас всего (N+1)! равновероятных возможных вариантов игры. Пусть d[i][j] — количество вариантов игры, при которых мы выиграем, если мы уже сделали i ходов и при этом вытянули j синих дисков. Посчитать каждый элемент d[i][j] можно за O(N * log(N)). При i = N, очевидно d[i][j] = 1 при j > N — j и 0 в противном случае. При j < N, получаем d[i][j] = d[i+1][j + 1] (мы вытянули синий диск) + (N+1) * d[i+1][j] (вытянули красный диск). Поскольку во всех числах O(N * log(N)) цифр, то каждая ячейка пересчитывается за O(N * log(N)), а всего их O(N^2).
      • 0
        про 30! маленькое число — «шутка-ловушка»

        оно же больше 2^107 и за 15 минут не справиться в одно ядро на персоналке

        у меня перебор до C(30,15)=1.5*10^8
        • 0
          Да, с 30! все персональные компьютеры мира в сумме не справятся и за год.
          На счет решения перебором до C(30,15) — я так понимаю, идет перебор расположения ходов, на которых вытянули красный диск. То есть надо еще и C(30,14), C(30,13)… C(30, 0) перебирать (что в сумме тоже имеет порядок 2^30, а именно 2^29). Потом для каждого расположения нужно посчитать частоту его возникновения, то есть для каждого хода выполнять умножение большого числа, что дает порядка 30^2 операций. Итого, будет считаться довольно долго (полагаю, около часа), но дождаться можно.
      • 0
        Вас уже приняли?
  • 0
    Интересно
  • 0
    Не вполне ясно решение задачи про числа. Здесь точно нет никакой ошибки:
        for d in range(0,11): # объявляем для чисел новой длины
            a[tail,d]=0
            b[tail,d]=0
            for d in range(1,10): # приписываем слева цифры
    
    ?
  • 0
    А еще, кажется, ошибка в конечном подсчете результата.
    start=0
    for q in range(2,76):
        [pa,pb]=snext(q)
        start=start-pa-pb-9 # т.к. числа состаящие из одних единиц, двоек, ...., девяток учитываем дважды - вычитаем лишние 9
    

    Наверное, в цикле к start стоит прибавлять 9*10^(q-1).
    и еще
    start=start-pa-pb-9 # т.к. числа состаящие из одних единиц, двоек, ...., девяток учитываем дважды - вычитаем лишние 9
    

    правильнее было бы написать
    start=start-(pa+pb-9) 
    

    так как числа состояшие из одинаковых цифр надо вычитать из количества увеличивающихся и убывающих, а не из результата
  • 0
    Что-то они зациклились на математических задачах. Могли бы и что-то пооригинальнее придумать. Вот, к примеру задачка с олимпиады для школьников: дана матрица из 0 и 1, из единиц внутри матрицы нарисованы кольца (кривые и разного размера). Нужно подсчитать, сколько таких колец.
    Пример:
    0000000000
    0100000000
    1010011000
    0100110110
    0000110100
    0000011100
    Ответ: 2.
    Ограничения для упрощения: кольца не граничат друг с другом, не пересекаются и не могут быть вложенными.
  • –1
    3-я точно неправильная.
    Даже если зафиксировать некий прыгающий префикс, допустим «121», и посчитать все варианты с ним, их куда больше будет.

    Правильное решение как-то так выглядит: pastie.org/5072192

    Очевидная динамика: d[i][j][k] — количество чисел длины i, с первой цифрой j и маской k.
    Маска тоже очевидная, у нас для прыгучести числа должны быть такие две позиции, что s[i] > s[i + 1] и s[j] < s[j + 1]. Двумя битами просто запоминаем, было ли такое.
  • +1
    Интересно, ведь эти задачки можно решить аналитически.
    Хорошо бы взглянуть на принципы и подходы к таким заданиям.
    • 0
      Разместил аналитическое решение 3 задачи
  • 0
    Все задачи на применение специфических разделов математики (комбинаторика, арифметика остатков и пр.), а не на программирование. Например, задачи, подобные последней, учат решать в 8 классе физ-мат. школ без программирования вообще.
    • 0
      Так ведь это только 1 этап из 3, простое автоматизированное тестирование.
      Или вы считаете, что знать математику даже на таком уровне программисту не нужно?
  • 0
    Ниодна из ваших задач не совпала c моими. Странно. Вы прошли во второй этап или нет?
    • 0
      На вопрос свой я нашел ответ в посте, извиняюсь.
  • 0
    Сейчас посчитал вторую задачу на руби, получил за 50 минут расчета результат:

    Вероятность — 2289739189263596147049585 / 8222838654177922817725562880000000
    Ответ — 3591168239

    Кто-нибудь еще пробовал считать?
    • 0
      Получил такой же ответ. Считал табличным методом. Работает меньше секунды.
      • 0
        Здорово, было бы любопытно взглянуть на ваше решение. Я, конечно, в лоб перебирал.
        • 0
          Как то так…
          n = 30
          
          a = [1,1]
          
          def fact(x):
          	if(x <= 2):
          		return x
          	return fact(x-1)*x
          
          for i in range(2,n+1):
          	b = [ a[0]*i ]
          	for j in range(1,i):
          		b += [ a[j-1] + a[j]*i ]
          
          	j += 1
          	b += [ a[j-1] ]
          	a = b
          
          sum = 0;
          for i in range(n/2+1,n+1):
          	sum += a[i]
          	
          print fact(n+1)/sum
          


          ПС с питоном знаком плохо
          • 0
            0! = 1
            а у вас будет 0
            • 0
              Думаю, в данном случае это не принципиально. Код — говно. Но в данном случае это и не важно, потому что он написан для того, чтобы один раз посчитать, а с этой задачей, как Вы можете убедиться, он справился.
          • 0
            Любопытный алгоритм, единственное не понял, как вам удалось заметить закономерность, что j-й элемент массива равен (j-1)-му на прошлом шаге плюс j-й на прошлом шаге умножить на n. То есть я расписал на листочке вероятности для n от 2 до 4 и убедился в этом, но вывести закономерность не так просто имхо.
            • 0
              Просто очень люблю задачи динамического программирования.

              Пусть a[i,j] — количество способов вытащить j — синих дисков на i ходу.
              Тогда a[i,j] = a[i-1,j] * j + a[i-1,j]

              То есть
              a[i-1,j] — мы взяли на прошлом ходу сколько нужно синих дисков, можем взять любой из i красных дисков (домножаем на i)
              a[i-1,j-1] — набрали на прошлом ходу меньше, чем нужно, на один и только один способ взять красный (домножаем на 1)

              Надеюсь, объяснил понятно.
  • 0
    Сколько было дано времени на решение задач?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.