编程介的小学生 2017-09-05 01:50 采纳率: 20.5%
浏览 750
已采纳

A Brief Gerrymander

The evil ruling party, the Liberatives, are redistributing the electoral regions (ridings) in your city, and are nefariously attempting to pack certain opposition-friendly neighborhoods into as few ridings as possible. If this plan succeeds, it will be the end of democracy as we know it! As a card-carrying member of the noble, compassionate Conservals (the main opposition party), you must foil their devious plot and safeguard the future of our country.

Under the new plan, the city will be divided up into a grid of rectangles by selecting certain major streets and avenues as boundaries. All streets and avenues stretch straight across the city, and are numbered starting from the southwest corner of the city. The city is bounded by four roads: 1st Street (west edge), 100th Street (east edge), 1st Avenue (south edge), 100th Avenue (north edge). Clearly these four roads must represent district boundaries; however, only a subset of the streets and avenues in between will divide districts. The Liberatives have already been able to fix the North-South (street) boundaries; however, they have been forced to allow the Conservals to select the East-West (avenue) boundaries.
You know the location of all the opposition-friendly neighborhoods, which vote strongly Conserval. A neighborhood is exactly one block between adjacent streets and avenues. For instance, one neighborhood might lie between 47th and 48th Street and 67th and 68th Avenue. Place the avenue boundaries so that as many ridings as possible contain at least one opposition-friendly neighborhood.

Input

Input consists of multiple cases, each describing a city. The first line will give N, the number of Conserval neighborhoods in the city; the following N lines will contain the street and avenue number of the southwest corner of each neighborhood. The next line will contain S, the number of street boundaries, and the S street numbers that they lie on, in increasing order. The final line will consist of A (at least 2), the number of avenue boundaries you must place. Input will be terminated by a line containing -1.

Output

For each case, output a single line giving A followed by A distinct avenue numbers for the optimal redistriubution, in increasing order. If there are multiple such solutions, print the lexicographically first one.

Sample Input

2
49 49
50 50
2 1 100
3
-1

Sample Output

3 1 50 100

  • 写回答

2条回答 默认 最新

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

报告相同问题?

悬赏问题

  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥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自动售货机数码管(相关搜索:数字时钟)