Gfrktyl

extindere | www.pbinfo.ro

Consider the operation (bar on top): {1; 2} → {1; 2} so that 1 (bar on top) = 2, 2 (bar on top) = 1. The
operation extends to any sequence formed by digits 1 and 2, for
example (bar on top of whole string) 1211212121 = 2122121212. We consider the infinite string to be
formatted with numbers 1 and 2, incrementally generated by extension
by the following concatenation rule: s(1) = 1221, s(2) = 1221 2112 2112 1221,
..., s(k + 1) = s(k) (bar on top)s(k) (bar on top)s(k) s(k), ..., for any natural number k>0.

Requirement

Write a program that determines and writes a number of the s-string so
that the number of steps in the program is proportional to log2 (n)
(logarithmic time complexity by n).

Input data

The extension.in file contains the natural number n on the first line.

Output data

The output file extindere.out will contain on the first line the
number c representing the n-th digit of the string formed according to
the rule specified above.
Restrictions and clarifications

1 ≤ n ≤ 1,000,000

*Limits: *

 - time: 0.01 seconds;

 - memory: 0.1 MB/ 0.1 MB.

Example

extindere.in

18

extindere.out

1

Explanation

To find out the digit in n = 18, 3 expansion steps are required. The
generated string is 1221211221121221 2112122112212112 2112122112212112
1221211221121221. The digit in position 18 is 1.

Here is my code, which goes way out of memory limit and I'm pretty sure out of time, too:

#include <iostream>

#include <fstream>

using namespace std;

ifstream in("extindere.in");

ofstream out("extindere.out");

void extension (long numOfExt, char v)

{

    long n = 4;

    while (numOfExt)

    {

        n *= 4;

        numOfExt --;

        for (long i = n / 4 + 1; i <= (n / 4) * 2; i ++)

        {

            if (v[i - n / 4] == '1')

                v[i] = '2';

            else

                v[i] = '1';

        }

        for (long i = (n / 4) * 2 + 1; i <= (n / 4) * 3; i ++)

        {

            v[i] = v[i - n / 4];

        }

        for (long i = (n / 4) * 3 +1; i <= n; i ++)

        {

            v[i] = v[i - (n / 4) * 3];

        }

    }

}

int main()

{

    long position, positionCopy, numOfExt = 0;

    char v[1000001];

    in >> position;

    for (long i = 1; i <= 4; i ++)

    {

        v[1]='1';

        v[2]='2';

        v[3]='2';

        v[4]='1';

    }

    positionCopy = position;

    while (positionCopy >= 4)

    {

        positionCopy /= 4;

        numOfExt ++;

    }

    extension (numOfExt, v);

    out << v[position];

}