2 shunfurh shunfurh 于 2017.09.08 00:56 提问

Skyscraper Floors

What a great idea it is to build skyscrapers! Using not too large area of land, which is very expensive in many cities today, the skyscrapers offer an extremely large utility area for flats or offices. The only disadvantage is that it takes too long to get to the upper floors. Of course these skyscrapers have to be equiped not only with a stairway but also with several elevators. But even using ordinary elevators is very slow. Just imagine you want to get from the very top floor to the base floor and many other people on other floors want the same. As a result the elevator stops on almost every floor and since its capacity is limited and the elevator is already full from the upper floors, most stops are useless and just cause a delay. If there are more elevators in the skyscrapers, this problem is a little bit eliminated but still not completely. Most people just press all the buttons of all the elevators and then take the first one so that all elevators will stop on the floor anyway.
However, the solution exists as we shall see. The Antique Comedians of Midilesia headquarters reside in a skyscraper with a very special elevator system. The elevators do not stop on every floor but only on every X-th floor. Moreover each elevator can go just to a certain floor Y (called starting floor) and cannot go any lower. There is one high-capacity elevator which can stop on every elevator's starting floor.

The ACM has a big problem. The headquarters should be moved to another office this week, possibly on a different floor. Unfortunately, the high-capacity elevator is out of order right now so it is not always possible to go to the base floor. One piece of furniture cannot be moved using the stairway because it is too large to pass through the stairway door. You are to write a program that decides whether it is possible to move a piece of furniture from the original office to the other.


The input consists of N cases. The first line contains only one positive integer N. Then follow the cases. Each case starts with a line containing four integers F, E, A, B, where F, 1 <= F < 50000000 determines the number of floors in the skyscraper (this means that there are floors 0 to F-1), E, 0 < E < 100 is the number of elevators and A, B, 0 <= A,B < F are numbers of the two floors between which the piece of furniture should be moved. Then follow E lines. Each of them contains description of one elevator. There are exactly two integers X and Y, X > 0, Y >= 0 at each line. Y determines, that the elevator starts on the Y-th floor and X determines, that it stops on every X-th floor, eg. for X = 3, Y = 7 the elevator stops on floors 7, 10, 13, 16, etc.).


For each case, print exactly one line. If floor B is reachable from floor A not using the stairway, print the sentence 'It is possible to move the furniture.', otherwise print 'The furniture cannot be moved.'.

Sample Input

22 4 0 6
3 2
4 7
13 6
10 0
1000 2 500 777
2 0
2 1

Sample Output

It is possible to move the furniture.
The furniture cannot be moved.


caozhy   Ds   Rxr 2017.09.23 23:26
Csdn user default icon
Skyscraper(摩天楼) 绿色表示8可以出现的位置。可以观察r2c2,r2c5,r7c1,r7c5四个位置的8 可以观察,如果A不是8,则B一定是8,则D一定不是8,则C一定是8. 反过来,如果C不是8,则D一定是8,则B一定不是8,则A一定是8. 所以A和C之间必定有一个是8,所以这两个点共同作用的点都一定不是8,所以得到以下的情况。 再观察6 同理,如果A不是
POJ 1508 Skyscraper Floors 未完成
<span title="Description ">描述 一个伟大的想法是建立摩天大楼!使用不是太大的土地面积,这在当今许多城市是非常昂贵的,摩天大楼提供了一个非常大的公用事业区的公寓或办公室。唯一的缺点是,它需要太长时间才能到达较高的楼层。当然,这些摩天大楼不仅必须配备楼梯,还必须配备几部电梯。但即使使用普通电梯也很慢。想象一下,你想从顶层到底层,其他楼层的其他人也想要一样。因此,电梯
UVA 718 - Skyscraper Floors(数论)
UVA 718 - Skyscraper Floors 题目链接 题意:在一个f层高的楼上,有e个电梯,每个电梯有x,y表示y + k * x层都可以到,现在要问从a层能否到达b层(中间怎么换乘电梯不限制) 思路:对于两个电梯间能不能换乘,只要满足y[i] + xx x[i] == y[j] + yy y[j].然后移项一下,就可以用拓展欧几里得求解,进而求出x,y的通解,然后利
uva 718 - Skyscraper Floors(数论+bfs)
题目链接:uva 718 - Skyscraper Floors 题目大意:一栋大楼,有F层楼,E个电梯,现在要从A层到B层,问是否可行,每个电梯给出Xi和Yi,代表这个电梯可以到达的层数Yi+k∗Xi(k≥0) 解题思路:建图,以A,B以及电梯为节点建图,将可以到达A,B这两层的电梯与这两点建边,在将两两电梯可以达到同一层的建边,判断方法为:Yi+aXi=Yj+bXj,移项得:a
      Skyscraper ad(摩天楼广告,也有叫做擎天柱广告),也叫做Sidebar ad。       摩天楼广告的特点是一般出现在右侧,垂直位置的广告,宽度有限,但高度很高。       由于其高度的特性,并且互联网网页在高度上对比宽度上的巨大优势,使得摩天楼广告位更多;更容易做出大体积的广告,发挥的空间大,更吸引人;用户在滚屏的过程中被曝光的机会更大。   
uva 718 - Skyscraper Floors(模拟优化)
Skyscraper Floors  What a great idea it is to build skyscrapers! Using not too large area of land, which is very expensive in many cities today, the skyscrapers offer an extremely large uti
bzoj2621[Usaco2012 Mar]Cows in a Skyscraper 状压dp
。。比较基础的状压dp,可以拿来练手,有背包的性质。 设f[i]表示状态为i时的最小答案,g[i]表示状态为i是当前这个电梯剩下的最大空间。 那么我们枚举每一头牛看看超不超过当前空间,超过就不装或者新开一个电梯,最后输出满状态时的f就可以了。 具体细节看代码。#include<cstdio> #include<cstring> #include<iostream> #include<algor
Coursera Algorithms week1 Interview Questions: Egg drop
Suppose that you have an n-story building (with floors 1 through n) and plenty of eggs. An egg breaks if it is dropped from floor T or higher and does not break otherwise.
B. Which floor?
B. Which floor? time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output In a building where Polycarp lives there are equal num