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.
