Just algorithm!
Egg Drop



ͶѴ Egg Drop

⨷ǡѺ÷ͧ¹ҡ֡ ᵡҡ鹷

input

ӹǹ鹢ͧ֡ (F)

ӹǹ (D)

ӹǹᵡ (B)



͹Ҷ֧ 3 ӵͺ

ӹǹ鹢ͧ֡ҡش (FMax)

ӹǹ·ش (DMin)

ӹǹᵡ·ش (BMin)

ͧҹ



ҡ FMax

͹ö Solve §´ Dynamic Programming

᷹ФԴҨٵͤӹǹ FMax

ҡᵡ FMax subproblem ᷹ ٵù



FMax(d, b) = 1 + FMax(d-1,b) + FMax(d-1,b-1)



1 á ¹ 1 ҡҪ鹷¹ᵡᵡ

FMax(d-1,b) ¹ᵡ ҡ仪鹺¹

d-1 ӹǹŴŧ 1 b ӹǹᵡѧ ¹ᵡ

FMax(d-1,b-1) ¹ᵡ Ҩŧҧ ¹

ǹ b-1 ӹǹᵡŴŧ 1



ҡ Dynamic Programming ҤѺ Memoization

Ҩ¡ input Ẻǫա

Ҥèкѹ֡ӵͺ աҨФӹǹա



繤 Memoize
letmemoizef=
letdict=Dictionary<_,_>()
funn->
matchdict.TryGetValue(n)with
|true,v->v
|_->letv=f(n)
dict.Add(n,v)
v

ѡ dict input (n) Ẻ return value (v) ѹ

ӹǹ (f) Ҥ dict



ǹҵ͡Ѻ FMax
letrecmaxF=
letmaxFx(d,b)=
letresult=1L+maxF(d-1,b)+maxF(d-1,b-1)
ifresult>=4294967296L
then-1L
elseresult
letcache=memoizemaxFx
function
|d,1->int64d
|d,bwhend=b->(1L<<<b)-1L
|d,b->cache(d,b)

Ըա result ͸ԺǴҹ

ҡ͸Ժ仡͹˹ҹԴ֧

⨷Ҷ result դҡҡѺ 232

return -1



жѴ cache memoize ͨӤӵͺ

÷¡ҡ cache աäӹǹ§ҹ



Ѵ ͡ä׹ͧҹ cache

觤Һҧҧ öӹǹʴ ͧҹ dynamic programming



ҡ
b = 1 ᵡͧ

10 ͧ ᵡͧ

ҡ¹ҡҧ ӹǹ鹷ҡش 10

ѧ b = 1 d = 10 ͵ͺ 10



ж d = b

ѹС binary search ѹ

ӹǹ search space ҡش Ѻä b 駤 2b - 1

öŧ (1L <<< b) - 1L



function maxF ѧըش͹

Ҩӹǹ (d) ҡҨӹǹᵡ (b) ҡ


ӹǹ 2 ѹҹ ᵡ 2

Դ recursion ͺ 2 ѹҹ ͹ҨԴ stack overflow

еԴ stack overflow search ҹ

ͧҡ⨷͡ result Թ 232 return -1



աٵ÷ҤҤ input ͧ function maxF overflow

Ըҡ brute force ¤Ѻ
letisOverflow=
letmaxDb=
letrecbruted=
matchmaxF(d,b)with
|-1L->d-1
|_->brute(d+1)
brute(b+1)
letcache=memoizemaxD
function
|d,1->false
|d,bwhenb>32->true
|d,b->d>cacheb

ҡҹ maxD ҡ d -1 ҡش

С function ѴùԴ˹ͧ¡ҡ cache

b = 1 d դҡѺ f ͸Ժ´ҹ ѧ鹨֧շҧ overflow

ж b > 32 d դҹ·ش ҡѺ b


ٵ binary search f դҡ 232



ǹҤ FMax function Ѻ
letrecsolveFdb=
ifd<bthensolveFdd
elifisOverflow(d,b)then-1L
elsemaxF(d,b)

Ҩӹǹ (d) ¡Ҩӹǹᵡ (b)

8 öᵡ 10


ᵡ 8 ӹǹöᵡա

ѧ óչ ӹǹᵡ ѹҡҨӹǹ



Ѵ Ҥ DMin


Ҩӹǹ (f) դ 2 ѹҹ

ᵡ (b)

ӹǹͧդ 2 ѹҹ

search space Ҵ binary search ö
letsolveDfb=
letrecbinarySearchlowhi=
iflow=hi
thenlow
elseletmid=(low+hi)/2
letmaxF=solveFmidb
ifmaxF=-1L||maxF>=int64f
thenbinarySearchlowmid
elsebinarySearch(mid+1)hi
binarySearch1f

Ѵ Ҥ BMin

ѹҡҹ b դԹ 32 overflow

ѧ鹤 b դ 1-32 ҹ brute force дǡش
letsolveBfd=
letrecbruteb=
letmaxF=solveFdb
ifmaxF=-1L||maxF>=int64f
thenb
elsebrute(b+1)
brute1

ش ӵͺ
letsolvefdb=
sprintf"%i%i%i"(solveFdb)(solveDfb)(solveBfd)







Create Date : 25 Ҥ 2557
Last Update : 27 Ҥ 2557 12:09:14 . 1 comments
Counter : 673 Pageviews.

 
thx u crab


: Kavanich96 ѹ: 26 Ҥ 2557 :3:54:47 .  

:
Comment :
  * code html 觢ͤ੾Ҫԡ
 
觢ͤ
س׹ѹ觢ͤ

chaowman
Location :
ا෾ Thailand

[Profile ]

ԻҢͧ Blog [?]
ҡͤѧ
Rss Feed
Smember
Դ͡ : 8 [?]









New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.