import java.util.*;

public class Main {
    static final int MAX_NUMBERS = 100;
    static final int GOAL = 100;
    static final int NUMBER_OF_RUNS = 1000;

    static int current = 0;
    static int numMoves = 0;

	public static void main(String[] args) {
	    int totalNumMoves = 0;
	    for (int i = 0; i < NUMBER_OF_RUNS; i++) {
	        int numMovesForRun = run();
	        totalNumMoves += numMovesForRun;
	    }

	    double averageNumMoves = 1.0 * totalNumMoves / NUMBER_OF_RUNS;
	    System.out.println("Average number of moves: " + averageNumMoves);
	}

	private static int run() {
	    current = 0;
	    numMoves = 0;

	    while (current != GOAL) {
	        if (shouldRandom()) {
	            random();
	        } else {
	            next();
	        }
	        numMoves++;
	    }

	    return numMoves;
	}

	private static boolean shouldRandom() {
	    // implement your strategy here
	    double distanceToGoal = computeDistanceToGoal();

	    // where X is distance to goal
	    double oddsOfGettingFartherAfterXRandoms = Math.pow(1 - distanceToGoal / MAX_NUMBERS, distanceToGoal);
	    if (oddsOfGettingFartherAfterXRandoms < 1.0 * distanceToGoal / MAX_NUMBERS) {
	        return true;
	    } else {
	        return false;
	    }
	}

	private static void next() {
	    current++;
	}

	private static void random() {
	    Random rng = new Random();
	    current = rng.nextInt(100) + 1; // +1 beacuse Random starts at 0
	}

	private static int computeDistanceToGoal() {
	    if (GOAL > current) {
	        return GOAL - current;
	    } else {
	        return MAX_NUMBERS - current + GOAL;
	    }
	}
}