编程介的小学生 2017-02-22 10:50 采纳率: 20.5%
浏览 836
已采纳

A City of Skyscrapers

Modern cities often contain densely packed skyscrapers arranged neatly on a rectangular grid of streets and avenues. Skytown is no exception. The city has grown tremendously in the past few years. New skyscrapers, ever taller than previous skyscrapers, are constantly being erected with great haste. The skyscrapers have all been constructed identically, of course with the exception that some skyscrapers are taller than others. According to city regulations, each floor of a skyscraper has some minimum and maximum capacity, c and C, respectively. At least c people are required to live on a floor to ensure that the floor is utilized to its full potential. At most C people are permitted to live on a floor to prevent overcrowding.

Because Skytown has grown so fast, the mayor wanted to boast about the city's soaring population. The only problem is that he hasn't the faintest clue how many people live in Skytown. He has put you in charge of estimating the city's population. Of course, being a programmer, you seek a programming solution and do not want to go around the entire city asking how many people live on each floor. You come up with the following simple strategy: you will record the skyline as viewed from from both the south and the west. The skyline from the south is computed as follows: for each line of skyscrapers running north-south, the highest one in that line is recorded.

Given this data, compute the minimum and maximum number of people that could be living Skytown.

Input

There are several test cases in the input. The first line of each case contains four integers, M(1 <= M <= 100,000), N(1 <= N <= 100,000), c (0 <= c <= 500), and C(c <= C <= 500), where M is the dimension of the grid in the north-south direction, N is the dimension of the grid in the east-west direction, c and C are the minimum and maximum number of people allowed per floor.

Each of the next M lines contains exactly one integer in [0, 20000]. Together, they specify the western skyline. After this, the next N lines specify the southern skyline in the same way. The input ends up with a case that M = N = 0.

Output

For each test case, output the minimum and maximum number of people that could be living in Skytown. Both numbers are guaranteed to fit in a 32-bit signed integer. If the two skylines specified in the input are consistent, that is, cannot possibly describe a possible configuration of skyscrapers, print "Impossible" on a single line.

Sample Input

5 10 10 20
2
4
6
8
10
1
2
3
4
5
6
7
8
9
10
0 0
Sample Output

Minimum: 550, maximum: 4100

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-02-28 14:35
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型