結果

問題 No.3 ビットすごろく
ユーザー bambambambam
提出日時 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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0