QOJ.ac

QOJ

Limite de temps : 1 s Limite de mémoire : 2048 MB Points totaux : 100

#4186. 卡牌交易

Statistiques

最近,我开始玩集换式卡牌游戏《Wizardry – The Meeting》。由于我非常想组建一套强力的卡组,我决定只在网上搜索最好的卡牌。事实证明,大多数卡牌都非常昂贵,只能靠极好的运气在购买随机卡包时获得,或者通过在线拍卖竞拍得到。由于拍卖非常耗时,而我更想把时间花在玩游戏上,而不是整天盯着拍卖,于是我产生了一个新想法:建立一个交易卡牌市场。

每种卡牌都是批量生产的,因此买家并不关心他们从哪个卖家那里购买特定的卡牌。因此,我的想法是为每种卡牌创建一个网页,用户可以在上面发布买入和卖出报价。以“Green Mana”卡牌为例:如果你想买一张,你可以创建一个买入报价,例如 $10.00$。这个报价意味着你愿意以 $10.00$ 或更低的价格购买该卡牌(如果有卖家愿意以更低的价格出售)。另一方面,如果你想卖出一张“Green Mana”卡牌,你可以创建一个卖出报价,例如 $12.01$。这个报价意味着你愿意以 $12.01$ 或更高的价格出售你的卡牌(如果有买家愿意以更高的价格购买)。

现在,网站每隔几秒钟就会根据这两种报价自动计算出一个卡牌价格。然后,它只考虑那些与该价格兼容的报价(如上所述),并尽可能多地满足这些报价。

作为一名有抱负的企业家,我决定我应该从网站上发生的每一笔交易中抽取佣金。但我遇到了一个小麻烦,即如何设计一种算法来确定价格,使得成交额(即价格乘以成功交易的数量)尽可能高(这意味着我的佣金也会尽可能高)。

输入格式

输入包含: 一行一个整数 $n$ ($1 \le n \le 10^5$),表示存在报价的不同价格数量。 $n$ 行,每行包含一个实数 $p$ 和两个整数 $b$ 和 $s$ ($0 < p \le 10^4, 0 \le b, s \le 10^6$),分别表示报价的价格(精确到小数点后两位)、该价格下的买入报价数量以及该价格下的卖出报价数量。

保证输入中的每个价格至少有一个买入或卖出报价,且没有价格重复出现。

输出格式

如果不存在任何价格能促成至少一笔交易,输出 “impossible”。否则,输出能产生最高成交额的价格以及该成交额。如果存在多个这样的价格,输出其中任意一个。两个数字均需输出,且精确到小数点后两位。

样例

样例输入 1

5
12.00 0 3
11.99 2 0
11.98 5 0
10.00 1 0
12.01 0 6

样例输出 1

impossible

样例输入 2

6
2.85 14 0
4.50 0 1
5.26 3 3
6.17 1 0
14.78 0 2
21.04 1 0

样例输出 2

5.26 21.04

样例输入 3

6
2.85 14 0
4.50 0 1
5.26 2 3
14.78 0 2
1.83 0 1
21.04 1 0

样例输出 3

21.04 21.04

说明

在第二个样例中,最优卡牌价格为 $5.26$,因为它产生了 $21.04$ 的最高可能成交额,共发生了四笔交易。总共有五位买家愿意支付至少 $5.26$:三位愿意支付正好 $5.26$,一位愿意支付 $6.17$,还有一位甚至愿意支付 $21.04$。另一方面,只有四位卖家愿意以 $5.26$ 的价格出售他们的卡牌:三位正好在这个价格,还有一位愿意以 $4.50$ 的价格出售。

注意,存在另一种解法:当卡牌价格为 $21.04$ 时,恰好会发生一笔交易,产生的成交额与上述最优成交额相同。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.