Page 1 of 1
427 - FlatLand Piano Movers
Posted: Tue Nov 04, 2003 12:04 am
by Saranga
I used trigonometry and derivative to calculate the maximum excursion of the piano into the corridor and if this value is less than the width it prints "Y", otherwise "N". In the test cases of course it works, and in drawings I have made it seems to work also. I have tried moving to next test case immediately on "N" or continuing, and both WA.
Any sample inputs or reasons why my program is getting WA? I can find no problem with it.
Posted: Tue Nov 04, 2003 8:28 am
by Saranga
Ah I had bad math. There is no way to take the derivative and get a simple formula. I got accepted by iterating thorugh angles and checking them.
Re: 427 - FlatLand Piano Movers
Posted: Mon Aug 01, 2016 4:41 am
by metaphysis
Use ternary search. The code below is test data generator.
Code: Select all
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main(int argc, char *argv[])
{
srand(time(NULL));
for (int c = 1; c <= 100; c++)
{
int l = rand() % 1000;
int w = rand() % 1000;
if (l < w) swap(l, w);
if (l == w) l += 25;
cout << l << ',' << w;
for (int i = 1; i <= 20; i++)
{
cout << ' ';
int corner = w + rand() % 1000 + 1;
cout << corner << ',';
corner = w + rand() % 1000 + 1;
cout << corner;
}
cout << '\n';
}
return 0;
}