10170 - The Hotel with Infinite Rooms

[M.Z]

What is wrong with my program?
[cpp]
#include<iostream.h>
#include<math.h>
#include<stdio.h>

const double eps=1e-14;
double cal(double S,double D)
{
if(S>=D) return S;
double temp;
double k;
temp=floor(sqrt(2*D))+1;
for(k=temp;k>0;k--){
if(((2*S+k-1)*k<2*D)&&(2*D-(2*S+k)*(k+1)<eps)) return (S+k);
}
}

void main()
{
double S;
double D;
while(cin>>S>>D){
printf("%.0lf\n",cal(S,D));
}
}[/cpp]

[yatsen]

I have the fomula:
(S+n)(n-S+1)/2 >= D
And n is my answer. But I got WA. Can anyone help me?

[Yarin]

I'm not sure what's wrong with your program, it seems to work with all testdata I can throw at it. However, my solution it's much shorter, and it doesn't have a for-loop. I guess the error is some rounding problem somewhere.

[yatsen]

Can you post your solution?
Thanks!

[Shih-Chia Cheng]

Since you have found the equation and you can solve it using little mathematics. You need only one line to produce the correct answer, don't you?

Can you post your solution?
Thanks!

[yatsen]

Thank you for your hint "mathemantics".
It remind me of the mathemantics I learned in solving equation in high school.
So I use the fomula x=(-b+sqrt(b^2-4ac))/2a
I don't need for-loop for this problem.

I have got AC. Thank you again.

[ggll]

About problem #10170, I tried both binary search and direct attack as shown below. However, the binary search method got WA, while direct attack passed.

I generated > 20 million random test cases(using the limitation in the problem) and always got the same result.

Any idea what might be wrong? Anybody know the test data?

[java]
// binary search
long low = 1;
long hi = 1000000000;

while (low < hi) {
long mid = (low + hi) / 2;
long use = (S + (S + mid - 1)) * mid / 2;
if (use < D) {
low = mid + 1;
}
else
hi = mid;
}

long resA = low + S - 1;

// direct attack
double x = (Math.sqrt((2 * S - 1) * (2 * S - 1) + 8 * D) - 2 * S + 1) / 2.0;

long resB = (long)Math.ceil(x - 1e-10) + S - 1;
[/java]

[cauchy]

I had also problems with this problem.
In fact, there is a bug in the problem specification (or in tests). There is a test case where d == 0. Try assert (d>=1). For this case the answer should be s-1.

[Tanzim-Saqib]

I am a very weak analytical thinker, so that I have used neither binary search nor derived any formula. I have just used a staright forward method.. (complete brute force).

Code: Select all

i=s+1, total=s

begin_of_the_loop
	if not (total<d) break
	total = total + i;
	i = i + 1
end_of_loop
print(i-1)

Hope it helps!

[ranban282]

Does anyone have any idea or test data as to why this gives WA??

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
#include<assert.h>
#define eps 1e-8
using namespace std;

int main()
{
	int a,b;
	while(cin>>a>>b)
	{
		//assert(b>=1);
		//if(b==0)
		//{printf("%d\n",a-1);continue;}
		int residue=(a*(a-1))/2;
		int n=b+residue;
		double ans=(sqrt((double)(1+8*n))-1.0)/2.0;
		printf("%.0lf\n",ceil(ans));

	}
	return 0;
}

[ranban282]

Also, I had tried assert(b>=1).
It gave RE.
It is completely unfair to have a test case which is contrary to problem statement.

[mf]

The test cases are fine. Your program suffers from overflows.

[iit2006015]

#include<iostream>
#include<cmath>
using namespace std;
int main()
{ double s,d;
while(cin>>s>>d)
{ double t=pow((double)s,(double)2);
double q=(double)2*(double)d;
double re=t+q-s;
re=((double)4*(double)re)+(double)1;
double pe=sqrt(re);
pe=(double)pe-(double)1;
pe=(double)pe/(double)2;
//cout<<pe<<" ";
cout<<round(pe)<<" ";
}
system("pause");
}
plz help why its giving wa even after rounding off !!!!!!

[Obaida]

Why my program passed time limit!

Code: Select all

deleted after accepted

[Nishith csedu 1448]

Use long long int.