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.
