Page 1 of 1
718 - Skyscraper Floors
Posted: Wed Dec 24, 2003 4:35 am
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!
Re: 718 Skyscraper Floors
Posted: Wed Dec 24, 2003 12:23 pm
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
Posted: Tue Jan 20, 2004 2:14 pm
by Aleksandrs Saveljevs
Thanks, Claudio.
But... any other ideas?
Posted: Tue Jan 20, 2004 8:19 pm
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).
Posted: Tue Jan 20, 2004 10:07 pm
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.
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".
Posted: Thu Sep 21, 2006 2:19 pm
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
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..
Posted: Wed Sep 27, 2006 4:58 pm
by Hisoka
Think about linear diophantine equation.
gutlak
718 WA
Posted: Wed Jan 10, 2007 1:57 pm
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;
}
Re: 718 - Skyscraper Floors
Posted: Sun Aug 16, 2009 8:55 am
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)