結果

問題 No.3 ビットすごろく
ユーザー Masahiro HayashiMasahiro Hayashi
提出日時 2015-06-06 00:56:41
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 65 ms / 5,000 ms
コード長 2,836 bytes
コンパイル時間 2,411 ms
コンパイル使用メモリ 111,180 KB
実行使用メモリ 22,872 KB
最終ジャッジ日時 2023-09-13 23:13:04
合計ジャッジ時間 5,784 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
20,980 KB
testcase_01 AC 59 ms
20,776 KB
testcase_02 AC 59 ms
18,764 KB
testcase_03 AC 61 ms
20,780 KB
testcase_04 AC 60 ms
22,836 KB
testcase_05 AC 62 ms
22,816 KB
testcase_06 AC 60 ms
20,744 KB
testcase_07 AC 60 ms
20,764 KB
testcase_08 AC 60 ms
20,808 KB
testcase_09 AC 62 ms
22,820 KB
testcase_10 AC 63 ms
20,696 KB
testcase_11 AC 61 ms
20,780 KB
testcase_12 AC 61 ms
20,864 KB
testcase_13 AC 62 ms
20,760 KB
testcase_14 AC 61 ms
20,920 KB
testcase_15 AC 63 ms
22,768 KB
testcase_16 AC 63 ms
20,900 KB
testcase_17 AC 65 ms
20,772 KB
testcase_18 AC 62 ms
22,872 KB
testcase_19 AC 63 ms
22,756 KB
testcase_20 AC 61 ms
22,828 KB
testcase_21 AC 58 ms
20,860 KB
testcase_22 AC 63 ms
22,808 KB
testcase_23 AC 64 ms
22,788 KB
testcase_24 AC 63 ms
20,696 KB
testcase_25 AC 63 ms
20,760 KB
testcase_26 AC 57 ms
18,808 KB
testcase_27 AC 62 ms
20,800 KB
testcase_28 AC 62 ms
20,764 KB
testcase_29 AC 62 ms
20,704 KB
testcase_30 AC 60 ms
22,816 KB
testcase_31 AC 59 ms
20,748 KB
testcase_32 AC 62 ms
20,776 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Application
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			new MainClass ().Calc ();
		}

		public MainClass ()
		{
		}
		private class Pair
		{
			public readonly int Distance;
			public readonly int Item;

			public Pair (int n, int d)
			{
				this.Item = n;
				this.Distance = d;
			}
		}

		public void Calc ()
		{
			var scan = new Scanner ();

			var N = scan.NextDigit ();
			var done = new Dictionary<int, int> ();

			var queue = new Queue<Pair> ();
			queue.Enqueue (new Pair (1, 1));

			while (queue.Count > 0) {
				var x = queue.Dequeue ();

				if (x.Item == N) {
					Console.WriteLine (x.Distance);
					return;
				}

                if (!done.ContainsKey(x.Item))
                {
                    done.Add(x.Item, 0);

                    foreach (var y in this.neiboughrNodes(N, x.Item))
                    {
                        if (!done.ContainsKey(y))
                            queue.Enqueue(new Pair(y, x.Distance + 1));
                    }
                }
			}

			Console.WriteLine (-1);
		}

		List<int> neiboughrNodes (int N, int i)
		{
			var b1 = bit (i);
			var res = new List<int> ();

			if (i + b1 <= N)
				res.Add (i + b1);

			if (i - b1 > 1)
				res.Add (i - b1);

			return res;
		}

		int bit (int i)
		{
			var c = 0;

			while (i > 0) {

				if ((i & 1) > 0)
					c++;

				i = i >> 1;
			}

			return c;
		}

		void WriteLine (object o)
		{
			System.Console.WriteLine (o.ToString ());
		}

		void WriteEnum<T> (IEnumerable<T> l)
		{
			WriteLine (JoinList (l));
		}

		string JoinList<T> (IEnumerable<T> l)
		{
			return string.Join (" ", l.Select (x => x.ToString ()).ToArray ());
		}
	}

	class Scanner
	{
		public int[] NextDigits (int count)
		{
			return Enumerable.Range (0, count)
                .Select (x => NextDigit ()).ToArray ();
		}

		public string NextToken ()
		{
			int i;
			var r = new List<char> ();

			while ((i = System.Console.Read()) >= 0) {
				var c = Convert.ToChar (i);

				if (IsSpace (c) && r.Count > 0)
					break;

				r.Add (c);
			}

			return new string (r.ToArray ());
		}

		bool IsSpace (char c)
		{
			if (char.IsWhiteSpace (c))
				return true;

			return false;
		}

		public int NextDigit ()
		{
			var token = NextToken ();

			return int.Parse (token);
		}
	}

	class Reader
	{
		public string Item ()
		{
			return Items () [0];
		}

		public String[] Items ()
		{
			return this.Items (' ');
		}

		public String[] Items (char c)
		{
			return System.Console.ReadLine ().Split (c);
		}

		public int Int ()
		{
			return Ints (' ') [0];
		}

		public int[] Ints ()
		{
			return this.Ints (' ');
		}

		public int[] Ints (char c)
		{
			return Items (c).Select (x => int.Parse (x)).ToArray ();
		}
	}
}
0