結果

問題 No.3 ビットすごろく
コンテスト
ユーザー bambam
提出日時 2019-08-22 11:20:50
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,147 bytes
コンパイル時間 2,572 ms
コンパイル使用メモリ 78,032 KB
実行使用メモリ 61,000 KB
最終ジャッジ日時 2024-10-12 03:44:57
合計ジャッジ時間 9,626 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;

public class Main {
	static boolean memo[];
	static int ans, min;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n = sc.nextInt();
		int map[] = new int[n + 1];
		int cnt;
		String bin;
		for (int i = 1; i <= n; i++) {
			cnt = 0;
			bin = Integer.toBinaryString(i);
			for (int j = 0; j < bin.length(); j++) {
				if (bin.charAt(j) == '1') {
					cnt++;
				}
			}
			map[i] = cnt;
		}
		memo = new boolean[n + 1];
		memo[1] = true;
		ans = 0;
		min = Integer.MAX_VALUE;
		solve(map, 1, n);
		if (min == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(min + 1);
		}
	}

	private static void solve(int[] map, int s, int n) {
		if (s == n) {
			min = Math.min(min, ans);
			return;
		}

		if (s + map[s] <= n && !memo[s + map[s]]) {
			memo[s + map[s]] = true;
			ans++;
			solve(map, s + map[s], n);
			ans--;
			memo[s + map[s]] = false;
		}
		if (s - map[s] > 0 && !memo[s - map[s]]) {
			memo[s - map[s]] = true;
			ans++;
			solve(map, s - map[s], n);
			ans--;
			memo[s - map[s]] = false;
		}
	}
}
0