3795: 同色三角形(第四轮01)
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
有一个 n 个点的完全图,点分别被编号为 1 ~ n ,每个点都有 n − 1 条边连向其它点。每 条边有绿色或者红色两种颜色,现在我们知道每个点连着几条绿色边,几条红色边,但不知 道每条边具体连接哪个点。
在完全图中任选三个点,观察它们之间的三条边,如果三条边颜色相同,那么我们就称其为 “同色三角形”。现在牛牛已经知道了每个点连着几条绿色、红色边(保证这样的图一定存在), 他想要知道图中最多有几个同色三角形。
很可惜,牛牛是色盲,所以这个问题只能交给你了。
大样例:sample.zip
输入
第一行输入一个正整数 n,表示共有 n 个点。
接下来包含 n 行,每行给两个数字 a, b,其中第 i 行的数字表示第 i 个点的红色边、绿 色边数量,保证 a + b = n − 1
输出
输出一行一个整数表示答案。
样例输入 复制
4
1 2
2 1
2 1
3 0
样例输出 复制
1
提示
【说明】
【备注】
对于 10% 的数据,有 n = 3
对于 20% 的数据,有 n = 4
对于 30% 的数据,有 n = 5 对于 50% 的数据,有 n ≤ 20
对于 70% 的数据,有 n ≤ 1000
对于 100% 的数据,有 3 ≤ n ≤ 3 * 10^5