結果

問題 No.3 ビットすごろく
コンテスト
ユーザー Masahiro Hayashi
提出日時 2015-05-31 18:38:47
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 3,072 bytes
コンパイル時間 863 ms
コンパイル使用メモリ 115,404 KB
実行使用メモリ 26,012 KB
最終ジャッジ日時 2024-07-06 13:04:40
合計ジャッジ時間 9,966 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 List<int> ();

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

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

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

				done.Add(x.Item);
				foreach(var y in this.neiboughrNodes(N, x.Item)){
					if (!done.Contains(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