Page 2 of 2
Re: 10170 - The Hotel with Infinite Rooms
Posted: Tue Aug 05, 2008 6:16 am
by Obaida
Oh! sorry i didn't looked at it.
Acc now.
Re: 10170 - The Hotel with Infinite Rooms
Posted: Sun Oct 18, 2009 9:54 am
by 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;
}
Re: 10170 - The Hotel with Infinite Rooms
Posted: Fri Oct 30, 2009 12:33 am
by 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. . .
Re: 10170 - The Hotel with Infinite Rooms
Posted: Wed Apr 06, 2011 7:26 pm
by 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
Re: 10170 - The Hotel with Infinite Rooms
Posted: Fri Dec 16, 2011 11:06 am
by 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;
}
Re: 10170 - The Hotel with Infinite Rooms
Posted: Sat Dec 17, 2011 8:35 am
by nebulousboy
now i get it......the prob is in sqrt(n)*sqrt(n)......