列表

详情

NC24753. [USACO 2010 Dec B]Bad Random Numbers

描述

Bessie is trying to generate random numbers. She stumbled upon an old reference to the 'middle square' method for making numbers that appear to be random. It works like this:
* Pick a starting four digit number (1 <= N <= 9999)
* Extract its middle two digits (the hundreds and tens digit) as a number
* Compute the square of those two digits
* That square is the 'random number' and becomes the new starting number 
Here's a sample:                 Num  Middle  Square                7339    33     1089                1089     8       64                  64     6       36                  36     3        9                   9     0        0                   0     0        0 The 'pigeon hole principle' tells us that the random numbers surely must repeat after no more than 10,000 of them -- and the sequence above repeats after just six numbers (the next number and all subsequent numbers are 0). Note that some sequences repeat in a more complex way; this one alternates back and forth between 576 and 3249:                 Num  Middle  Square                 2245   24      576                    576   57     3249                  3249   24      576
Your job is to tell Bessie the count of 'random numbers' that can be generated from a starting number before the sequence repeats a previously seen number. In the first case above, the answer is '6'. In the 'alternating' case, the answer is '3'.

输入描述

* Line 1: A single integer: N

输出描述

* Line 1: A single integer that is the count of iterations through the middle square random number generator before a previous value is repeated

示例1

输入: 

7339

输出: 

6

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 480K, 提交时间: 2019-10-12 16:10:43 

#include <bits/stdc++.h>
using namespace std;
int vis[10005];
int main(){
    int n; cin>>n;
    int ans=0;
    while(!vis[n]){
        vis[n]=1;
        ++ans;
        int tmp=(n-n/1000*1000)/10;
        n=tmp*tmp;
    }
    cout<<ans;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2019-10-12 18:29:01 

#include<cstdio>
using namespace std;
#define N 10000
bool e[N];
int main(){
	int x;	scanf("%d",&x);
	int ans=0;
	while(!e[x]){
		e[x]=true;
		x/=10;	x%=100;	x*=x;
		ans++;
	}
	printf("%d",ans);
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 35ms, 内存消耗: 3520K, 提交时间: 2019-10-12 20:48:08 

N=int(input())
n=N//10%100
t=1
s=0
mid=[0]*10000
while n!=0:
    if n in mid:
        print(t)
        exit()
    t+=1
    mid[s]=n
    s+=1
    n=n**2//10%100
print(t+1)

上一题

© 2024 nowcoder.com