娱乐 每 日 算 法 挑 战 （大嘘）【第0x17期】

[Mr.K 018]

第23期哦！话不多说，看题：

第23期 倒饮料

MrK-018和MrK-019有一天出去吃饭，点菜的时候另点了一扎饮料。这两个人都比较抠，因为是AA制结账，所以两个人都想刚好喝到一半的饮料。桌上有两个形状不同的杯子没有用过，可以拿来倒饮料。两个杯子和装饮料的扎都没有刻度，因此只能把杯子/扎倒空或者倒满。

已知两个杯子和扎的容量（整数，单位为毫升），饮料送上来的时候扎是满的。试问，如何倒饮料，才能做到均分饮料（某一个容器中存放的饮料刚好是送上来的一半）？

输入

一行三个整数a b c，分别表示扎和两个杯子的大小。

输出

若能做到，就输出一个可以均分饮料的倒饮料的序列，如下所示：

a > b
b > c

表示把饮料从扎里倒进杯子1，再从杯子1里倒进杯子2.

若不能做到，输出一行Not possible。

以上是今天的题目。另有一个我现在在考虑的问题，发出来供大家讨论：

给定一张带边权的有向图（保证边权都是正的），给定图上的某个顶点，试求一条经过这个顶点的环路，且途径边的边权的平均值最小。

附加题并不是在出之前已经想好答案或者确定有答案的，因此它可能有多项式时间的解也可能没有，请各位留意。

五月 8, 2020，由Mr.K 018修改

[Mr.K 018]

1 小时前, PhoeniXLL 说道:

先判a %2 == 0 && (a / 2) % gcd(b, c) == 0然后BFS求方案

第二个问题我现在只会非简单环，你有简单环这个限制吗

 

30 分钟前, yhz012 说道:

附加题至少有一些预处理可以做

给定有向图，那首先可以获取给定顶点的强连通部分strongly connected components，任何包含这个顶点的环必然只在这个部分里

 

说起来题目要求简单环么，如果要求的话，甚至可以根据双联通bi-connected再砍一次？

 

原则上没有

五月 8, 2020，由Mr.K 018修改

[Mr.K 018]

刚刚, yhz012 说道:

那最坏情况是在强连通部分暴搜所有环，然后判断环是否包含该顶点……

确实

其实今天本来想出一个类似的题来着，但是就卡在这里，感觉没什么好方法

[Mr.K 018]

1 分钟前, PhoeniXLL 说道:

不要求简单环就二分下答案，然后把图里每条边减掉答案再找负环

听上去不错，详细说说？

[Mr.K 018]

1 小时前, PhoeniXLL 说道:

其实这个限定过某点的限制就有些无力

的确，因为这个限制并不是我加的，而是客观要求，今天这个附加话题是某个更大话题的一部分