P2036 [COCI 2008/2009 #2] PERKET
题目描述
Perket 是一种流行的美食。为了做好 Perket,厨师必须谨慎选择食材,以在保持传统风味的同时尽可能获得最全面的味道。
你有 n 种可支配的配料,第 i 种配料的酸度为 si、苦度为 bi。当你加入若干种配料时:
∙总酸度为所加入配料的酸度之乘积;
∙总苦度为所加入配料的苦度之和。
美食应该做到口感适中,因此你希望「总酸度与总苦度之差的绝对值」尽可能小。此外你必须至少加入一种配料,因为没有任何食物是只以水为配料的。
请你求出这个最小绝对差。
输入格式
第一行输入一个整数 n(1≦n≦10) 代表可供选用的食材种类数。
此后 n 行,第 i 行输入两个整数 si,bi(1≦si,bi≦109),分别代表第 i 种食材的酸度和苦度。
保证将所有 n 种食材全部使用时的总酸度与总苦度都小于 109。
输出格式
输出一行一个整数,代表可能的总酸度与总苦度的最小绝对差。
测试样例
1
3 10
7
样例 1 解释
只有一种食材,只能选它,总酸度为 3、总苦度为 10,绝对差为 ∣3−10∣=7。
2
3 8
5 8
1
样例 2 解释
三种选法如下:
∙只选第 1 种:∣3−8∣=5;
∙只选第 2 种:∣5−8∣=3;
∙两种都选:总酸度 3×5=15,总苦度 8+8=16,∣15−16∣=1。
因此最小绝对差为 1。
4
1 7
2 6
3 8
4 9
1
样例 3 解释
选择后三种食材时,总酸度为 2×3×4=24,总苦度为 6+8+9=23,绝对差为 1。可以枚举全部 24−1=15 种非空选法验证,没有比 1 更小的绝对差。
提示
对于 100% 的数据,1≦n≦10,1≦si,bi≦109,且全部食材的总酸度乘积与总苦度之和都小于 109。
非空子集一共只有 2n−1≦1023 个,直接枚举所有选法即可。