搜索

Count the Polygons

Time Limit: 2000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

[Submit] [Go Back] [Status]

Description

Count the Polygons

Input: Standard Input

Output: Standard Output

A polygon is a plane figure that is bounded by a closed path and composed of a finite sequence of straight line segments. These segments are called its edges, and the points where two edges meet are the polygon's vertices.

You have got a set of N sticks of various lengths. How many ways can you choose K sticks from this set and form a polygon with K sides by joining the end points.

Input

The first line of input is an integer T (T<100) that indicates the number of test cases. Each case starts with a line containing 2 positive integers N and K ( 3≤N≤30 & 3≤K≤N ). The next line contains N positive integers in the range [1, 2^31), which represents the lengths of the available sticks. The integers are separated by a single space.

Output

For each case, output the case number followed by the number of valid polygons that can be formed by picking K sticks from the given N sticks.

Sample Input Output for Sample Input

4 3

10 10 20 20

6 4

1 1 1 1 1 1

4 3

10 20 30 100000000

6 6

2 3 4 5 6 7

Case 1: 2
Case 2: 15
Case 3: 0
Case 4: 1

1000ms：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 #define ll long long
 7 int a[40],k,maxa,n;
 8 ll ans,C[40][40],sum[40];
 9 void dfs(ll summ,int cnt,int x)
10 {
11     if(cnt==k)
12     {
13         if(summ>a[maxa])ans++;
14         return ;
15     }
16     if(summ+sum[k-cnt+x-1]-sum[x-1]>a[maxa])
17     {
18         ans+=C[maxa-x][k-cnt];
19         return ;
20     }
21     if(summ+sum[maxa-1]-sum[maxa-k+cnt-1]<=a[maxa])return ;
22     if(x==maxa)return;
23     dfs(summ+a[x],cnt+1,x+1);
24     if(maxa-x>k-cnt)
25     dfs(summ,cnt,x+1);
26 }
27 void init()
28 {
29     for(int i=1; i<=30; i++)
30     {
31         C[i][0]=C[i][i]=1;
32         for(int j=1; j<i; j++)
33             C[i][j]=C[i-1][j-1]+C[i-1][j];
34     }
35 }
36 int main()
37 {
38     int T,i,j;
39     init();
40     scanf("%d",&T);
41     for(i=1; i<=T; i++)
42     {
43         ans=0;
44         memset(sum,0,sizeof(sum));
45         scanf("%d%d",&n,&k);
46         for(j=0; j<n; j++)
47             scanf("%d",&a[j]);
48         sort(a,a+n);
49         sum[0]=a[0];
50         for(j=1; j<n; j++)sum[j]=sum[j-1]+a[j];
51         k--;
52         for(j=k; j<n; j++)
53         {
54             maxa=j;
55             dfs(0,0,0);
56         }
57         printf("Case %d: %lld
",i,ans);
58     }
59 }

View Code

9ms：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 #define ll long long
 7 int a[40],k,maxa,n;
 8 ll ans,C[40][40],sum[40];
 9 void dfs(ll summ,int cnt,int x)
10 {
11     if(cnt==k)
12     {
13         if(summ>a[maxa])ans++;
14         return ;
15     }
16     if(x==0)return;
17     if(summ+sum[k-cnt]>a[maxa])
18     {
19         ans+=C[x][k-cnt];
20         return ;
21     }
22     if(summ+sum[x]-sum[x-k+cnt]<=a[maxa])return ;
23     dfs(summ+a[x],cnt+1,x-1);
24     if(x>k-cnt)
25         dfs(summ,cnt,x-1);
26 }
27 void init()
28 {
29     for(int i=1; i<=31; i++)
30     {
31         C[i][0]=C[i][i]=1;
32         for(int j=1; j<i; j++)
33             C[i][j]=C[i-1][j-1]+C[i-1][j];
34     }
35 }
36 int main()
37 {
38     int T,i,j;
39     init();
40     scanf("%d",&T);
41     for(i=1; i<=T; i++)
42     {
43         ans=0;
44         memset(sum,0,sizeof(sum));
45         scanf("%d%d",&n,&k);
46         for(j=1; j<=n; j++)
47             scanf("%d",&a[j]);
48         sort(a+1,a+n+1);
49         sum[0]=0;
50         for(j=1; j<=n; j++)sum[j]=sum[j-1]+a[j];
51         k--;
52         for(j=k+1; j<=n; j++)
53         {
54             maxa=j;
55             dfs(0,0,j-1);
56         }
57         printf("Case %d: %lld
",i,ans);
58     }
59 }

View Code