Parsing tasks 1 round of the school programmers HeadHunter

Passed the first round of selection of participants in the school programmers HeadHunter , the announcement on Habré

Where after filling in the questionnaire it was proposed to solve 5 problems



The questionnaire was asked to fill in the following fields:

• Full name
• date of birth
• email
• city
• University
• faculty
• year of ending
• specialty
• subject of the last course or diploma
• which of the subjects you listened to the most
• place of work and position for employees
• what languages ​​do you program
• describe development experience
• participation in competitions and certificates
• why are you interested in the program, expectations of participation

Task 1

Condition

For how many n and k, subject to 1 <= n <132, 1 <= k <n, the number of combinations C (n, k)> 1,000,000?

Think

What is there to think about? 132 is very small, brute force fits, we implement it on Python.

We take the implementation of the number of combinations from the SciPy package - in many ways this is the open source of Matlab

Decide

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 

Run, measuring the execution time:

 #:~/hh$ time python 1.py Answer: 7579 real 0m0.530s user 0m0.504s sys 0m0.020s #:~/hh$ 

Task 2:

Condition

In the bag is 1 red and 1 blue disk. During the game, the player takes a random disc from the bag for the turn, his color is recorded. After each move, the disc taken is returned to the bag and another red disc is added there.

The player pays 1 euro per game and wins if at the end of the game he has got more blue discs than red ones. If the game lasts 4 turns, the probability of winning is 11/120, so the maximum prize that the host can assign for winning in this game is 10 euros, otherwise he will start to suffer losses.

Please note that this is an integer and it includes the initial payment of participation, so the player actually wins 9 euros.

Find the maximum total amount of the prize that does not make the game unprofitable for the leader in the game of 30 moves?

We understand the condition

During the game, the number of red balls increases, it means that the probability of getting a single blue falls. To win, you need to get more than half of the blue. For the first time, guess the blue probability 1/2 for the second time 1/3, for the n-th time, the probability to reach blue is 1 / (n + 1).

Parse an example from the condition

If the duration of the game is 4 moves, the probabilities are 1/2, 1/3, 1/4, 1/5. To win, you can make a mistake only 1 time. And in which of the attempts we made a mistake it does not matter. Let's calculate what the probability of success is: 1/60 + 1/40 + 1/30 + 1/24 + 1/120 = 15/120

Think

The factorial 30 is a small number, again using complete brute force. We take the generator of the number of combinations from the itertools package built into the python .

Decide

 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$ 

While counting 23 minutes, we solve other problems.

the fraction needs to be transferred to the maximum winnings - we divide the denominator by the numerator, we get the winnings of “self-sufficiency”.

 #:~/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$ 

We need a maximal prediction, in response we write the whole part, i.e. 1288459240

Task 3:

If the number of all the numbers not less than the left of them, it is called increasing. Example - 133456. Accordingly, if the numbers are not less than those on the right, it is called decreasing. Example: 66420.

Numbers that are neither increasing nor decreasing will be called jumping.

How many pyrgus numbers are there are less than 10 ^ 75?

We think:

Brute force is long, and induction is applied perfectly (dynamic programming)

Indeed, any increasing number on the left can be assigned from 1 to the first digit of the number, inclusive, and to any decreasing number on the right, it can be assigned from zero to the last digit of the number, inclusive.

We solve:

 #    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 

Task 4:

Find the number of such a member of the Fibonacci sequence, that the number of digits in it is 1369

We think:

We count Fibonacci numbers, translate into a string representation, and look at the length.

We solve:

 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 1368 6548 real 0m0.183s user 0m0.164s sys 0m0.012s #:~/hh$ 

Task 5:

Find the last 10 digits in the final sum of the series, 1 ^ 1 + 2 ^ 2 + 3 ^ 3 + ... + 1145 ^ 1145

We think:

The number 1145 to 1145 degrees is really big. The task is asked only the last 10 digits, then we take advantage of the modular arithmetic - we will immediately assume everything in the module.

We solve:

To calculate the degree modulo we use the package http://userpages.umbc.edu/~campbel/Computers/Python/numbthy.html

Download http://userpages.umbc.edu/~rcampbel/Computers/Python/lib/numbthy.py and put it in the program folder:

 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$ 

They say that 2 tasks out of 5 have been solved correctly. I know one mistake, and where are the others?