UESTC 1264人民元の構造数論


人民元の構造
Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit  Status
人民元の額面が1、2、5、10であることはよく知られていますが、なぜこの数値なのかを分析してみると、1−10の数字ごとに額面ごとに1枚以上を選択して加算することができます
減算(お釣り)として構成され、(例えば、1+2=3、5−1=4、5+1=6、5+2=7、1+2+5=8、10−1=9)
しかし、実際には1、2、7の3つの額面だけで1−10の数字を構成することができます.
( 1+2=3,7−1−2=4,7−2=5,7−1=6,7+1=8,7+2=9,7+1+2=10 )
そこで質問ですが、数nをあげると、少なくとも何種類の異なる額面が必要なのかを聞いて、1−nからのすべての数字を構成することができます.各数字を構成する際、同種の額面は1枚を超えてはいけないことに注意してください.
Input
1つの数字n(1<=n<=10000000)
Output
1つの数字は、少なくともどれだけの異なる値が必要かを表す1−nからのすべての数字を構成することができる.
Sample input and output
Sample Input
Sample Output
10
3

Source
第7回ACM趣味プログラミングコンテスト第3戦(公式戦)C
My Solution
tem+sumは、現在の最大構成可能な値です.
そうでなければtem=sum;tem=2*(tem+sum)+1;新しい最大値はtem+sum
1,3,9は法則を探し始めて1,1,3は1,2,3,4を構成することができて、9は13.これまで与えられた1,2,7の良い穴を構成することができて、また1,3,8を試してやっとこの3つの数のとできるだけのことを理解します
才能がある.4番目からこの法則があると思っていた.2回間違えてやっと1、3、9が直接第1項からこの法則を満たし始めたと思った.sumofall*2+1
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int n,sum=13,cot=3,tem=0;
    scanf("%d",&n);
    while(tem+sum<n){
        sum+=tem;
        tem=sum;//cout<<tem<<endl;
        sum=2*tem+1;//cout<<sum<<endl;
        cot++;
    }
    if(n==1) printf("1");
    else if(n<=4) printf("2");
    else if(n<=13) printf("3");
    else printf("%d",cot);
    return 0;
}