UVa 10844

From Algorithmist
Jump to navigation Jump to search

10844 - Bloques[edit]

Summary[edit]

Given N blocks, partition them into groups such that no sets are empty.

Explanation[edit]

This is precisely the definition of Bell Numbers.

Implementations[edit]

BigNum is required for this problem, and a relatively robust implementation is needed using Bell's Triangle instead of simply summing up the Stirling numbers of the second kind.

Input[edit]

2
3
4
5
6
7
8
9
10
100
200
400
500
700
800
0

Output[edit]

4, 15
5, 52
6, 203
7, 877
8, 4140
9, 21147
10, 115975
100, 47585391276764833658790768841387207826363669686825611466616334637559114497892442622672724044217756306953557882560751
200, 624748477619370179475169176526172040868676631541156088557319107233592458655068693596197197036539240046478541880130367251305801992731793116433134463929399319082714196961652168013602803041772182448739785880587721883539643696750170168607678730423675712080858884633763266376601388
400, 128261995246769380878849989673162844495741812427678270882963180636242713855726064750004149360479071961503220220374412084097982998754129071964081016342180594447295234957307849053136142262187198041697706618269675106032058766508219018191041025227154405239070717974326472656790314025578873635568845645400584805973277109784704247819668645330078730089176377369486585200688259376276226326047144161664074606144962450341109176725141203709382729161373603015443782173650486386564293580745397932788174532989368164802643511683971049745644137353539657792137177577885735906140433488541186235560068405906674108348856252058415280107523359277443716405758698296515
500, 1606072601039991453743732860465507786291924546645001249221458647036609031692388742264533068377381547526083956701374955501037620644265991485823997560423919472253673154287711452243482625943425324523587807683222016163482602127637462832110631754715883059004999887672474956910305625687386159330549479316789123608152541634373822059048622685196944645607338672012856321864174391445622227559253116940246721792836722819030355122406510335693235060922934260516725520015677030684701624259205472835900194453402189046985409254748392090704758491594261624209127147911854676983943733984734941560341133801950893641167229353543298699168088163197933266361361171749567806252210577980695569672801349293276671456649407517188002835703107649119161489459759875153938295482960189635009623545528574680095812422777380790576825931823862858389709617386930741651345394229457772
700, 67359654588923573870731234774558403179609614985334301091045189635072692834019001991683598015568710686201070150816952395004875114835944136239430187385135852961808135310137054547737502838011053290502942971740164346744291242724747694577667252352518364668920511666306520638221764734616296361135066488375483426230965809856740974643955557781131499026820001071987424594157718502099085813430946035593164441925620125882731408153915046840937193903617498227500703586133732162558020737839872395868799957905306573005117357798819988925491189031990549736280494584976848113763675996225704888480954530219550176086164180582601563759324635050490320397500510859416296056217864694226527945892238038005832506767033631117728097166475817308152737685995950452393810985303668746656162107876907128906926785568210529524819717674047998058190891254855126510211943132694633701489914254862390228119194670804660013625088883682481088133386344679144361965388378962954440655147656518301102764391616149172809525091593421107810657796697371548160089325562975431962591417512431497360396053808179998103490378079654159022567991492939024479192226461424425807991789765270019679782937318729843854859278593214057297490220401281392452347977510103996636707927953600885156377655442617230729146269783414645549895
800, 2140430394861207120362456436057658762511479576747173165459296144365238493082563938697377347058508442322725376469890976591989767808426839088555251556601889213186315172127364968206675846728629314756971256016647940946441909158855951980780828290467012573966925761817853332176409457473579613294404943020556998283261399130503544529546645990992972653324721031177942404962733598635345849312627080147367006194664317222923560267182028316256253054989942945473513137625671392726991082197267250311275665868391934449663543681040098433765491475183729761383240073021920188408270172874878749045554515374597134119964824767563745784286899337516567461542907994634251710778922120765906309828456554195574273817199281123303289692270527856144387706991245123527030189092188854882869429317091872659703066201621318201579575117332106962597064398797117568290112394422878599315517850676780313498551508100558391684329823327706641524789298708346511981096823574842745939716741255534796810395199052432159757620191223326726926731244233861301873614961939703531572164645214183936862489356322141429445090674767436564669860562421585768422758469144630977874419829330220668698487786024787577756700989334562974122777197858225848350573232520372160287419677119303044308910723166728667208233239372853146293712244155783452754507208797733113716373935736796756184902296315309394445438422607226279090161449151373563699297475156798601907674220713682436429053892480847317808197228655192244412178435532679865707376477757623435408972

References[edit]

A000110 from On-Line Encyclopedia of Integer Sequences