2591:Set Definition

keyword

C++

概要

1はSの元であり、x in Sならば2*x+1, 3*x+1 in Sである。Sの元を昇順に並べたときのN(<10^7)番目の数を求める問題。
いもす先生に教えてもらった。ハミング数を列挙する時の手法でハミングDPというらしい。この方法はxから定数個のxより大きい元が生成されるときに適用可能な手法らしい。

int main(){
    pair<int,int> f, g;
    int i;
    f = MP(0,3);
    g = MP(0,4);

    ans[0] = 1;
    FOR(i,1,10000000){
        if(f.sc == g.sc){
            ans[i] = f.sc;
            f.fs++;
            g.fs++;
            f.sc = ans[f.fs]*2 + 1;
            g.sc = ans[g.fs]*3 + 1;
        }
        else if(f.sc < g.sc){
            ans[i] = f.sc;
            f.fs++;
            f.sc = ans[f.fs]*2 + 1;
        }
        else{
            ans[i] = g.sc;
            g.fs++;
            g.sc = ans[g.fs]*3 + 1;
        }
    }

    int n;
    while(scanf("%d",&n)!=EOF){
        printf("%d\n",ans[n-1]);
    }

    return 0;
}