Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1639
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1639
Generate Random Numbers
Local Contest, University of Ulm 
Germany
Timelimit: 1
John von Neumann suggested in 1946 a method to create a sequence of pseudo-random numbers. His idea is known as the "middle-square"-method and works as follows: We choose an initial value a0, which has a decimal representation of length at most n. We then multiply the value a0 by itself, add leading zeros until we get a decimal representation of length 2 × n and take the middle n digits to form ai. This process is repeated for each ai with i > 0. In this problem we use n = 4.
Example 1: a0=5555, a02=30858025, a1=8580,...
Example 2: a0=1111, a02=01234321, a1=2343,...
Unfortunately, this random number generator is not very good. When started with an initial value it does not produce all other numbers with the same number of digits.
Your task is to check for a given initial value a0 how many different numbers are produced.
Input
The input contains several test cases. Each test case consists of one line containing a0 (0 < a0 < 10000). Numbers are possibly padded with leading zeros such that each number consists of exactly 4 digits. The input is terminated with a line containing the value 0.
Obs.: Note that the third test case has the maximum number of different values among all possible inputs.
Output
For each test case, print a line containing the number of different values ai produced by this random number generator when started with the given value a0. Note that a0 should also be counted.
| Sample Input | Sample Output |
|
5555 |
32 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
int n, count;
while(cin >> n && n)
{
bool visi[1000000];
memset(visi, false, sizeof(visi));
count = 0;
while(!visi[n])
{
visi[n] = true;
n *= n;
n /= 100;
n %= 10000;
count++;
}
cout << count << endl;
}
return 0;
}
Input
0815
6239
0
Output
17
111