Euler Projesi 219. Soru

A ve B bit dizileri olsun (0 ve 1 sayı dizileri). Eğer A, B'nin sol uzunluk(A) bitine eşitse, A'ya B'nin bir öneki denir. Örneğin, 00110 dizisi 001101001 dizisinin bir öneki fakat 00111 veya 100110 dizilerinin öneki değildir.

Herhangi bit dizisinin diğerinin öneki olmadığı n farklı bit dizisi kümesine n boyutlu önek-bağımsız kod adı verilir. Örneğin, $$0000, 0001, 001, 01, 10, 11$$ dizisi 6 boyutlu önek-bağımsız bir koddur.

Şimdi '0' bitini iletmenin maliyeti 1 sent ve '1' bitini iletmenin maliyeti 4 sent olsun. Bu durumda yukarıda verilen önek-bağımsız kodu iletmenin maliyeti 35 sent olur, ki bu aslında belitilen maliyet hesabına göre olası en ucuz maliyetli olanıdır. Yani Cost(6)=35 yazılır.

Bu durumda Cost($10^9$)=?

Cevap: 64564225042

C++:

#include 
#include 


int main()
{
  int n1,n2,n3,n4,n5,m1,m2,m3,m4,m5;
  n1=1;
  n2=0;
  n3=0;
  n4=1;
  n5=0;
  long long int c=1;
  long long int totcost;
  long long int wanted=1000000000ll;
  long long int i=2;
  while(i+n1+1<=wanted)
    {
      i+=n1+1;
      m1=n2+n1-1;m2=n3+1;m3=n4;m4=n5+n1;m5=1;
      n1=m1;
      n2=m2;
      n3=m3;
      n4=m4;
      n5=m5;
      c++;
      
    }
  long long int diff=wanted-i;

      n1-=diff;
      n2+=diff;
      n5+=diff;     
    
   totcost=c*n1+(c+1)*n2+(c+2)*n3+(c+3)*n4+(c+4)*n5;

   printf("%lld\n",totcost);
 
}

C#:

static long Cost(long max)
 {
 checked
  {
  long[] a = new long[4] { 1, 1, 1, 2 };

  long n=0, an, cost=5;
  long pos = 2,step = 6;

  while (pos < max)
   {
   if (n >= 4)
    an = a[(n - 1) & 3] + a[(n - 4) & 3];
   else
    an = a[n&3];
   a[n&3] = an;
   ++n;
   if (pos + an > max)
    {
    cost += step * (max - pos);
    pos = max;
    }
   else
    {
       cost += step*an;
    pos += an;
    step++;
    }
   }
  return cost;
  }
 }
static public void Run(bool sample)
 {
 Console.WriteLine("Cost {0}=64564225042",Cost(1000000000));
 }

Java:

private static long s(int n) {
    long m = 0, f0 = 1, f1 = 0, f2 = 0, f3 = 0, f4 = 0;
    long remaining = n - 1;
    while (remaining > 0) {
        if (remaining >= f0) {
            // advance the sequence by f0
            remaining = remaining - f0;
            f1 = f1 + f0;
            f4 = f4 + f0;
            f0 = f1;
            f1 = f2;
            f2 = f3;
            f3 = f4;
            f4 = 0;
            m = m + 1;
        } else {
            // advance the sequence by remaining
            f0 = f0 - remaining;
            f1 = f1 + remaining;
            f4 = f4 + remaining;
            remaining = 0;
        }
    }
    return f0*m + f1*(m+1) + f2*(m+2) + f3*(m+3) + f4*(m+4);
}

Haskell:

problem219' max = sum.map (\(x,y) -> x*y) $ zip (elems as) [4..bound+3]                     
    where   lim n = sum [ binom (n-3*k) (k+1) | k<-[0..n `div` 4]] -- A098578
            bound = 1 + (fromInteger.head$[k| k<-[1..], lim k > max ] )
            as = as' 5 3 $ listArray (1,bound) ([0,1,1,1] ++ replicate (bound-4) 0) -- A003269
                where as' n s arr | s < max = let a = arr!(n-1) + arr!(n-4) 
                                              in as' (n+1) (s+a) (arr//[(n,a)])
                                  | otherwise = arr//[(n-1,arr!(n-1) - s + max - 1)]

Mathematica:

len = 10^9;
set = {1, 0, 0, 0, len - 1};
a = 0;
While[set[[5]] > 0,
  set = {set[[2]] + set[[1]], set[[3]], set[[4]], set[[1]], 
    set[[5]] - set[[1]]};
  a++];
Sum[(a + i - 1)*set[[i]], {i, 5}]

Maple:

> fiboA:=t->[t[1]+t[4],t[1..3][]]:cost:=proc(n)
> local c,f,i,ta;
> c:=5*n-5;
> f:=[1,0,0,0];
> ta:=1; i:=n-2;
> while i>0 do
>   f:=fiboA(f);
>   c:=c+ta*f[1];
>   i:=i-f[1];
>   ta:=ta+1
> od;
> c+i*(ta-1)
> end:
> 
> cost(10^9);
                             64564225042

> t:=time(): cost(10^10000): time()-t;
                                1.562