首页 > itarticle > calculator conundrum – uva 11549

calculator conundrum – uva 11549

admin 11月 12, 2020 0

Problem

Summary

Given n(1 <= n <= 9) and k (0 <= k < 10^n) where n is the number of digits the calculator can display, k is the starting number. Compute the maximum number that we can get by repeatedly squaring the starting number.

Analyse

Floyd Cycle Detection Algorithm !

Code in C++

using namespace std;
int buffer[100];
int (int n, int p) {	
	if (!p) return 0;
	long long q = (long long) p * p;
	int tmp = 0;
	while (q > 0) {
		buffer[tmp++] = q % 10;
		q /= 10;
	}
	if (n > tmp) n = tmp;
	int ans = 0;
	for (int i = 0; i < n; i++)
		ans = ans * 10 + buffer[--tmp];
	return ans;
}
int main() {
	int T;
	int n, k;
	cin >> T;
	while (T--) {
		cin >> n >> k;
		int ans = k;
		int p1 = k, p2 = k;
		do {
			p1 = floyd(n, p1);
			p2 = floyd(n, p2); if (p2 > ans) ans = p2;
			p2 = floyd(n, p2); if (p2 > ans) ans = p2;
		} while (p1 != p2);
		cout << ans << endl;
	}
	return 0;
}