user1122000 - 21 days ago 6

C++ Question

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;
```

Source (Stackoverflow)

Comments