728
UVA之11549 - Calculator Conundrum
【題目】
Problem C
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 the n 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 integer t (1 ≤ t ≤ 200), the number of test cases. Each test case contains two integers n (1 ≤ n ≤ 9) and k (0 ≤ k < 10n) where n 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
【分析】
【思路一】
題目已經暗示計算器顯示會的數字出現循環，所以不妨一個一個的模擬，每次判斷新得到的數字是否以前出現過。如何判斷呢？一種方法
就是把所有計算出的數字放在數組中，然後一個一個的比較。這種方法每次判斷需要花費很長時間，相當慢，能否開一個數組visited，直接讀取visited[k]
來判斷整數k是否出現過，k(0 <= k < 10^9)的範圍很大，需要開辟的空間很大，嚴重浪費資源。在這種情況下我們可以利用STL的集合set。
【思路二】
這個方法還是不夠快的，第二種方法是用神奇的Floyd判圈算法。
假設兩個小孩在一個可以無限向前跑的跑道上賽跑，同時出發，但其中一個小孩的速度是另一個小孩速度的兩倍。如果跑道是直的，跑得快的小孩永遠在前麵，另一個小孩
永遠都追不上。但如果跑道有環，則跑的快的小孩將”追上“跑的慢的小孩。
【代碼】
/*********************************
* 日期：2014-5-2
* 作者：SJF0115
* 題號: 11549 - Calculator Conundrum
* 地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2544
* 來源：UVA
* 結果：Accepted
* 總結：
**********************************/
#include <iostream>
#include <set>
#include <stdio.h>
using namespace std;
int bits[10];
//截取k平方的高n位
int HighNBits(int n,int k){
if(!k){
return 0;
}
long long s = (long long)k * k;
int index = 0;
//分離s的各位
while(s > 0){
bits[index++] = s % 10;
s /= 10;
}
//不夠n位
if(n > index){
n = index;
}
//高n位
int result = 0;
for(int i = 0;i < n;i++){
result = result * 10 + bits[--index];
}
return result;
}
int main(){
int T,i,j,n,k;
scanf("%d",&T);
//T組測試數據
while(T--){
scanf("%d %d",&n,&k);
set<int> visited;
int max = 0;
//判斷新得到的數值以前是否出現過
while(visited.count(k) == 0){
visited.insert(k);
//更新最大值
if(max < k){
max = k;
}
k = HighNBits(n,k);
}
printf("%d\n",max);
}
return 0;
}
【代碼2】
/*********************************
* 日期：2014-5-2
* 作者：SJF0115
* 題號: 11549 - Calculator Conundrum
* 地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2544
* 來源：UVA
* 結果：Accepted
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;
int bits[10];
//截取k平方的高n位
int HighNBits(int n,int k){
if(!k){
return 0;
}
long long s = (long long)k * k;
int index = 0;
//分離s的各位
while(s > 0){
bits[index++] = s % 10;
s /= 10;
}
//不夠n位
if(n > index){
n = index;
}
//高n位
int result = 0;
for(int i = 0;i < n;i++){
result = result * 10 + bits[--index];
}
return result;
}
int main(){
int T,i,j,n,k;
scanf("%d",&T);
//T組測試數據
while(T--){
scanf("%d %d",&n,&k);
int max = k;
int k1 = k,k2 = k;
do{
//小孩1
k1 = HighNBits(n,k1);
//小孩2 第一步
k2 = HighNBits(n,k2);
if(k2 > max){
max = k2;
}
//小孩2 第二步
k2 = HighNBits(n,k2);
if(k2 > max){
max = k2;
}
}while(k1 != k2);//快的小孩追上慢的小孩停止
printf("%d\n",max);
}
return 0;
}
最後更新：2017-04-03 12:56:32