GCJ2012 Qualification C. Recycled Numbers

2012-04-15

10:55 |

A <= n <= B <= 2000000 な n の各桁を回転させた数字 m が A <= n < m <= B になるような (n, m) の個数を重複なく求める問題。

2000000 だから微妙かと思いつつ特に工夫なく書いたら大丈夫そうなので出した
重複をカウントしない処理が抜けていて large 落ちた(´・ω・`)
small のテストケースに頼ってはいけない...

と思ったら small どころか sample 1111 2222 -> 287 とあって親切にも "Are we sure about the output to Case #4? Yes, we're sure about the output to Case #4." と書いてあったのであった。
目diff が 288 と 287 を等しいと判定してしまった ... 目diff failed.

↓あとで

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int A, B;
		cin>>A>>B;
		int sp=1;
		VI tb;
		VI tb2;
		while(B>sp*10) {
			sp*=10;
			tb.PB(sp);
		}
		REP(i, tb.size()) tb2.PB(sp*10/tb[i]);
		int ans=0;
		for(int i=A;i<=B;i++) {
			//cout<<"i "<<i<<endl;
			set<int> used;
			REP(j, tb.size()) {
				int b = i/tb[j] + (i%tb[j])*tb2[j];
				if(i<b && A<=b && b<=B && /* ADDED */ used.insert(b).second) {
					ans++;
					//cout<<b<<endl;
				}
			}
		}
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}