2015 GCJ 1b

counter_culture_naive.cc

#include <iostream>
#include <algorithm>
#include <string> 
#include <cstring>
#include <sstream> 
#include <queue>
using namespace std;
typedef pair<int, int> pii;
int N, TC=1;
const int U=1000005;
int dp[U];
int rev(int num){
	string s = to_string(num);
	reverse(s.begin(), s.end());
	stringstream ss(s);
	int rev_num=0;
	ss>>rev_num;
	return rev_num;
}
void bfs(){
	queue<pii> q;
	q.emplace(11, 11);//level 11
	while(!q.empty()){
		pii cur = q.front(); q.pop();
		int c=cur.first, lv=cur.second;
		if(c>U) continue;
		if(dp[c]!=-1) continue;
		if(dp[c]==-1) dp[c]=lv;
		q.emplace(c+1, lv+1);
		q.emplace(rev(c), lv+1);
	}
}
int main(){
	cin>>N;
	memset(dp, -1, sizeof(dp));
	for(int i=1;i<=10;++i) dp[i]=i;
	bfs();
	int in;
	for(int i=0;i<N;++i){
		cin>>in;
		cout<<"Case #"<<TC++<<": "<<dp[in]<<endl;
	}
	return 0;
}


/*vepifanov: elegant way to reverse long number*/
ll rev (ll x) {
	ll y = 0;
	while (x) {
		y = y * 10 + x % 10;
		x /= 10;
	}
	re y;
}
/* 從N倒著往前減，我也有想到9001 -> 1009
   但無法確定是用幾位數來往回走，看來是從位數的一半+1的來推算，if x=932177, base=10000
   例如9321->9301 flip-> 1039 
   到底為什麼base是平方的來檢查？
*/
ll get (ll x) {
	ll base = 1;
	while (base * base <= x) base *= 10;
	ll ans = 0;
	while (x >= 10) {
		while ((base / 10) * (base / 10) > x) base /= 10;
		ll y = x % base;
		if (y == 0) {
			ans++;
			x--;
		} else {
			ans += y;
			x -= y - 1;
			ll z = rev (x);
			if (x != z) x = z; else x--;
		}
	}
	re ans + x;
}