結果

問題 No.3 ビットすごろく
コンテスト
ユーザー Masahiro Hayashi
提出日時 2015-06-06 00:56:41
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 32 ms / 5,000 ms
コード長 2,836 bytes
コンパイル時間 2,363 ms
コンパイル使用メモリ 110,080 KB
実行使用メモリ 26,292 KB
最終ジャッジ日時 2024-07-01 07:24:22
合計ジャッジ時間 3,282 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.

ソースコード

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