Hi All total number of coins = 1+(2+2)+(3+3+3)+(4+4+4+4)+........(N+N+.....N times) = 1+(2*2)+(3*3)+4*4+.......+(N*N) = (N*(N+1)*(2N+1))/6
Please do correct me if i am wrong Regards Praveen On Thu, Feb 17, 2011 at 6:26 AM, Rel Guzman Apaza <rgap...@gmail.com> wrote: > I did it. > > #include <iostream> > #include <cmath> > using namespace std; > > int main(){ > int n,ac,k,sum; > while(cin>>n && n){ > ac=0; > k=ceil((sqrt(1+8*n)-1)/2)-1; > ac+=k*(k+1)*(2*k+1)/6; > sum=(k+1)*(k+2)/2; > ac+=(k+1)*((k+1)-(sum-n)); > cout<<n<<" "<<ac<<endl; > } > } > > 2011/2/16 nphard nphard <nphard.nph...@gmail.com> > > Let f(n) = n(n+1)/2 >> We have to find n1 and n2 such that f(n1) < N <= f(n2) and n2 = n1 + 1. >> Solution is n2. >> >> Can be done in O(1) as follows: >> >> Solve N = n(n+1)/2 for unknown n. >> Requires us to solve quadratic equation: n^2 + n - 2N = 0 >> Find positive root of the equation which could be a real number. n2 = >> ceil(n). >> >> On Wed, Feb 16, 2011 at 5:14 PM, Pedro Rezende <web...@gmail.com> wrote: >> >>> It seems to be a very easy problem, but I'm not finding an *equation *that >>> solves it... could someone help me with the steps? >>> >>> Brief: >>> A king pays 1 gold coin to a knight on the first day. 2 gold coins for >>> the next 2 days, 3 gold coins for the next 3 days, and so on... >>> Given a day N, how much gold coins the knight must receive? >>> >>> Link: >>> http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3045 >>> >>> Thank you all! :-) >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- B. Praveen -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.