TJU Problem 2120 Solution – Java

Psuedo-Random Numbers is a fairly straight forward question but it has one main trick that even I didn’t notice initially… The last sentence of the explanation says “But be careful — the cycle might not begin with the seed!” and that’s the trick.

 

Essentially the example shows you how to solve this problem if the seed is the first number, but what should be assumed from the problem is that the random number sequence has “cycles” which will eventually restart. so the trick is to figure out if the new number you’ve generated has been generated before, and if it did, you’re done. All it is is a simple array that is as big as M (read the problem…), and every time a number is calculated and added to the array, backtrack to make sure it wasn’t there before. if it was, the arrays length from the point it was originally generated until now is your answer… here’s a simple solution in Java.

import java.util.Scanner;

public class p2120 {

    public static void main(String[] args){
        boolean run = true;
        boolean done = false;
        int Z, I, M, L = 0;
        int caseNumber = 1; 
        int answer = 0;
        Scanner src = new Scanner(System.in);
        while(run){
            Z = src.nextInt();
            I = src.nextInt();
            M = src.nextInt();
            L = src.nextInt();
            if(Z == 0 && I == 0 && M == 0 && L == 0)
                break;
            int[] results = new int[M];
            for(int i = 0; i <= M; i++){
                results[i] = (Z*L+I) % M;
                L = results[i];
                if(i > 0){
                    for(int j = i-1; j >= 0; j--){
                        if(results[j] == results[i]){
                            answer = i - j;
                            done = true;
                            break;
                        }  
                    }
                }
                if(done)
                    break;
            }
            System.out.printf("Case %d: %dn", caseNumber, answer);
            caseNumber++;
            answer = 0;
            done = false;
        }
    }
}

									

Leave a Reply

Your email address will not be published. Required fields are marked *