当前位置: 首页 > >

Problem 1207 半数集问题 from http://acm.fzu.edu.cn/problem.php?pid=1207

发布时间:

?Problem 1207 半数集问题


Accept: 1200????Submit: 3595
Time Limit: 1000 mSec????Memory Limit : 32768 KB


?Problem Description

给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。


(1)n∈set(n); (2)在n的左边加上一个自然数,但该自然数不能超过最*添加的数的一半; (3)按此规则进行处理,直到不能再添加自然数为止。

例如,set(6)={6,16,26,126,36,136}。半数集set(6)中有6个元素。



注意
半数集不是多重集。集合中已经有的元素不再添加到集合中。

编程任务

对于给定的自然数n,编程计算半数集set(n)中的元素个数。



?Input

本题有多组输入数据,你必须处理到EOF为止。

每组数据只有1行,给出整数n。(0


?Output

对于每组数据,输出只有1行,给出半数集set(n)中的元素个数。

?Sample Input

6

?Sample Output

6










关键是处理重复元素,考虑新增的数小于等于100,100是不会有重复的。然后就是两位数有可能与一位数的产生重复。如48 100, 4 8 100。两位数产生的包含了一位数的,所以去掉的元素个数为halfSet(4).






#include
#include
#include
#include
using namespace std;
int a[202] = {0};
int halfSet(int n){

if(a[n] == 0){
int sum = 1;
for(int i=1;i<=n/2;++i){
sum += halfSet(i);
if(i>9 && ((i/10)<=(i%10/2)))
sum -= halfSet(i/10);
}
a[n] = sum;

}

return a[n];
}
int main(){
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);

int n;
while(cin>>n){
cout<





友情链接: