242014 - T5-最优分组方案

题目描述

有 n 名学生,第 i 名学生的能力值为 a_i。

现在需要将全部学生划分成两个非空小组。

每名学生必须且只能属于其中一个小组。

设两个小组的能力值总和分别为 S_1 和 S_2。

定义两个小组的能力差为:

D=|S_1-S_2|

请完成以下两个任务:

  1. 求出所有合法分组方案中,最小的能力差 D。
  2. 统计有多少种不同的分组方案能够达到最小能力差。

注意:

  • 两个小组交换名称后,视为同一种分组方案。
  • 两个小组都必须至少包含一名学生。
  • 不同位置的学生视为不同个体,即使他们的能力值相同。
输入

第一行输入一个正整数 n,表示学生数量。

第二行输入 n 个正整数:

a_1,a_2,\ldots,a_n

表示每名学生的能力值。

输出

输出两个整数:

  • 第一个整数表示最小能力差 D。
  • 第二个整数表示达到最小能力差的不同分组方案数量。

两个整数之间使用一个空格分隔。

样例

输入

4
1 2 3 4

输出

0 1
说明

样例解释

一种最优分组方式为:

第一组:第 1,4 名学生。

第二组:第 2,3 名学生。

两组能力值总和分别为:

S_1=a_1+a_4=1+4=5

S_2=a_2+a_3=2+3=5

因此最小能力差为:

D=|S_1-S_2|=|5-5|=0

交换两个小组的名称不产生新的分组方案,所以答案为:

0 1

数据范围

  • 2\le n\le 20
  • 1\le a_i\le 10^6
标签
题目参数
时间限制 1 秒
内存限制 511 MB
提交次数 0
通过人数 0
金币数量 5 枚
难度 提高


上一题 下一题