首页 > 代码库 > hdu----(5047)Sawtooth(大数相乘+数学推导)

hdu----(5047)Sawtooth(大数相乘+数学推导)

2024-07-24 17:57:22   220人阅读

Sawtooth

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 422    Accepted Submission(s): 134


Problem Description
Think about a plane:

● One straight line can divide a plane into two regions.
● Two lines can divide a plane into at most four regions.
● Three lines can divide a plane into at most seven regions.
● And so on...

Now we have some figure constructed with two parallel rays in the same direction, joined by two straight segments. It looks like a character “M”. You are given N such “M”s. What is the maximum number of regions that these “M”s can divide a plane ?

 

 

Input
The first line of the input is T (1 ≤ T ≤ 100000), which stands for the number of test cases you need to solve.

Each case contains one single non-negative integer, indicating number of “M”s. (0 ≤ N ≤ 1012)
 

 

Output
For each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning. Then an integer that is the maximum number of regions N the “M” figures can divide.
 

 

Sample Input
212
 

 

Sample Output
Case #1: 2Case #2: 19
 

 

Source
2014 ACM/ICPC Asia Regional Shanghai Online
 
 
其实题目已经很清楚的告知我们是有线条分平面引申而来的了....
对于线条分平面
0  1
1  1 +1
2  1+1 +2
3 1+1 +2+3
4 1+1 +2+3+4
............
n   1+n(n+1)/2;
那么对于一个m型号的模型，其实我们可以将其视其为四条线段组合而成，这样这个公式就变为：
 4n*(4n+1)/2 +1  ---->显然得到的答案有余坠，我
0  1
1   11    2       9
2   37    19     9*2
......
推到得到：
 4n*(4n+1)/2  +1 -8*n----> 8n^2-7n+1
代码：
 1 #include<cstdio> 2 #include<cstring> 3 char aa[50],bb[50]; 4 int ans[50]; 5 int mul( char *a, char *b, int temp[]) 6 { 7  8     int i,j,la,lb,l; 9     la=strlen(a);10     lb=strlen(b);11 12     for ( i=0;i<la+lb;i++ )13         temp[i]=0;14     for ( i=0;i<=la-1;i++ ) {15           l=i;16         for ( j=0;j<=lb-1;j++ ) {17             temp[l]=(b[j]-‘0‘)*(a[i]-‘0‘)+temp[l];18             l++;19         }20     }21     while ( temp[l]==0 )22         l--;23     for ( i=0;i<=l;i++ ) {24         temp[i+1]+=temp[i]/10;25         temp[i]=temp[i]%10;26     }27     if ( temp[l+1]!=0 )28         l++;29 30     while ( temp[l]/10!=0 ) {31         temp[l+1]+=temp[l]/10;32         temp[l]=temp[l]%10;33         l++;34     }35     if ( temp[l]==0 )36         l--;37     return l;38 }39 void cal(__int64 a,char *str)40 {41     int i=0;42     while(a>0)43     {44      str[i++]=(a%10)+‘0‘;45      a/=10;46     }47 }48 int main()49 {50     int cas;51     __int64 n;52     scanf("%d",&cas);53     for(int i=1;i<=cas;i++)54     {55       scanf("%I64d",&n);56       printf("Case #%d: ",i);57       if(n==0)printf("1\n");58       else59       {60       memset(aa,‘\0‘,sizeof(aa));61       memset(bb,‘\0‘,sizeof(bb));62       memset(ans,0,sizeof(ans));63       //,(8*n-7)*n+164       cal(8*n-7,aa);65       cal(n,bb);66       int len=mul(aa,bb,ans);67        ans[0]++;68        int c=0;69      for(int j=0;j<=len;j++)70      {71          ans[j]+=c;72        if(ans[j]>9)73         {74           c=ans[j]/10;75           ans[j]%=10;76         }77      }78       if(c>0)79         printf("%d",c);80       for(int j=len;j>=0;j--)81         printf("%d",ans[j]);82     printf("\n");83     }84     }85  return 0;86 }
View Code

 

hdu----(5047)Sawtooth(大数相乘+数学推导)


联系
我们