loj#P6809. 「THUPC 2022 初赛」赛程制定
「THUPC 2022 初赛」赛程制定
题目描述
Lewis 热爱打拳,因此他组建了一家拳击俱乐部,希望通过举办表演赛卖票以筹集自己训练的资金,但是,很遗憾,Lewis 人缘并不好,因此这个俱乐部只有两个成员——Lewis 和他的好基友 Valtteri,而观众们很快就厌倦了每晚都是他们两人出场的表演赛,票卖不出去了,拳击俱乐部濒临倒闭。穷则思变,Lewis 决定通过请外援的方式,尝试拯救自己的俱乐部。
通过支票攻势,Lewis 很快就请到了两个拳坛明星——Max 和 Checo,他们将作为飞行嘉宾加入 Lewis 的俱乐部。在接下来的一个赛季里,Lewis 总共会安排 场比赛,每场比赛会从现有的4个成员中选出2人比赛,对于第 场比赛,如果是 Lewis 和 Valtteri 的比赛,只能卖出 元的门票,如果是他们中一人和一个明星的比赛,能卖出 元的门票,如果是两个明星 Max 和 Checo 之间的比赛,能卖出 元的门票。观众们喜欢看明星之间的高水平比赛,而不是 Lewis 和 Valtteri 的菜鸡互啄,因此有 。除此之外,安排比赛时还有如下要求——
-
因为明星都是日理万机的,他们只同意分别在 Lewis 的俱乐部停留最多 场比赛的时间。设 Max 出席的第一场比赛是第 场,最后一场是 场,Checo 出席的第一场比赛是第 场,最后一场是 场,则需要满足 且 ;
-
Lewis 深知自己不会是两个明星的对手,他不会愿意自己被打得鼻青脸肿直接 KO,因此,他不会安排自己与两位明星的比赛(言下之意,挨打的工作就被 Lewis 偷偷安排给了自己的好基友 Valterri,让我们为可怜的工具人 Valterri 默哀);
同时,Lewis 希望最大化自己的总收入,但是,他不太聪明,因此,如果一种方案满足以下条件,他就认为此方案满足”收入最大“——
定义 (“Lewis 的最优方案”):对于一种方案,可以看作一个长度为 的序列,序列的第 和 项为第场比赛的对阵双方,如果通过修改序列的任意1个位置,都无法得到一个收入严格大于当前收入的合法方案,则称此方案为“Lewis 的最优方案”。
聪明的你很快就发现了,“Lewis 的最优方案”不一定能最大化总收入且可能不唯一。已知 Lewis 会从所有“Lewis 的最优方案”(两个方案相同,当且仅当每一天的对阵均相同,注意,Max vs Valtteri 和 Checo vs Valtteri 虽然卖出门票相当,但视为两种不同的方案)等概率随机选一个方案执行,那么,请问在 Lewis 可能最终选择的所有方案中,门票收入的中位数是多少呢?(答案保留一位小数输出)
输入格式
第 行:3个正整数 ,意义见题面;
接下来 行:每行3个正整数 表示三种情况下卖出的门票价格。
输出格式
一行一个数表示在 Lewis 最终选择的所有方案中,门票收入的中位数,保留一位小数输出。
2 1 1
1 10 100
1 2 3
12.0
3 1 3
1 2 3
5 6 12
1 5 6
14.0
数据范围与提示
数据范围: ,