joj 2431: Shift and Increment

2431: Shift and Increment

Result
TIME Limit
MEMORY Limit
Run Times
AC Times
JUDGE
5s
16384K
1362
215
Standard
Shift and increment is the basic operations of the ALU (Arithmetic Logical Unit) in CPU. One number can be transform to any other number by these operations. Your task is to find the shortest way from x to 0 using the shift (*=2) and increment (+=1) operations. All operations are restricted in 0..n, that is if the result x is greater than n, it should be replace as x%n.

Input and Output

There are two integer x, n (n <=1000000)

Sample Input

2 4
3 9

Sample Output

1
3

Problem Source: provided by skywind
#include #include using namespace std; int a[1000003];//각 노드를 저장하는 수 intvis[100003]={0,1};//모든 노드의 수가 검색되었는지 아닌지를 판단하는 데 쓰인다.intmain() {intx, n;while(scanf('%d%d', &x, &n)=2) {memset(vis, 0, sizeof(vis));if(x>=n)x=x%n, intbeg=0, end=0;//이것은 검색의 각 층의 시작점과 끝점인 intcnt=0,number=1;//cnt로 층수를 기록하고 number는 모든 나타난 숫자를 기록합니다.])//vis[0]==1에서 n을 찾은 것과 같다{cnt++;beg=end;end=number;for(int i=beg;i=n)k=k%n;if(!vis[k])//다음 층 왼쪽으로 확장 {a[number++]=k;vis[k]=1;    }     k=a[i]+1;     if(k>=n)      k%=n; if(!vis[k])//다음 층 오른쪽으로 {a[number++]=k;vis[k]=1;    }    }       }   printf("%d",cnt);  }  return 0; }