10170 - The Hotel with Infinite Rooms

[Obaida]

Oh! sorry i didn't looked at it.
Acc now.

[landuomu]

hi I get TLE for this problem. Below is my code. For the largest possible option(1 10^15), I took 28s. How can I improve my algorithm? Thank you.

Code: Select all

#include <cstdio>
using namespace std;

int main() {
    long long s=0,d=0,day,dayleft;
    
    while (scanf("%lld %lld",&s,&d)==2) {
          day=1;
          dayleft=s;
          while (day<d) {
                dayleft--;
                if (dayleft==0) {
                   s++;
                   dayleft=s;
                }
                day++;
          }
          printf("%lld\n",s);
    }
    return 0;
}  

[Taman]

You should have a look at the earlier posts first. If all the posts fail to help you then you can ask for help. Well, the earlier discussions on this problem should be enough. If you find it is not enough then I would like to tell you that it's a problem of simple math. If you have an idea of quadratic equation it should be very simple to you. Quadratic equation will just make the code shorter(maximum 3 lines) and do what your code does but will do it more efficiently. Thnx. . .

[Shafaet_du]

Think about triangular number .
sample input:

Code: Select all

1 6
3 10
3 14
1 1000
10 1000
555 32354
10000 1000000000000000
34545 565
234234 6577
5 4
5 5
5 6
5 7

out:

Code: Select all

3
5
6
45
46
610
44721361
34545
234234
5
5
6
6
3
5
6
45
46
610
44721361
34545
234234
5
5
6
6

[nebulousboy]

why WA??
i tried many test cases and all came out correctly????then why WA???

here is my code.....

# include <math.h>
# include <stdio.h>
int main()
{
long long a,s,n,d;
while(scanf("%lld",&a)==1)
{
scanf("%lld",&s);
d=2*a-1;
d=d*d+8*s;
n=(-(2*a-1)+sqrt(d))/2;
if(d==sqrt(d)*sqrt(d))
printf("%lld\n",a+n-1);
else
printf("%lld\n",a+n);
}
return 0;
}

[nebulousboy]

now i get it......the prob is in sqrt(n)*sqrt(n)......