UVa : 974 (Kaprekar Numbers)



// http://uva.onlinejudge.org/external/9/974.html
// runtime: 0.736s
// tag: math

#include <cstdio>
#include <string>
#include <sstream>
#include <vector>
#include <cstring>

#define N 40010

using namespace std;

vector <int> kapNum;

bool isKaprekar(int num){
	int sq = num * num;
	char res [20];

	sprintf(res, "%d", sq);

	string result = res;
	int len = strlen(res);

	for ( int i = 1; i < len; i++ ) {
		string firstPart = result.substr(0, i);
		string secondPart = result.substr(i, len - i);

		int firstNum, secondNum;
		stringstream ss (firstPart);
		ss >> firstNum;

		stringstream ss2 (secondPart);

		ss2 >> secondNum;

		if ( firstNum > 0 && secondNum > 0 && firstNum + secondNum == num) return true;
	}

	return false;
}

void preCalc(){

	for ( int i = 2; i < N; i++ ) {
		if (isKaprekar(i)) kapNum.push_back(i);
	}
}

int main ()
{

	preCalc();

	// printf("%d",kapNum.size());

	int testCases; scanf ("%d", &testCases);
	int cases = 0;
	bool blank = false;

	while ( testCases-- ) {
		int start, end;
		scanf ("%d %d", &start, &end);

		vector <int> output;

		for ( int i = 0; i < kapNum.size(); i++ ) {
			if ( kapNum [i] >= start && kapNum [i] <= end ) output.push_back(kapNum [i]);
		}

		if (blank) printf ("\n"); blank = true;

		printf ("case #%d\n", ++cases);

		if ( output.size() ) {
			for ( int i = 0; i < output.size(); i++ ) printf ("%d\n", output [i]);
		} else {
			printf ("no kaprekar numbers\n");
		}
	}

	return 0;
}

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