結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2016-02-26 11:08:29 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 343 ms / 5,000 ms |
コード長 | 680 bytes |
コンパイル時間 | 815 ms |
コンパイル使用メモリ | 108,928 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-12 03:07:30 |
合計ジャッジ時間 | 4,582 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import std.stdio, std.conv, std.string, std.range, std.math, std.bigint, std.algorithm, core.bitop; enum INF = int.max; void main() { auto N = readln.strip.to!int; auto dice = iota(N + 1).map!(e => popcnt(e)).array; auto memo = new int[](N + 1); memo[] = INF; int solve(int i, int c) { if (i < 1 || i > N || memo[i] < c) return INF; if (i == N) return c; memo[i] = c; auto f = solve(i + dice[i], c + 1); auto b = solve(i - dice[i], c + 1); return min(f, b); } auto ans = solve(1, 1); (ans == INF ? -1 : ans).writeln; }