718 - Skyscraper Floors

All about problems in Volume 7. 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
Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

718 - Skyscraper Floors

Post by Aleksandrs Saveljevs »

I am a little bit confused by the sentence:
Unfortunately, the high-capacity elevator is out of order right now so it is not always possible to go to the base floor.
Which of the following is correct:
1) we should forget about the high-capacity elevator since it is out of order;
2) we should forget about the high-capacity elevator since it is out of order and the other elevators cannot reach the base floor even if it is their starting floor;
3) we should not forget about the high-capacity elevator, but it cannot go to the base floor;
4) we should not forget about the high-capacity elevator and no lift can go to the base floor;
5) we should do rand() do determine if any given lift can reach floor 0 :).

Thanks!

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: 718 Skyscraper Floors

Post by CDiMa »

Aleksandrs Saveljevs wrote:I am a little bit confused by the sentence:
Unfortunately, the high-capacity elevator is out of order right now so it is not always possible to go to the base floor.
Which of the following is correct:
I didn't try to solve the problem :-? but I'm pretty sure that the sentence means :):
Aleksandrs Saveljevs wrote: 3) we should not forget about the high-capacity elevator, but it cannot go to the base floor;
Ciao!!!

Claudio

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs »

Thanks, Claudio. :)

But... any other ideas?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

It means: we should forget about the high-capacity elevator since it is out of order.
If it wouldn't be out of order, it would always be possible to move the furniture, at least if we assume that floor a and floor b can be reached by an elevator (I don't know if input contains such cases where this is not possible, but in real life it wouldn't make sense).

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs »

Thank you, Adrian. :)
Your reply made me sure my initial assumption was OK. It must have been a bug in the program. :oops:

Just out of curiosity: is it possible to get near 0.000 without the use of a 64-bit integer or using a 32-bit integer without risk (I know of a faster way than the one I used to solve the probelm, but it may require the use of a 64-bit integer)? Just "yes" or "no".

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

Hello..~
Could anybody give me some hints..?

I'd like to model the elevators to a graph but I have no idea how to make an edge between each elevator..

For example

Code: Select all

22 2 0 6
3 2
4 7
elevator A starts at 2nd floor and stops every 3rd floor
elevator B starts at 7th floor and stops every 4th floor

How can I know which floor they meet..?
My brute force approach will get TLE

Thanks..

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

Think about linear diophantine equation.

gutlak

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

718 WA

Post by pineapple »

Please help me!
Why this code can't get Accepted?
Who can give me some special cases?

Code: Select all

#include <cstdio>
#include <iostream>
#include <cmath>
#include <memory>
#define MAX 100
using namespace std;

bool mark[MAX];
bool graph[MAX][MAX];
long long elevator[MAX][2],queue[MAX];

long long GCD(long long a,long long b)
{
    if(b==0)
    {
        return a;
    }
    else
    {
        return GCD(b,a%b);
    }
}

void calculate(long long x1,long long x2,long long *i,long long *j)
{
    long long y1,y2,z1,z2,gcd;
    gcd=GCD(x1,x2);
    y1=x1/gcd;
    y2=x2/gcd;
    if((*i<0)||(*j<0))
    {
        z1=1-(*i+1)/y2;
        z2=1-(*j+1)/y1;
        if(z1<z2)
        {
            *i=*i+z2*y2;
            *j=*j+z2*y1;
        }
        else
        {
            *i=*i+z1*y2;
            *j=*j+z1*y1;
        }
    }
    if((*i>=y2)&&(*j>=y1))
    {
        z1=*i/y2;
        z2=*j/y1;
        if(z1<z2)
        {
            *i=*i-z1*y2;
            *j=*j-z1*y1;
        }
        else
        {
            *i=*i-z2*y2;
            *j=*j-z2*y1;
        }
    }
}

bool diophantine(long long z,long long x1,long long x2,long long *i,long long *j)
{
    if(z==0)
    {
        *i=0;
        *j=0;
        return true;
    }
    else if(x1==0)
    {
        if(z%x2!=0)
        {
            return false;
        }
        else
        {
            *i=0;
            *j=(-z)/x2;
            return true;
        }
    }
    else if(x2==0)
    {
        if(z%x1!=0)
        {
            return false;
        }
        else
        {
            *i=z/x1;
            *j=0;
            return true;
        }
    }
    else
    {
        if(x1<=x2)
        {
            if(diophantine(z,x1,x2%x1,i,j)==false)
            {
                return false;
            }
            else
            {
                *i=*i+(*j)*(x2/x1);
                calculate(x1,x2,i,j);
                return true;
            }
        }
        else
        {
            if(diophantine(-z,x2,x1%x2,j,i)==false)
            {
                return false;
            }
            else
            {
                *j=*j+(*i)*(x1/x2);
                calculate(x1,x2,i,j);
                return true;
            }
        }
    }
}

bool test(long long f,long long f1,long long x1,long long f2,long long x2)
{
    long long i,j;
    if(diophantine(f2-f1,x1,x2,&i,&j)==false)
    {
        return false;
    }
    if((i>=0)&&(i<f)&&(j>=0)&&(j<f))
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool divide(long long p,long long q)
{
    if(q==0)
    {
        if(p==0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else
    {
        if(p%q==0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}

int main()
{
    //freopen("718.in","r",stdin);
    //freopen("718.out","w",stdout);
    long long a,b,e,f,i,j,n,p,q,s,size;
    cin >> n;
    for(i=0;i<n;i++)
    {
        memset(mark,0,sizeof(mark));
        cin >> f >> e >> a >> b;
        for(j=0;j<e;j++)
        {
            cin >> elevator[j][1] >> elevator[j][0];
        }
        for(p=0;p<e;p++)
        {
            for(q=0;q<e;q++)
            {
                if(test(f,elevator[p][0],elevator[p][1],elevator[q][0],elevator[q][1])==true)
                {
                    graph[p][q]=true;
                }
                else
                {
                    graph[p][q]=false;
                }
            }
        }
        size=0;
        for(j=0;j<e;j++)
        {
            if((a>=elevator[j][0])&&(divide(a-elevator[j][0],elevator[j][1])==true))
            {
                mark[j]=true;
                queue[size++]=j;
            }
        }
        while(size!=0)
        {
            s=queue[--size];
            for(j=0;j<e;j++)
            {
                if((graph[s][j]==true)&&(mark[j]==false))
                {
                    mark[j]=true;
                    queue[size++]=j;
                }
            }
        }
        for(j=0;j<e;j++)
        {
            if((mark[j]==true)&&(b>=elevator[j][0])&&(divide(b-elevator[j][0],elevator[j][1])==true))
            {
                cout << "It is possible to move the furniture." << endl;
                break;
            }
        }
        if(j>=e)
        {
            cout << "The furniture cannot be moved." << endl;
        }
    }
    return 0;
}

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 718 - Skyscraper Floors

Post by serur »

Your opinion on this code is appreciated

Code: Select all

/*
 * `Scyscraper Floors'
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 0x80
#ifdef _MSC_VER
typedef __int64 i64;
#else
typedef long long i64;
#endif

i64 m,g[N][N],
	can_reach_a[N],
	can_reach_b[N];
i64 x[N],y[N],a,b,F;

i64 gcd( i64 x, i64 y ) {
	return !y ? x : gcd(y,x%y);
}

/*
 * solves the equation ``ax + by = c'',
 * a,b -- positive integers, c -- integer;
 */
int f( i64 a, i64 b, i64 c, i64 *x, i64 *y  ) {
	i64 x0,y0,k,nb;

	assert( a >= b );
	assert( a > 0 && b > 0 );

	if ( c % gcd(a,b) )
		return 0;
	
	if ( !(a % b) ) {
		*y = c/b - (a/b)*(*x = 0);
		return 1;	
	}

	k = a/b, nb = a % b;
	assert( a == k*b + nb );
	assert( 0 < nb && nb < b );

	if ( f(b,nb,c,&x0,&y0) ) {
		*x = y0, *y = x0 - k*y0;
		assert( a*(*x) + b*(*y) == c );
		return 1;
	}
	
	return 0;

}

int solvable( int i, int j ) {
	i64 alpha_i, alpha_j,
		a,b,c,d,x_i,x_j;

	if ( x[i] < x[j] )
		return solvable(j,i);

	if ( !f(x[i],x[j],y[j]-y[i],&alpha_i,&alpha_j) )
		return 0;

	x_i = x[i]/gcd(x[i],x[j]), x_j = x[j]/gcd(x[i],x[j]);

	a = -alpha_i/x_j, b = ((F-1-y[i])/x[i]-alpha_i)/x_j;
	c = alpha_j/x_i,  d = (alpha_j + (F-1-y[j])/x[j])/x_i;

	if ( b < c || d < a )
		return 0;

	return 1;

}

int main() {
	int i,j,k,ts;
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	for ( scanf("%d",&ts); ts--; ) {
		scanf("%lld %d %lld %lld",&F,&m,&a,&b);
		for ( k = 0; k < m; ++k )
			scanf("%lld %lld",x+k,y+k);
		for ( i = 0; i < m; ++i )
			for ( j = i; j < m; ++j )
				g[j][i] = g[i][j] = solvable(i,j);
		for ( i = 0; i < m; ++i )
			assert( g[i][i] );
		for ( k = 0; k < m; ++k )
			for ( i = 0; i < m; ++i )
				for ( j = 0; j < m; ++j )
					g[i][j] |= (g[i][k] && g[k][j]);
		for ( k = 0; k < m; ++k ) {
			can_reach_a[k] = a >= y[k] && !((a-y[k]) % x[k]);
			can_reach_b[k] = b >= y[k] && !((b-y[k]) % x[k]);
		}
		for ( i = 0; i < m; ++i )
			if ( can_reach_a[i] )
				for ( j = 0; j < m; ++j )
					if ( can_reach_b[j] )
						if ( g[i][j] ) {
							puts("It is possible to move the furniture.");
							goto next;
						}
		puts("The furniture cannot be moved.");
next:;
	}
	return 0;
}
(it gets WA)

Post Reply

Return to “Volume 7 (700-799)”