PKU 1426 Find The Multiple
http://poj.org/problem?id=1426
正の整数nが与えられる。
1と0からなる十進の数字のうち、nで割り切れるものを答えろというような問題。
nが200以下なので、余りだけを考えて文字列に付け足していく。
線形性というのを使えた気分に浸れました。
こういう運よくあからさまな解法が見える問題はいいのですが、解法が見えない問題はいつまでたっても解法が見えないままなのが、なかなか悲しい気分になります。
bool vis[200]; main(){ int n; while(cin>>n,n){ queue<pair<int,string> >q; q.push(mp(1,"1")); memset(vis,0,sizeof(vis)); while(!q.empty()){ int c=q.front().F%n; string cs=q.front().S; q.pop(); if(vis[c])continue; vis[c]=true; if(c==0){ cout<<cs<<endl; break; } if(!vis[c*10%n])q.push(mp(c*10%n,cs+"0")); if(!vis[c*10%n+1])q.push(mp(c*10%n+1,cs+"1")); } } }