牛客-幸运的袋子

发表于 | 分类于 ，

题目

描述

一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。
如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。
例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，
因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3
你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。
现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。

输入

第一行输入一个正整数n(n ≤ 1000)
第二行为n个数正整数xi(xi ≤ 1000)

输出

输出可以产生的幸运的袋子数

Example

Input

3
1 1 1

Output

2

题解

思路

  • 若 x,y 满足 x+y>x*y,则 x/(x-1)>y 或 y/(y-1)>x,即 x=1 或 y=1;
  • 所以想要满足幸运条件,1 的个数必须大于等于 1;
  • 分情况讨论
    • 假设一共有 z 个 1 ( z>=1 );
    • 则全是 1 时,一共有 z-1 种情况;
    • 从非 1 序列里选择任意数量数字,分别求其和 s 与积 p,(选择数字用 递归 实现)
    • 若 p-s > z-1,则说明不能构成幸运袋子
    • 若 p-s <= z-1,则可以构成 (z-(p-s)) 个幸运袋子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>

#define ll long long

using namespace std;

int arr[1001],one,n,c;

void luckyPag(int next,int sum,ll product)
{
    int ts=sum+arr[next],tp=product*arr[next];
    if(tp-ts<one)
    {
        c+=one-tp+ts;
        for(int i=next+1;i<n;++i)
        {
            luckyPag(i,ts,tp);
            while(arr[i]==arr[i+1])
                ++i;
        }
    }
}

int main()
{
    one=c=0;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>arr[i];
        if(arr[i]==1)
          ++one;
    }
    sort(arr,arr+n);
    if(one)
    {
        c+=one-1;
        for(int i=one;i<n;++i)
        {
            luckyPag(i,0,1);
            while(arr[i]==arr[i+1])
                ++i;
        }
    }
    cout<<c;
}