TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2018
  • 問題
  • P2018【G2015 第一学期期末赛】何老板卖卡车
    制限 : 時間制限 : 15000 MS   メモリ制限 : 128000 KB
    問題説明

    何老板开了一家重型卡车店,店中出售n种重型卡车(每种卡车的数量无限),每种卡车都有一定的最大载重量和最大行驶速度。
      到店的客人要求购买一辆载重能力为t吨且速度为s的卡车,客人会首先选择载重能力>=t且与t最接近的车,如果有多款可选,客人会选择速度>=s且与s最接近的那款。
      今天总共来了m个顾客,每个顾客都最多买走了一辆车(有可能没有满足顾客要求的车),请打印出每个顾客购买车辆的情况。

    入力形式

    第一行,一个整数n,表示有n种车
    第二行,n个空格间隔的整数,表示1到n每种车的载重能力
    第三行,n个空格间隔的整数,表示1到n每种车的速度
    第四行,一个整数m,表示有m个顾客
    接下来m行,每行两个整数,表示顾客对载重和速度的要求

    出力形式

    M行,每行两个空格间隔的整数,表示顾客买车的情况,第一个整数表示所购买车辆的载重,第二个整数表示车辆的速度。如果没有买到车,就输出两个空格间隔的0。

    サンプル入力

    7
    67  88  91  88  99  88  67
    80  92  69  70  85  77  85
    4
    88 76
    88 100
    80 68
    65 90

    サンプル出力

    88 77
    0 0
    88 70
    0 0

    ヒント

    数据范围:
    1<=n<=500000
    1<=M<=200000
    0<=车的载重能力<=1000000000
    0<=车的最大速度<=1000000000
    样例说明:
    对于客户提出的条件65 90
    客户首先考虑载重,于是选择载重为67这种车,该车的载重是>=65且与65最接近的一个。
    接着讨论速度,客户要求的速度是>=90,而载重为67的车中,最大速度是85,不满足要求,于是客户放弃购买。