user1122000 user1122000 - 21 days ago 6
C++ Question

Why does this input cause time limit exceeded

I am solving the Theatre Square problem for the inputs:


1000000000 1000000000 1


I get a time exceeded limit

#include <iostream>

using namespace std;

int main()
{
signed long long int n,m,a,count_n=0,count_m=0,count;
std::cin>>n>>m>>a;

if(a>1000000000)
{
cout<<"fail"<<endl;
return 0;
}

if(n>=1)
{
while(n>a)
{
count_n++;
n=n-a;
}
if(n>0)
count_n++;
}

m=m-a;
if(m<0)
{
cout<< count_n<<endl;
return 0;
}
else
{
while(m>a)
{
count_m++;
m-=a;
}
if(m>0)
count_m++;
}

count=count_n+(count_m*count_n);
cout<<count<<endl;

return 0;
}


How can I avoid it?
Am I also supposed to read the inputs using scanf(). I've read online that it would be faster, but I am not sure if this is what's causing the problem with the large inputs.

Answer

The problem is with your loop, which for big n and small a can take considerably long time:

int count_n = 0;
//...
while(n>a)
{
    count_n++;
    n=n-a;
}

What is this loop doing? It counts how many a can you fit in n. That's division! You can express this as:

count_n = n / a;
n = n % a;
Comments