2591:Set Definition
keyword
概要
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; }