894E — Ralph and Mushrooms-mushrooms count by math
Difference between en4 and en5, changed 0 character(s)
Div2↵
[894E — Ralph and Mushrooms](http://mirror.codeforces.com/problemset/problem/894/E) ↵

as we know we can find cycle and contract to a point to make the graph become DAG↵

but tutorial dont explain about finding mushrooms in the cycle by math knowledge↵

I have read some one's code and the math is as the follow ↵

IF I HAVE MISTAKE WELLCOME TO TELL ME! THX↵

walk through the cycle me can get the max mushrooms as we could↵

because we can still pass it though we get 0 mushroom so we can get all the mushrooms↵

mushrooms decrease by 1,2,3...n↵

for the initial mushrooms w↵

i-th time you get w-i(i+1)/2↵

for every w suppose you can get mushrooms n time↵


w,w-1,w-1-2,w-1-2-3...w-(1+2..n)↵

which is w*(n+1)-[i(i+1)/2 i for 0 to n]↵

-> w(n+1)-i(i+1)(i+2)/6↵

see here https://en.wikipedia.org/wiki/Tetrahedral_number↵

and the way to find n↵

we have w already↵

to make it simple↵

consider w is one of the i(i+1)/2↵

 8*w↵

=4*i(i+1)↵

=4i^2+4i↵

8*w+1=(2i+1)^2↵

sqrt(8*w+1)-1=2i↵

[sqrt(8*w+1)-1]/2=2i/2=i↵

which is what we want,i is the max times to get mushroom↵

for any w get floor for the ans↵

c++↵

n is the max times to get mushroom↵

int n= floor((sqrt(1+8*w)-1)/2);↵

sum_mushroom=(n+1)*w — n*(n+1)*(n+2)/6;↵

i.e.↵

w=9↵

9,8,6,3,-1↵

9,9,9,9,9  (+ plus↵

0,1,3,6,10 (- minus↵

n is 4↵

9*(4+1)-(0+1+(1+2)+(1+2+3)+(1+2+3+4))↵

=9+8+6+3=26

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English JayZhan 2017-12-07 13:04:26 0 (published)
en4 English JayZhan 2017-12-07 13:01:32 20
en3 English JayZhan 2017-12-07 12:59:43 77
en2 English JayZhan 2017-12-07 12:57:43 10
en1 English JayZhan 2017-12-07 12:55:52 1407 Initial revision (saved to drafts)