dirichle.java

package com.game;

import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Dirichle {

	public static class State {

		public final long a;
		public final long b;

		public State(long a, long b) {
			this.a = a;
			this.b = b;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o) return true;
			if (o == null || getClass() != o.getClass()) return false;

			State state = (State) o;

			if (a != state.a) return false;
			return b == state.b;

		}

		@Override
		public int hashCode() {
			int result = (int) (a ^ (a >>> 32));
			result = 31 * result + (int) (b ^ (b >>> 32));
			return result;
		}
	}

	public boolean dfs(State s, final long n) {
		if (visited.containsKey(s)) {
			return visited.get(s);
		}
		if (Math.pow(s.a, s.b) >= n) {
			return true;
		}
		boolean addARes = dfs(new State(s.a + 1, s.b), n);
		visited.put(new State(s.a + 1, s.b), addARes);
		if (!addARes) {
			return true;
		}
		boolean addBRes = dfs(new State(s.a, s.b + 1), n);
		visited.put(new State(s.a, s.b + 1), addBRes);
		if (!addBRes) {
			return true;
		}
		return false;
	}

	private final Map<State, Boolean> visited = new HashMap<>();

	public void solve(int testNumber, Scanner in, PrintWriter out) {
		long a = in.nextLong();
		long b = in.nextLong();
		long n = in.nextLong();

		if (a == 1) {
			if (Math.pow(2, b) >= n) {
				out.print("Missing");
				return;
			}
		}

		if (b == 1) {
			if (Math.pow(a, 2) >= n) {
				out.println((n - a) % 2 == 0 ? "Masha" : "Stas");
				return;
			}
		}

		out.println(dfs(new State(a, b), n) ? "Masha" : "Stas");
	}
}