dziwne rozwinięcie liczby

0

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);
}
0
21=RLRLL
   10100=20

1 użytkowników online, w tym zalogowanych: 0, gości: 1