ACM-10784 - Time limit exceeded.

[bahador saket]

Dear All

I am going to solve this question : 10784 - Diagonal but I faced with
this message from UVa.

"
Your submission with number 8031141 for the problem 10784 - Diagonal
has failed with verdict Time limit exceeded.
Your program used more CPU time than what is allowed for this problem.
That means that your algorithm is not fast enough or that it entered
into an infinite loop."

It is my program:
Is it slowly?



#include<iostream>
using namespace std;
int main()
{
long long int a;
int j=1;
while(cin>>a)
{
int i=3;
long long int result=0;

if(a==0) break;
while(a>result)
{
result= (i*(i-3))/2;
i++;
}
cout<<"Case "<<j<<": "<<i-1<<endl;
j++;
}
}


Cheers,
Bahador Saket

[Josiah]

Did you mean while(a<result) instead of while(a>result)? I sense an
infinite loop there otherwise.

J

[bahador saket]

Dear Josiah

I think it is correct because basic Formula: Number of diagonal in i-gon is (i * (i-3) ) / 2.
so the result  is number of diagonals.
attend to this trace:                                    i is the sides / result is diagonals/ a is the input
 
  i   |  a  | result
------|-----|----------
  3  | 11 |  3                a>result
  4  | 11 |  2                a>result
  5  | 11 |  5                a>result
  6  | 11 |  9                a>result
  7  | 11 |  14              a<result  // and 7 is the correct answer


I will be happy if other can participate in this issue.


Regards,
Bahador

--
Post: fit-ca...@googlegroups.com
Unsubscribe: fit-cafeteri...@googlegroups.com
Visit: http://groups.google.com/group/fit-cafeteria?hl=en

[Josiah]

Sorry, I was just guessing and didn't exactly look at the question.

The problem with your program is that it cannot handle large inputs
(e.g. it fails when the input is 10000000000).

Check the type for your variable "i". I think the problem lies
there. :)

J.

[johnsee]

Dear bahador,

I would encourage you to direct your ACM/UVA enquiries to the MMU ACM
Interest Group instead.
http://groups.google.com/group/mmu-acm

regards,
john