UVa : 11730 (Number Transformation)



// http://uva.onlinejudge.org/external/117/11730.html
// Runtime : 0.016s
// bfs

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

bool mark [N];
vector <int> primeList;
vector <int> factors [1000 + 10];

void sieve ()
{
	memset (mark, true, sizeof (mark));

	mark [0] = mark [1] = false;

	for ( int i = 4; i < N; i += 2 ) mark [i] = false;

	for ( int i = 3; i * i <= N; i += 2 ) {
		if ( mark [i] ) {
			for ( int j = i * i; j < N; j += 2 * i ) mark [j] = false;
		}
	}

	primeList.clear ();
	primeList.push_back (2);

	for ( int i = 3; i < N; i += 2 ) {
		if ( mark [i] ) primeList.push_back (i);
	}

	//printf ("%d\n", primeList.size ());
}

void findFactors ()
{
	for ( int i = 0; i < 1010; i++ ) factors [i].clear ();

	vector <int>::iterator it;

	for ( int i = 0; i < 1010; i++ ) {
		int index = 0;
		int tmp_i = i;
		while ( primeList [index] * primeList [index] <= i ) {
			while ( tmp_i % primeList [index] == 0 ) {
				factors [i].push_back (primeList [index]);
				tmp_i /= primeList [index];
			}
			index++;
		}

		if ( tmp_i > 1 ) factors [i].push_back (tmp_i);
		
		it = unique (factors [i].begin (), factors [i].end ());
		factors [i].resize (it - factors [i].begin ());
	}
}

int minimumTransform (int s, int t)
{
	queue < pair <int, int> > q;
	q.push (make_pair (s, 0));

	bool freq [1000 + 10];
	memset (freq, false, sizeof (freq));

	while ( !q.empty () ) {
		pair <int, int> p = q.front ();
		q.pop ();

		if ( p.first == t ) return p.second;
		if ( freq [p.first] ) continue;

		freq [p.first] = true;
			
		for ( size_t i = 0; i < factors [p.first].size (); i++ ) {
			int sum = p.first + factors [p.first].at (i);
			if ( sum <= t && factors [p.first].at (i) != p.first ) q.push (make_pair (sum, p.second + 1));
		}
	}

	return -1;
}

int main ()
{
	sieve ();
	findFactors ();

	int s, t;
	int cases = 0;

	while ( scanf ("%d %d", &s, &t) ) {
		if ( s == 0 && t == 0 ) break;

		printf ("Case %d: %d\n", ++cases, minimumTransform (s, t));
	}

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s