using System; using System.Collections; using System.Collections.Generic; using System.Linq; public class Hello { public static void Main() { string line = System.Console.ReadLine().Trim(); int N = int.Parse(line); int[] dist = new int[N + 1]; Queue que = new Queue(); que.Enqueue(1); dist[1] = 1; while(que.Any()) { int now = que.Dequeue(); string bin = Convert.ToString(now, 2); int bit = bin.Where(c => c == '1').Count(); if (now - bit > 0 && dist[now - bit] == 0)//now-bit数が0以上,未訪問の場合 { dist[now - bit] = dist[now] + 1;//点の距離をnowから+1の距離で確定する que.Enqueue(now - bit);//次の位置をqueueに入れる } if (now + bit <= N && dist[now + bit] == 0)//now+bit数がN以下,未訪問の場合 { dist[now + bit] = dist[now] + 1;//点の距離をnowから+1の距離で確定する que.Enqueue(now + bit);//次の位置をqueueに入れる } } if (dist[N] == 0) { System.Console.WriteLine("-1"); return; } System.Console.WriteLine(dist[N]); } }