Geek asks and answers

Calculate a series without being able to store values?

Description of the problem [ here ]

Let S be an infinite sequence of integers:

S0 = a; S1 = b;

Si = | Si-2 - Si-1 | for all i> = 2.

You have two integers a and b. You have to answer some queries about the nth element in the sequence. (Means printing the nth number in the sequence ie S (n))

(0 <= a, b <= 10 18), (1 <= q <= 100000)

What I tried (this will give a runtime error):

#include <bits/stdc++.h>
using namespace std;

long long int q,a,b,arr[100002];/*Can't declare an array of required size */

int main() {
    // your code goes here
    scanf("%lld%lld",&a,&b);
    arr[0]=a,arr[1]=b;
    scanf("%d",&q);
    int p[100002];
    long long int m = -1;//stores max index asked
    for(int i=0;i<q;i++)
    {
        scanf("%lld",&p[i]);
        m = (m>p[i])?m:p[i];
    }
    for(int i=2;i<=m;i++)//calculates series upto that index
    {
        arr[i]=abs(arr[i-1]-arr[i-2]);
    }
    for(int i=0;i<q;i++)
    {
        printf("%lld\n",arr[p[i]]);
    }
    return 0;
}

Indicated: qi corresponds to a 64-bit integer. since the index can be very large, and I cannot declare that the bit of the array is how I approach this problem (since brute force will give TLE). Thank!

+4
source share
1 answer

HA! , () :

Si Sj, i, j > 1. , , ( ), , .

( ), .

, , , " ". , .

(*) , 0. :

a) , ( ) 0, . , ...

b) . ( ), 0. (*).

: L, L, 0,...

:

3, 1, 2, 1, 1, 0, 1, 1, 0, ...
1, 3, 2, 1, 1, 0, 1, 1, 0, ...
3.5, 1, 2.5, 1.5, 1, .5, .5, 0, .5, .5, 0, ...
.1, 1, .9, .1, .8, .7, .1, .6, .5, .1, .4, .3, .1, .2, .1, .1, 0, ...

: 0, , , , 0 :

// A and B could also be negative, that wouldn't change the algorithm,
// but this way the implementation is easier
uint64_t sequence(uint64_t A, uint64_t B, size_t n) {
 if (n == 0) {
  return A;
 }
 uint64_t prev[2] = {A, B};
 for (size_t it = 1u; it < n; ++it) {
  uint64_t next =
    (prev[0] > prev[1]) ?
      (prev[0] - prev[1]) :
      (prev[1] - prev[0]);
  if (next == 0) {
   size_t remaining = n - it - 1;
   if (remaining % 3 == 0) {
    return 0;
   }
   return prev[0]; // same as prev[1]
  }
  prev[0] = prev[1];
  prev[1] = next;
 }
 return prev[1];
}

( a b, ).

A B, next == 0 std::vector, .

, , 0, .

, , ...

, :

// deciding on a concrete type is hard ...
uint64_t sequence (uint64_t A, uint64_t B, uint64_t n) {
 if (n == 0) {
  return A;
 }
 uint64_t prev[2] = {A, B};
 for (auto it = 1u; it < n; ++it) {
  auto next =
    (prev[0] > prev[1]) ?
      (prev[0] - prev[1]) :
      (prev[1] - prev[0]);
  prev[0] = prev[1];
  prev[1] = next;
 }
 return prev[1];
}

, , .

, : prev std::map ( n ). , n, . , : "" .

, . :

a
b
a-b
b-(a-b) = 2b-a
(a-b)-(b-(a-b)) = 2(a-b)-b = 2a-3b
2b-a-(2a-3b) = 5b-3a
2a-3b-(5b-3a) = 5a-8b
...

...

b: 0 1 1 2 3 5 8 ...
a: (1) 0 1 1 2 3 5 ...

... . , :

b: - + - + - ...
a: + - + - + ...

, n-

f(0) = a
f(n) = (-1)^n      * fib(n-1) * a +
       (-1)^(n-1)  * fib(n)   * b

, n- , , , :

fib(n) = (phi^n - chi^n) / (phi - chi)
   with
  phi = (1 + sqr(5)) / 2
  chi = 1 - phi

, :

unsigned long fib(unsigned n) {
 double const phi = (1 + sqrt(5)) / 2.0;
 double const chi = 1 - phi;
 return (pow(phi, n) - pow(chi, n)) / (phi - chi);
}
long sequence (long A, long B, unsigned n) {
 if(n ==0) {
  return A;
 }
 auto part_a = fib(n-1) * A;
 auto part_b = fib (n) * B;
 return (n % 2 == 0) ? (part_a - part_b) : (part_b - part_a);
}

, ( , ).

, . , . , .

, , .. ( ) .

+4

More articles:


All Articles