首页 > ACM题库 > HDU-杭电 > hdu 2451 Simple Addition Expression-数学相关-[解题报告]C++
2014
01-26

hdu 2451 Simple Addition Expression-数学相关-[解题报告]C++

Simple Addition Expression

问题描述 :

A luxury yacht with 100 passengers on board is sailing on the sea in the twilight. The yacht is ablaze with lights and there comes out laughers and singing from the hall where an evening party is in full swing. People are singing, dancing and enjoying themselves.

The yacht is equipped with the most advanced navigation and driving system which can all be manipulated by a computer. When the captain notices that there is only gentle breeze and the sea waves are not high, he starts the autopilot. The yacht sails forward smoothly, ploughs the waves. When it’s completely dark, the passengers start to feel a little funny for sudden forward rushes or sudden decelerations or slight swings. The captain immediately walks to the driving platform and switches the autopilot to human manipulation. The yacht returns back to normal and the party restarts. Laughers come back, too.

The captain summons the engineer on board to do a thorough check of the navigation system. It turns out that only the computer is out of order, but the exact failure is still unclear. There is a computer scientist among the passengers who is also invited to the cab to give a hand. He first inputs several groups of data to test the computer. When he inputs 1+2+3, the computer outputs 6, which is exactly right. But when he inputs 4+5+6, the computer outputs 5, which is wrong. Then he inputs 12+13+14, and gets 39, another right answer, while he inputs 14+15+16, and gets 35, another wrong answer. After the test, the computer scientist says smilingly: “the failure is clear now. The computer’s adder can not carry." After excluding the failure, the captain restarts the autopilot and the yacht returns back to normal, sailing smoothly on the sea.

The captain and the engineer invite the computer scientist to sit down and have a talk. The computer scientist tells a story as following:

A former mathematician defined a kind of simple addition expression.
If there is an expression (i) + (i+1) + (i+2), i>=0, when carried out additive operations, no position has a carry, it is called simple addition expression.

For instance, when i equals 0, 0+1+2 is a simple addition expression, meanwhile when i equals 11, 11+12+13 is a simple addition expression, too. Because of that no position has a carry.

However, when i equals 3, 3+4+5 is not a simple addition expression, that is because 3+4+5 equals 12, there is a carried number from unit digit to tens digit. In the same way, when i equals 13, 13+14+15 is not a simple addition expression, either. However, when i equals 112, 112+113+114 is a simple addition expression. Because 112+113+114 equals 339, there is no carry in the process of adding.

when the students have got the definition of simple addition expression, the mathematician puts forward a new question: for a positive integer n, how many simple addition expressions exist when i<n. In addition, i is the first number of a simple addition expression.

when the value of n is large enough, the problem needs to be solved by means of computer.

输入:

There are several test cases, each case takes up a line, there is an integer n (n<10^10).

输出:

There are several test cases, each case takes up a line, there is an integer n (n<10^10).

样例输入:

1
2
3
4
10
11

样例输出:

1
2
3
3
3
4

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=2451

 ********************************************************

    
由题意知:要想不进位,那么个位数字只能取0、1、2;
其它高位只能取0、1、2、3;但要注意最高位不能是0!
    
例如:n=1222,那么就要找从0到1221有多少个满足条件的。
    
首先是看n的最高位大不大于3,如果大于3,就是a[l]
(l是n的长度),否则进行下面的操作:第一步:找到0到999有多
少个?(这个我们先打表统计小于等于X位的有有多少个数,从
表中获得)。第二步:考虑1000到1221有多少个,这个怎么处理
了,n=n-1000=221,这时只要考虑0到221有到少个,这个采用上
面一样的思考方法重复执行!最后一步:当长度l==1时,这就是
对个位的考虑了!!
********************************************************
#include
#include
#include
#include
using namespace std;
#define ll __int64
int fun(int a)
{
    int
sum=1;
    for(int i=0;
i
       
sum*=4;
    return
sum;
}
template
void inist(int (&a)[n])
{
   
a[0]=0;
   
a[1]=3;
   
a[2]=12;
    for(int i=3;
i
    {
       
a[i]=9*fun(i-2)+a[i-1];
    }
}
int main()
{
    int
a[12];
    char
b[12];
    ll n;
   
inist(a);///a[]中存的是小于等于l位的数的个数!
   
while(cin>>n)
    {
       
if(n==0)
       
{
           
cout<<”0\n”;
           
continue;
       
}
       
n–;
       
_i64toa(n,b,10);
   
///将_int64位的数转换成字符串!第三个数是按几进制转!
       
int l=strlen(b),sum=0;
       
while(l>1)
       
{
           
if(b[0]-’0′>3)///这是对最高位的判断!
           
{
               
sum+=a[l];
               
break;
           
}
           
else
               
sum+=a[l-1];
           
n=n-(int)pow(10,l-1);
           
_i64toa(n,b,10);
           
l=strlen(b);
       
}
       
if(l==1)///这是是对个位的处理!
       
{
           
if(b[0]-’0′>2)
               
sum+=3;
           
else
               
sum+=(b[0]-’0′+1);
       
}
       
cout<<sum<<endl;
    }
    return
0;
}


解题转自:http://blog.sina.com.cn/s/blog_a7d396a40101f8n9.html