結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2017-03-19 21:12:52 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 30 ms / 5,000 ms |
コード長 | 1,032 bytes |
コンパイル時間 | 2,213 ms |
コンパイル使用メモリ | 111,896 KB |
実行使用メモリ | 27,044 KB |
最終ジャッジ日時 | 2024-07-01 08:37:23 |
合計ジャッジ時間 | 4,115 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; class Program { static int CountBit(int n) { var cnt = 0; for (var i = 0; n > 0; i++) { if (n % 2 == 1) cnt++; n /= 2; } return cnt; } static void Main() { const int inf = 1145141919; var n = int.Parse(Console.ReadLine()); var d = new int[n + 1].Select(x => inf).ToArray(); var que = new Queue<int>(); que.Enqueue(1); d[1] = 1; while (que.Count > 0) { var p = que.Dequeue(); if (p == n) break; for (var i = 0; i < 2; i++) { var np = i == 0 ? p + CountBit(p) : p - CountBit(p); if (1 <= np && np <= n && d[np] == inf) { que.Enqueue(np); d[np] = d[p] + 1; } } } Console.WriteLine(d[n] == inf ? -1 : d[n]); return; } }