UVa 11549-Calculator Conundrum(計算ループ・セクション)

CALCULATOR CONUNDRUM
Alice got a hold of an old calculator that can display n digits. She was bored enough to come up with the following time waster.
She enters a number k then repeatedly squares it until the result overflows. When the result overflows, only then most significant digits are displayed on the screen and an error flag appears. Alice can clear the error and continue squaring the displayed number. She got bored by this soon enough, but wondered:
“Given n and k, what is the largest number I can get by wasting time in this manner?”
Program Input
The first line of the input contains an integert (1 ≤ t ≤ 200), the number of test cases. Each test case contains two integersn (1 ≤ n ≤ 9) and k (0 ≤ k < 10n) wheren is the number of digits this calculator can display k is the starting number.
Program Output
For each test case, print the maximum number that Alice can get by repeatedly squaring the starting number as described.
Sample Input & Output
INPUT

2
1 6
2 99

OUTPUT

9
99

Calgary Collegiate Programming Contest 2008
 
経験と教訓:問題の解決方法を考える前に、まず既知の条件に基づいて問題の特徴と性質を推定しなければならない.例えば本題では,計算機が表示できる数字は最大nビットであり,表示できる数字の個数は限られているが,kに対して平方を求め,次に前のnビット数を取る方法で繰り返し,いつか,繰り返しの数が現れ,この数がループ節である.

//  STL  set      
#include <iostream>
#include <cstdio>
#include <set>
#include <cmath>
using namespace std;

//#define LOCAL

#ifdef LOCAL
#define TYPE __int64
#else
#define TYPE long long
#endif

int HighNDigits(int n, TYPE k)
{
	int len = floor(log10(k)) + 1;
	if (len > n)
	{
		len -= n;
		int m = 1;
		while (len-- != 0)
		{
			m *= 10;
		}
		return (int)(k / m);
	}
	return (int)k;
}

int main(void)
{
	int ncases;
	cin >> ncases;
	while (ncases-- != 0)
	{
		int n, k;
		cin >> n >> k;
		int max = k;
		set<int> s;
		while (s.find(k) == s.end())
		{
			s.insert(k);
			if (k > max)
			{
				max = k;
			}
			k = HighNDigits(n, (TYPE)k*k);
		}
		cout << max << endl;
	}
	return 0;
}

 

//Floyd    
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

//#define LOCAL

#ifdef LOCAL
#define TYPE __int64
#else
#define TYPE long long
#endif

int HighNDigits(int n, TYPE k)
{
	int len = floor(log10(k)) + 1;
	if (len > n)
	{
		len -= n;
		int m = 1;
		while (len-- != 0)
		{
			m *= 10;
		}
		return (int)(k / m);
	}
	return (int)k;
}

int main(void)
{
	int ncases;
	cin >> ncases;
	while (ncases-- != 0)
	{
		int n, k;
		cin >> n >> k;
		int k1 = k, k2 = k, max = k;
		//k1       ，k2       ，      ，
		//k2    k1  ，  k2          ，  max  
		do
		{
			k1 = HighNDigits(n, (TYPE)k1*k1);
			k2 = HighNDigits(n, (TYPE)k2*k2);
			if (k2 > max) max = k2;
			k2 = HighNDigits(n, (TYPE)k2*k2);
			if (k2 > max) max = k2;
		} while (k2 != k1);
		cout << max << endl;
	}
	return 0;
}