LG#P2036. [COCI 2008] PERKET

[COCI 2008] PERKET

P2036 [COCI 2008/2009 #2] PERKET

题目描述

\hspace{15pt}Perket 是一种流行的美食。为了做好 Perket,厨师必须谨慎选择食材,以在保持传统风味的同时尽可能获得最全面的味道。

\hspace{15pt}你有 nn 种可支配的配料,第 ii 种配料的酸度为 sis_i、苦度为 bib_i。当你加入若干种配料时:

∙ \hspace{15pt}\bullet\,总酸度为所加入配料的酸度之乘积;

∙ \hspace{15pt}\bullet\,总苦度为所加入配料的苦度之和。

\hspace{15pt}美食应该做到口感适中,因此你希望「总酸度与总苦度之差的绝对值」尽可能小。此外你必须至少加入一种配料,因为没有任何食物是只以水为配料的。

\hspace{15pt}请你求出这个最小绝对差。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦10)n \left(1 \leqq n \leqq 10\right) 代表可供选用的食材种类数。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 si,bi(1≦si,bi≦109)s_i, b_i \left(1 \leqq s_i, b_i \leqq 10^9\right),分别代表第 ii 种食材的酸度和苦度。

\hspace{15pt}保证将所有 nn 种食材全部使用时的总酸度与总苦度都小于 10910^9。

输出格式

\hspace{15pt}输出一行一个整数,代表可能的总酸度与总苦度的最小绝对差。

测试样例

1
3 10
7

样例 1 解释

\hspace{15pt}只有一种食材,只能选它,总酸度为 33、总苦度为 1010,绝对差为 ∣3−10∣=7|3-10| = 7。

2
3 8
5 8
1

样例 2 解释

\hspace{15pt}三种选法如下:

∙ \hspace{23pt}\bullet\,只选第 11 种:∣3−8∣=5|3-8| = 5;

∙ \hspace{23pt}\bullet\,只选第 22 种:∣5−8∣=3|5-8| = 3;

∙ \hspace{23pt}\bullet\,两种都选:总酸度 3×5=153 \times 5 = 15,总苦度 8+8=168+8=16,∣15−16∣=1|15-16| = 1。

\hspace{15pt}因此最小绝对差为 11。

4
1 7
2 6
3 8
4 9
1

样例 3 解释

\hspace{15pt}选择后三种食材时,总酸度为 2×3×4=242 \times 3 \times 4 = 24,总苦度为 6+8+9=236+8+9 = 23,绝对差为 11。可以枚举全部 24−1=152^4 - 1 = 15 种非空选法验证,没有比 11 更小的绝对差。

提示

\hspace{15pt}对于 100%100\% 的数据,1≦n≦101 \leqq n \leqq 10,1≦si,bi≦1091 \leqq s_i, b_i \leqq 10^9,且全部食材的总酸度乘积与总苦度之和都小于 10910^9。

\hspace{15pt}非空子集一共只有 2n−1≦10232^n - 1 \leqq 1023 个,直接枚举所有选法即可。