Two integer variables L and R are given. Their initial content is 0 and 1, respectively, and it can be manipulated using the following unfold operations:
* operation 'L' is the assignment of value 2*L−R to variable L; * operation 'R' is the assignment of value 2*R−L to variable R.
An integer N is given. An unfold sequence for N is a sequence of unfold operations such that, after performing these operations, either L = N or R = N.
For example, consider N = 21 and the following sequence of unfold operations: ['L', 'L', 'R', 'L', 'R']. This is an unfold sequence for N, because:
* after the first operation L becomes −1 (R remains 1); * after the second operation L becomes −3 (R remains 1); * after the third operation R becomes 5 (L remains −3); * after the fourth operation L becomes −11 (R remains 5); * after the fifth operation R becomes 21 (L remains −11).
After the last operation, R = N. The sequence consists of five operations, and no shorter unfold sequence for N exists.
Write a function
int interval_unfold_count(int N); int interval_unfold_count(int N); int interval_unfold_count(int N); class Solution { int interval_unfold_count(int N); } class Solution { public int interval_unfold_count(int N); } function interval_unfold_count(N); function interval_unfold_count(N) function interval_unfold_count($N); function interval_unfold_count(N : longint) : longint; def interval_unfold_count(N) sub interval_unfold_count { my ($N)=@_; ... } def interval_unfold_count(n) Private Function interval_unfold_count ( N As Integer ) as Integer
that, given an integer N, returns the length of the shortest unfold sequence for N. The function should return −1 if no unfold sequence for N exists.
For example, given N = 21, the function should return 5, as explained above.
....
po krótce: wtf? czy jest jakiś sposób na znalezienie sekwencji L/R?
ponizej wklejam coś, co być moze otarło sie o rozwiazanie, ale nie do końca.
int do_it(int N,int l,int r){
if(l>N || r>N)return -1;
if(l==N || r==N)return 0;
int ret=do_it(N,2*l-r,r);
if(ret==-1)ret=do_it(N,l,2*r-l);
if(ret>-1)ret++;
return ret;
}
int interval_unfold_count(int N){
int L=0;
int R=0;
return do_it(N,L,R);
}