2014
02-10

# Count Problem

In this problem,we need to count the number that accord with the following rule(include the input number n).Read a integer number n(1<=n<=2^31 – 1) first,then do as following ways:
(1)Do nothing, then exit the process.
(2)Add a digit to the left of it,but the digit should not bigger than the half of the original first digit.For example,from 36 to 136 is legal,but 36 to 236 is illegal because 2 is bigger than half of 3.
(3)After add the digit,continue the process,until could not add digit anymore.

The first line of the input contains an integer T which means the number of test cases.Then T lines follow, each line starts with a number n(1<=n<=2^31 – 1).

The first line of the input contains an integer T which means the number of test cases.Then T lines follow, each line starts with a number n(1<=n<=2^31 – 1).

2
1
6

1
6

Hint
The first case 1 cannot any digital to the leftmost, so the number so only 1.
The second case 6 can add 1, 2, 3 to the leftmost so 16,26,36 are legal. And then 26, 36 also can add  1 to the leftmost so get 126, 136. So 6,16,26,36,126,136 are all legal.The result is 6. 

PS:题目很简单，找到规律然后用数组储存，本体笔下误错了一次！
#include<stdio.h>
#include<string.h>
int main()
{
int t,n,a[10]={0,1,2,2,4,4,6,6,10,10};
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
while(n>9)n/=10;
printf("%d\n",a[n]);
}
return 0;
}

1. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测