427 - FlatLand Piano Movers

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Saranga
New poster
Posts: 4
Joined: Thu Oct 16, 2003 10:25 pm

427 - FlatLand Piano Movers

Post by Saranga » Tue Nov 04, 2003 12:04 am

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.

Saranga
New poster
Posts: 4
Joined: Thu Oct 16, 2003 10:25 pm

Post by Saranga » Tue Nov 04, 2003 8:28 am

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.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 427 - FlatLand Piano Movers

Post by metaphysis » Mon Aug 01, 2016 4:41 am

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;
}

Post Reply

Return to “Volume 4 (400-499)”