TopCoder SRM 639 Div1 Easy: AliceGame (貪欲法)

問題

TopCoder Statistics - Problem Statement

解法

残っている数から引くことの出来る最大の奇数を引く。これを繰り返す。ただし。残りの数字が2になるようなパターンは避ける。

コード

public class AliceGame {

	public long findMinimumValue(long x, long y) {
		long sum = x + y;
		long n = (long) Math.sqrt(sum);
		if (n * n != sum || x == 2 || y == 2) {
			return -1;
		}

		long ans = 0;

		// 数列の最大値
		long max = 2 * n - 1;
		while (x > 0 && max > 0) {
			// max以下かつx以下の最大の奇数を求める
			if (max > x) {
				max = x;
			}
			if (max % 2 == 0) {
				max--;
			}

			// 2になるとどうしようもないので除く
			if (x - max != 2) {
				x -= max;
				ans++;
			}
			max -= 2;
		}

		if (x == 0) {
			return ans;
		} else {
			return -1;
		}

	}
}