10167  Birthday Cake
Moderator: Board moderators
10167  Birthday Cake
 Note: the coordinate of a cherry (x , y) are two integers. You must give the line as form two integers A,B(stands for Ax+By=0) each number mustn't in [500,500].
What does that mean by "mustn't in[500,500]", while the sample output is 0,1??
What does that mean by "mustn't in[500,500]", while the sample output is 0,1??
10167 Birthday Cake
I got WA..
any one have good test case for this question?
any one have good test case for this question?
Well I've tried the random approach as follows:
while(true){
randomly generate A, B. That is O(1)
divide the points in two sets where each set lies in one side of the line Ax+BY=0. That is O(n)
if both sets has the same size break
}
However the soltion also times out! do you make any further enhancements?
while(true){
randomly generate A, B. That is O(1)
divide the points in two sets where each set lies in one side of the line Ax+BY=0. That is O(n)
if both sets has the same size break
}
However the soltion also times out! do you make any further enhancements?
Got AC using your random approach (I had a bug in intializing an array ).
I still can't imagine that a problem setter intended such a solution for the problem
Funny thing I got AC using my wrong condition, I think there wasn't a testcase for that!Btw, that "if both sets same size, break" part is wrong, should be "if both sets are of size n, break". Just check that you really break.
I still can't imagine that a problem setter intended such a solution for the problem
Re: 10167  Birthday Cake
I solved this using a Divideandconquer approach. I got the idea from problem 10077  The SternBrocot number system. However, a brute force algorithm will also run on time.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
Re: 10167  Birthday Cake
why is randomized faster than linear iteration?
Re: 10167  Birthday Cake
Here is my code that uses the random method, but it is slow and cann't get an AC.
Needs some help.
Thanks.
Needs some help.
Thanks.
Code: Select all
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int N;
struct Point
{
int x,y;
};
Point p[100];
void Process()
{
int A,B;
srand ( time(NULL) );
while (true)
{
A = rand()*1000/RAND_MAX500;
B = rand()*500/RAND_MAX;
//cout<<A<<' '<<B<<endl;
int count1 = 0;
int count2 = 0;
for (int i=0;i<2*N;i++)
{
if (A*p[i].x+B*p[i].y>0)
{
count1++;
}
// else if(A*p[i].x+B*p[i].y<0)
// {
// count2 ++;
// }
}
if (count1*2==N)
{
break;
}
}
cout<<A<<' '<<B<<endl;
}
int main()
{
cin>>N;
while (N)
{
for (int i=0;i<N*2;i++)
{
cin>>p[i].x>>p[i].y;
}
Process();
cin>>N;
}
return 0;
}

 New poster
 Posts: 9
 Joined: Sat Jul 18, 2009 1:18 am
Re: 10167  Birthday Cake
JINX, I used the same ideia than you and got AC. I'm not sure if your way to generate the random numbers is correct. I think a more easy way is:
And I think that the break condition should be:
I hope it helps. Sorry for my english.
Code: Select all
a=500+(rand()%1001);
b=500+(rand()%1001);
Code: Select all
if(count1==n && count2==n)
break;