結果

問題 No.3 ビットすごろく
ユーザー fgwiebfaoish
提出日時 2020-02-15 03:19:41
言語 C#
(csc 3.4.0-beta4-19569-03)
結果
AC  
実行時間 28 ms
コード長 3,166 Byte
コンパイル時間 920 ms
使用メモリ 17,688 KB
最終ジャッジ日時 2020-02-15 03:19:44

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 24 ms
17,508 KB
2.txt AC 24 ms
17,432 KB
3.txt AC 24 ms
17,616 KB
4.txt AC 24 ms
17,588 KB
5.txt AC 24 ms
17,516 KB
6.txt AC 24 ms
17,504 KB
7.txt AC 24 ms
17,364 KB
8.txt AC 24 ms
17,560 KB
9.txt AC 24 ms
17,600 KB
10.txt AC 24 ms
17,380 KB
11.txt AC 28 ms
17,488 KB
12.txt AC 24 ms
17,380 KB
13.txt AC 24 ms
17,600 KB
14.txt AC 24 ms
17,688 KB
15.txt AC 28 ms
17,420 KB
16.txt AC 24 ms
17,328 KB
17.txt AC 24 ms
17,340 KB
18.txt AC 24 ms
17,544 KB
19.txt AC 24 ms
17,384 KB
20.txt AC 24 ms
17,560 KB
challenge01.txt AC 24 ms
17,352 KB
challenge02.txt AC 24 ms
17,484 KB
challenge03.txt AC 24 ms
17,584 KB
system_test1.txt AC 24 ms
17,544 KB
system_test2.txt AC 24 ms
17,520 KB
system_test3.txt AC 24 ms
17,512 KB
system_test4.txt AC 24 ms
17,600 KB
system_test5.txt AC 24 ms
17,680 KB
system_test6.txt AC 24 ms
17,508 KB
system_test7.txt AC 24 ms
17,680 KB
system_test8.txt AC 24 ms
17,408 KB
テストケース一括ダウンロード
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.4.0-beta4-19569-03 (82f2e254)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		var h=new int[n+1];
		var qu=new Queue<int>();
		qu.Enqueue(1);
		h[1]=1;
		while(qu.Count>0){
			var e=qu.Dequeue();
			int i=bits(e);
			if(e+i<=n&&h[e+i]==0){
				qu.Enqueue(e+i);
				h[e+i]=h[e]+1;
			}
			if(e-i>1&&h[e-i]==0){
				qu.Enqueue(e-i);
				h[e-i]=h[e]+1;
			}
		}
		Console.WriteLine("{0}",h[n]==0?-1:h[n]);
	}
	static int bits(long bits){
		bits=(bits&0x55555555)+(bits>>1&0x55555555);
		bits=(bits&0x33333333)+(bits>>2&0x33333333);
		bits=(bits&0x0f0f0f0f)+(bits>>4&0x0f0f0f0f);
		bits=(bits&0x00ff00ff)+(bits>>8&0x00ff00ff);
		return (int)((bits&0x0000ffff)+(bits>>16&0x0000ffff));
	}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}
0