#P18369. Projects
Projects
Projects
你是一家软件公司的经理。今天,公司的 名程序员需要完成 个项目。
项目 只能由程序员 和 完成。程序员 独自完成该项目需要 个时间单位;若 ,程序员 在这个项目上的工作速度只有 的一半。两人可以分工: 选择一个实数 ,满足 ,在该项目上工作 个时间单位;剩余部分由 完成,需要 个时间单位。
若 ,则该项目只能由这一人独自完成,需要 个时间单位。
同一项目的两位程序员可以独立工作:既可以同时工作,也可以在完全不同的时段工作。每名程序员在任意时刻只能处理一个项目,其总工作时间等于他在各项目上花费的时间之和。切换项目所需的时间忽略不计。所有程序员今天同时开始工作。
有些程序员赶时间,希望尽早离开。你尚不知道具体哪些人赶时间,因此需要考虑 个互相独立的情形。每个情形指定一个非空的赶时间程序员集合。
对于每个情形,求最小的实数 ,使你能够安排工作,最终完成所有项目,并使每名赶时间的程序员总工作时间都不超过 。其余程序员的工作时间没有上限。
可以证明答案一定是有理数。请将答案写成最简分数。
输入格式
第一行包含三个整数 ,分别表示程序员数、项目数和情形数。
接下来 行,每行包含三个整数 ,描述一个项目。不同项目允许具有相同的 ,也允许 。
接下来 行,每行包含一个长度为 的二进制字符串 。第 个字符为 1 表示程序员 在该情形中赶时间,为 0 表示他不赶时间。每个字符串至少包含一个 1。
输出格式
输出 行。第 行输出该情形的最小可能工作时间上限,格式为 x/y,其中 且 。答案为零时输出 0/1。
数据范围
- ;
- ;
- ;
- ;
- 。
输入只有一组数据; 个情形分别独立考虑。
样例输入 1
5 7 7
2 1 2
2 2 1
3 2 3
3 4 5
4 3 2
1 5 7
1 5 7
10000
01000
00110
11100
11111
01111
01111
样例输出 1
0/1
1/1
4/1
18/7
28/3
19/4
19/4
样例说明
第一个情形中,程序员 1 可以立即离开,其余人能够完成全部项目。
第二个情形中,程序员 2 必须独自完成第二个项目,需要 1 个时间单位。
第三个情形中,程序员 4 在第五个项目上花费 2 个时间单位,在第四个项目上花费 2 个时间单位;程序员 3 在第四个项目上花费 4 个时间单位。因此两人的总工作时间都是 4。
第四个情形中,程序员 1 和 3 分别在第一个和第三个项目上工作 个时间单位。程序员 2 在前三个项目上分别工作 个时间单位,总计也是 。
第五个情形中,为完成最后两个项目,程序员 1 和 5 中至少一人的工作时间必须达到 。存在使每个人的总工作时间都不超过 的安排。