Question is to find the number of coins received on Nth day and not the total number of coins received after N iterations.
On Wed, Feb 16, 2011 at 11:48 PM, Praveen <[email protected]> wrote: > 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 <[email protected]>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 <[email protected]> >> >> 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 <[email protected]>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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
