/ Vijos / 题库 /

天平

天平

时间限制:1秒  内存限制:256M


题目描述

你有 \(n\) 个砝码,均为 \(1\) 克,\(2\) 克或者 \(3\) 克。你并不清楚每个砝码的重量,但你知道其中一些砝码重量的大小关系。你把其中两个砝码 A 和 B 放在天平的左边,需要另外选出两个砝码放在天平的右边。问:有多少种选法(选法是无序的,也就是说选择砝码 \(1\) 和 \(2\) 或者 \(2\) 和 \(1\) 是一种选法)使得天平的左边重(\(c_1\))、一样重(\(c_2\))、右边重(\(c_3\))?(只有结果保证唯一确定的选法才统计在内)

输入格式

第一行包含三个正整数 \(n,A,B\)(\(1\le A,B\le n,A\neq B\))。

以下 \(n\) 行包含重量关系矩阵,其中第 \(i\) 行第 \(j\) 个字符为加号 + 表示砝码 \(i\) 比砝码 \(j\) 重,减号 - 表示砝码 \(i\) 比砝码 \(j\) 轻,等号 = 表示砝码 \(i\) 和砝码 \(j\) 一样重,问号 ? 表示二者的关系未知。

数据保证至少存在一种情况符合该矩阵。

输出格式

仅一行,包含三个整数,即 \(c_1,c_2,c_3\)。

输入输出样例 #1

输入 #1

6 2 5
?+????
-?+???
?-????
????+?
???-?+
????-?

输出 #1

1 4 1

输入输出样例 #2

输入 #2

14 8 4
?+???++?????++
-??=?=???????=
??????????=???
?=??+?==??????
???-???-???-??
-=????????????
-??=???=?-+???
???=+?=???????
??????????????
??????+???????
??=???-????-??
????+?????+???
-?????????????
-=????????????

输出 #2

18 12 11

说明/提示

\(4\le n\le 50\)。

信息

ID
3297
难度
(无)
分类
离散化与扫描图结构 | 最短路差分约束数据结构 | 队列线段树树状数组 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者