• Guest
HabraHabr
  • Main
  • Users

  • Development
    • Programming
    • Information Security
    • Website development
    • JavaScript
    • Game development
    • Open source
    • Developed for Android
    • Machine learning
    • Abnormal programming
    • Java
    • Python
    • Development of mobile applications
    • Analysis and design of systems
    • .NET
    • Mathematics
    • Algorithms
    • C#
    • System Programming
    • C++
    • C
    • Go
    • PHP
    • Reverse engineering
    • Assembler
    • Development under Linux
    • Big Data
    • Rust
    • Cryptography
    • Entertaining problems
    • Testing of IT systems
    • Testing Web Services
    • HTML
    • Programming microcontrollers
    • API
    • High performance
    • Developed for iOS
    • CSS
    • Industrial Programming
    • Development under Windows
    • Image processing
    • Compilers
    • FPGA
    • Professional literature
    • OpenStreetMap
    • Google Chrome
    • Data Mining
    • PostgreSQL
    • Development of robotics
    • Visualization of data
    • Angular
    • ReactJS
    • Search technologies
    • Debugging
    • Test mobile applications
    • Browsers
    • Designing and refactoring
    • IT Standards
    • Solidity
    • Node.JS
    • Git
    • LaTeX
    • SQL
    • Haskell
    • Unreal Engine
    • Unity3D
    • Development for the Internet of things
    • Functional Programming
    • Amazon Web Services
    • Google Cloud Platform
    • Development under AR and VR
    • Assembly systems
    • Version control systems
    • Kotlin
    • R
    • CAD/CAM
    • Customer Optimization
    • Development of communication systems
    • Microsoft Azure
    • Perfect code
    • Atlassian
    • Visual Studio
    • NoSQL
    • Yii
    • Mono и Moonlight
    • Parallel Programming
    • Asterisk
    • Yandex API
    • WordPress
    • Sports programming
    • Lua
    • Microsoft SQL Server
    • Payment systems
    • TypeScript
    • Scala
    • Google API
    • Development of data transmission systems
    • XML
    • Regular expressions
    • Development under Tizen
    • Swift
    • MySQL
    • Geoinformation services
    • Global Positioning Systems
    • Qt
    • Dart
    • Django
    • Development for Office 365
    • Erlang/OTP
    • GPGPU
    • Eclipse
    • Maps API
    • Testing games
    • Browser Extensions
    • 1C-Bitrix
    • Development under e-commerce
    • Xamarin
    • Xcode
    • Development under Windows Phone
    • Semantics
    • CMS
    • VueJS
    • GitHub
    • Open data
    • Sphinx
    • Ruby on Rails
    • Ruby
    • Symfony
    • Drupal
    • Messaging Systems
    • CTF
    • SaaS / S+S
    • SharePoint
    • jQuery
    • Puppet
    • Firefox
    • Elm
    • MODX
    • Billing systems
    • Graphical shells
    • Kodobred
    • MongoDB
    • SCADA
    • Hadoop
    • Gradle
    • Clojure
    • F#
    • CoffeeScript
    • Matlab
    • Phalcon
    • Development under Sailfish OS
    • Magento
    • Elixir/Phoenix
    • Microsoft Edge
    • Layout of letters
    • Development for OS X
    • Forth
    • Smalltalk
    • Julia
    • Laravel
    • WebGL
    • Meteor.JS
    • Firebird/Interbase
    • SQLite
    • D
    • Mesh-networks
    • I2P
    • Derby.js
    • Emacs
    • Development under Bada
    • Mercurial
    • UML Design
    • Objective C
    • Fortran
    • Cocoa
    • Cobol
    • Apache Flex
    • Action Script
    • Joomla
    • IIS
    • Twitter API
    • Vkontakte API
    • Facebook API
    • Microsoft Access
    • PDF
    • Prolog
    • GTK+
    • LabVIEW
    • Brainfuck
    • Cubrid
    • Canvas
    • Doctrine ORM
    • Google App Engine
    • Twisted
    • XSLT
    • TDD
    • Small Basic
    • Kohana
    • Development for Java ME
    • LiveStreet
    • MooTools
    • Adobe Flash
    • GreaseMonkey
    • INFOLUST
    • Groovy & Grails
    • Lisp
    • Delphi
    • Zend Framework
    • ExtJS / Sencha Library
    • Internet Explorer
    • CodeIgniter
    • Silverlight
    • Google Web Toolkit
    • CakePHP
    • Safari
    • Opera
    • Microformats
    • Ajax
    • VIM
  • Administration
    • System administration
    • IT Infrastructure
    • *nix
    • Network technologies
    • DevOps
    • Server Administration
    • Cloud computing
    • Configuring Linux
    • Wireless technologies
    • Virtualization
    • Hosting
    • Data storage
    • Decentralized networks
    • Database Administration
    • Data Warehousing
    • Communication standards
    • PowerShell
    • Backup
    • Cisco
    • Nginx
    • Antivirus protection
    • DNS
    • Server Optimization
    • Data recovery
    • Apache
    • Spam and antispam
    • Data Compression
    • SAN
    • IPv6
    • Fidonet
    • IPTV
    • Shells
    • Administering domain names
  • Design
    • Interfaces
    • Web design
    • Working with sound
    • Usability
    • Graphic design
    • Design Games
    • Mobile App Design
    • Working with 3D-graphics
    • Typography
    • Working with video
    • Work with vector graphics
    • Accessibility
    • Prototyping
    • CGI (graphics)
    • Computer Animation
    • Working with icons
  • Control
    • Careers in the IT industry
    • Project management
    • Development Management
    • Personnel Management
    • Product Management
    • Start-up development
    • Managing the community
    • Service Desk
    • GTD
    • IT Terminology
    • Agile
    • Business Models
    • Legislation and IT-business
    • Sales management
    • CRM-systems
    • Product localization
    • ECM / EDS
    • Freelance
    • Venture investments
    • ERP-systems
    • Help Desk Software
    • Media management
    • Patenting
    • E-commerce management
    • Creative Commons
  • Marketing
    • Conferences
    • Promotion of games
    • Internet Marketing
    • Search Engine Optimization
    • Web Analytics
    • Monetize Web services
    • Content marketing
    • Monetization of IT systems
    • Monetize mobile apps
    • Mobile App Analytics
    • Growth Hacking
    • Branding
    • Monetize Games
    • Display ads
    • Contextual advertising
    • Increase Conversion Rate
  • Sundry
    • Reading room
    • Educational process in IT
    • Research and forecasts in IT
    • Finance in IT
    • Hakatonas
    • IT emigration
    • Education abroad
    • Lumber room
    • I'm on my way

The problem with skyscraper and eggs is not Newton's binomial?

In fact, he is the most. But first things first.
 
 

Statement of the problem


 
I master the python, I solve everything on Codewars. Faced with a known problem about skyscraper and eggs. The only difference is that the original data - not 100 floors and 2 eggs, but a little more.
 
Given: N eggs, M attempts to throw them, an endless skyscraper.
 
 
Identify: the maximum floor from which you can throw an egg without breaking it. Eggs are spherical in vacuum and, if one of them did not break, falling, for example, from the 99th floor, then the rest will also withstand a drop from all floors less than one hundred.
 
 
0 <= N, M <= 20000.
 
The run time of two dozen tests is 12 seconds.
 
Triangle of Pascal , so it is officially called. Infinite table of binomial coefficients. So the answer to the problem with N eggs and M throws is the sum of the first N coefficients in the expansion of the Newton binomial of the Mth power, except for the zero one.
 
 
An arbitrary binomial coefficient can be calculated through the factorials of the line number and the coefficient number in the line: bk = m! /(N! * (M-n!)). But the most pleasant - you can consistently calculate the numbers in a row, knowing its number and zero coefficient (always one): bk[n]  = bk[n-1]* (m - n + 1) /n. At each step the numerator decreases by one, and the denominator increases. And the laconic final solution looks like this:
 
 

def height (n, m):
h, bk = ? 1 # height and zero binomial coefficient
for i in range (? n + 1):
bk = bk * m //i
h + = t
m- = 1
return h

 
33 ms. on the calculation of f (947? 10000)! This solution can also be optimized, although it works well in the specified ranges. If n lies in the second half of the triangle, then you can invert it to m-n, calculate the sum of the first n coefficients and subtract it from 2 ^ m-2. If n is close to the middle and m is odd, then the calculations can also be shortened: the sum of the first half of the line will be 2 ^ (m-1) -? the last factor in the first half can be calculated through the factorials, its number is (m-1) /? and then either continue to add coefficients, if n in the right half of the triangle, or take away, if in the left. If m is even, then you can not count half the line, but you can find the sum of the first m /2 + 1 coefficients, calculating the average through factorials and adding half of it to 2 ^ (m-1) -1. On the input data in the vicinity of 10 ^ 6 this greatly reduces the execution time.
 
 
Even after a successful decision, I began to look for someone else's research on this issue, but found only the same thing, with interviews, with only two eggs, and this is not sports. The Internet will be incomplete without my decision, I decided, and that's it.

It may be interesting

  • Comments
  • About article
  • Similar news
This publication has no comments.

weber

Author

18-09-2018, 18:30

Publication Date

Mathematics / Python

Category
  • Comments: 0
  • Views: 297
How to reduce the risk of investments
The obvious problem with using assert
The world of the Jurassic period: and
Learning the language of bushes
The clerk screwed the Canon EF 70-200
Development of the elevator movement
Write a comment
Name:*
E-Mail:


Comments
There is a very weak knowledge in people about the astrology and spiritual stuff even it was well known by everyone in ancient times and it was the secret behind their happy life. Today is the time, when we lost our faith on spiritual science and we became addict of modern science technology.

Knowledge is very important to do any ritual properly but it is very hard to find a true knowledge about tantra, vashikaran, healing etc but thanks to avijeet aacharya who is supporting people by his free article like you and spreading the knowledge to needy people.

I seen your page and it look so interesting and i am thankful to you for spreading knowledge by this portal. if someone wants to learn about different types of
powerful vashikaran mantra for boyfriend so read avijeet aacharya pages on his portal and find interesting topics and updates.
Yesterday, 23:14

trishamukharjee

Ambulances maroc est installée à Marrakech & Rabat et se déplace dans le royaume entier pour des trajets toutes distances en ambulances. Check Out: médecin a domicile Marrakech
Yesterday, 16:37

noorseo

Welcome in the Top Class Escorts in Delhi. Are you instant going on google and doing searches for Delhi Escorts? Then Your Search is now Over Here. Our Escorts in Delhi is ready to make your glorious mood for Call Girls in Delhi.
[hide]Call Girl in Delhi[/http://escortservicesinnewdelhi.launchrock.com/] | [hide]Escort Services in New Delhi[/https://telegra.ph/Call-Girls-in-Delhi-7428151367-Call-Girls-Services-in
-Mahipalpur-01-15] | [hide]Call Girls Services in Mahipalpur[/https://escortservicesinnewdelhi.mystrikingly.com/] | [hide]Sex Services in Paharganj[/http://www.geocities.ws/natashasingh76/index.html]

Yesterday, 14:24

Natasha Singh

Hi there, I found your blog via Google while searching for such kinda informative post and your post looks very interesting for me  hole in one coverage
Yesterday, 12:32

jacksonseo

Great article it is useful and some new ideas after reading this article it is useful and a lot of new things and getting a lot of writing.  https://www.dawateislami.net/about-us
Yesterday, 11:41

Global Islamic Organization

Adv
Website for web developers. New scripts, best ideas, programming tips. How to write a script for you here, we have a lot of information about various programming languages. You are a webmaster or a beginner programmer, it does not matter, useful articles will help to make your favorite business faster.

Login

Registration Forgot password