Siruri2 | www.pbinfo.ro

Fibonacci, a famous Italian mathematician in the Mediaeval Era, had discovered
a series of natural numbers with multiple applications, a string that
bears his name:

Fibonacci (n) = 1, if n = 1 or n = 2



Fibonacci (n) = Fibonacci (n−1) + Fibonacci (n−2), if n>2

Fascinated by Fibonacci's line, and especially the applications of
this string in nature, Iccanobif, a mathematician in the making,
created a string and he named him:

Iccanobif (n) = 1, if n = 1 or n = 2



Iccanobif (n) = reversed (Iccanobif (n-1)) + reversed (Iccanobif (n-2)), if n > 2

Obtaining the following rows:

Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Iccanobif: 1, 1, 2, 3, 5, 8, 13, 39, 124, 514, 836, ...

Iccanobif now wonders which number has more natural
divisors: the n-th term in the Fibonacci row or the n-th term in the
Iccanobif row. Requirements:

Write a program that reads n natural number and displays:

a) the n-th term in Fibonacci's row and its number of divisors

b) the n-th term of the Iccanobif string and its number of divisors

Input data

The input file siruri2.in contains on the first line a natural number p.
For all input tests, the p number can only have a value of 1 or value
2. A natural number n is found on the second line of the file.

Output data

If the value of p is 1, only a) of the requirements will be solved. In
this case, in the output file siruri2.out, the n-th term in Fibonacci
string and its number of divisors will be written.

If the value of p is 2, only the point b) of the requirements will be
solved. In this case, in the output file siruri2.out the n-th term
in Iccanobif string and its number of divisors will be written
Restrictions and clarifications

1 ≤ n ≤ 50

For the correct resolution of the first requirement, 50% of the score is 

awarded, and 50% of the score is awarded for the second requirement.

Limits:
- time: 1 second;
- memory: 2 MB/ 2 MB.

Example 1

siruri2.in

1 8

siruri2.out

21 4

Example 2

siruri2.in

2 9

siruri2.out

124 6

Explanations

For the first example: The eighth term in Fibonacci's string is 21 and
21 has 4 divisors. (p being 1 solves only requirement a)

For the second example: The ninth term in Iccanobif's string is 124,
and 124 has six divisors. (p being 2 solves only requirement b)

Here is my code, which doesn't execute all given tests in time (exceeds time limit for 3 tests):

#include <iostream>

#include <fstream>

using namespace std;

ifstream in("siruri2.in");

ofstream out("siruri2.out");

void numOfDivisors (long long n)

{

    long numOfDivisors = 1, factor = 2;

    while (factor * factor <= n)

    {

        if (!(n % factor))

        {

            long exponent = 0;

            while (!(n % factor))

            {

                n /= factor;

                exponent ++;

            }

            numOfDivisors *= exponent + 1;

        }

        if (factor == 2)

            factor = 3;

        else factor += 2;

    }

    if (n > 1)

    {

        numOfDivisors *= 2;

    }

    out << numOfDivisors;

}

long long inverted (long long a)

{

    long long b=0;

    while (a)

    {

        b = b * 10 + a % 10;

        a /= 10;

    }

    return b;

}

void fibonacci (short ord)

{

    long long a = 1, b = 1;

    if (ord < 3)

        {out << "1 1";}

    else

    {

        ord -= 2;

        while (ord)

        {

            a+=b;

            ord--;

            if (!ord)

            {

                out << a << " ";

                numOfDivisors(a);

                break;

            }

            else

            {

                b+=a;

                ord--;

                if (!ord)

                {

                    out << b << " ";

                    numOfDivisors(b);

                }

            }

        }

    }

}

void iccanobif (short ord)

{

    long long a = 1, b = 1;

    if (ord < 3)

        out << "1 1";

    else

    {

        ord -= 2;

        while (ord)

        {

            a = inverted(a) + inverted(b);

            ord--;

            if (!ord)

            {

                out << a << " ";

                numOfDivisors(a);

                break;

            }

            else

            {

                b = inverted(a) + inverted(b);

                ord--;

                if (!ord)

                {

                    out << b << " ";

                    numOfDivisors(b);

                }

            }

        }

    }

}

int main()

{

    short requirement, ord;

    in >> requirement >> ord;

    if (requirement == 1)

        fibonacci(ord);

    else

        iccanobif(ord);

}

Efficiency

numOfDivisors()

• numOfDivisors and exponent do not need to be long. Using int is sufficient, and should be slightly faster.




• n is a long long, where as factor is only a long. So factor will be repeated promoted to a long long for the operations n % factor and n /= factor. You might find a speed improvement by actually declaring factor as a long long to avoid the repeated type promotion.




• factor is only a long, so factor * factor is also only a long, and may overflow when looping while (factor * factor <= n). Using a long long will avoid this, which may prevent the loop from running for a long time if n is prime and larger than a long.




• If n % factor == 0, then the exponent counting inner loop is entered, and the first thing that is done is n % factor, which is already known to be zero. Using a do { ... } while (!(n % factor)); loop will prevent the redundant calculation.




• The outer loop starts at n=2, and has an if statement to choose between incrementing n by 2, or setting it to 3. If 2 was handled as a special case, then the loop could unconditionally increment by 2, eliminating the if statement for another speed gain. To handle the 2^exponent case, simply count the number of trailing zeros in the binary representation of n.




• Your factor finder is testing all odd numbers whose square is less than n. You only need to test factor numbers which are prime. Other than 2 & 3, all prime numbers can be generated from 6k-1 and 6k+1. Or maybe use a prime sieve ... you are allowed 2MB of memory ...

iccanobif()

You are computing...

while (...) {

    a = inverted(a) + inverted(b);   // #1

    ...

    b = inverted(a) + inverted(b);   // #2

}

When you are executing statement #2, you've already computed inverted(b) during statement #1, above. If you cached that value, you wouldn't need to invert it a second time.

Similarly, when computing statement #1 in subsequent loops, you've already computed inverted(a) during statement #2, below, on the previous iteration. If you cached that value, you wouldn't need to invert it a second time.

General

Add vertical white space after #includes, after global variables, and between functions.

Add whitespace around operators. Ie, a += b; instead of a+=b;.

Don't use using namespace std;. Simply use:

std::ifstream in("...");

std::ofstream out("...");

numOfDivisors() should return the answer, not print the answer.

fibonacci() should return the Fibonacci value, not print the value and call another function which also has the side-effect of additional printing. Ditto for iccanobif().

main() is declare to return an int, but doesn't return anything.

If the above changes were made, then in and out don't need to be global variables; they could be made local to the main function:

void main() {

   std::ifstream("siruri2.in");

   std::ofstream("siruri2.out");



   short requirement, ord;

   in >> requirement >> ord;



   long long n = requirement == 1 ? fibonacci(ord) : iccanobif(ord);



   int num_divisors = numOfDivisors(n);



   out << n << ' ' << num_divisors;

}

constexpr is your friend

You may feel like it's cheating, but C++ allows you to pre-compute the answers really easily with the constexpr keyword. A constexpr value must be known at compile-time, and a constexpr function, given a constexpr argument, will be executed at compile-time. It means that you can easily compute and store the 50 first terms of the fibonacci progression -and of the iccanobif progression for that matter- at compile-time. And you can of course calculate how many divisors they have. The beauty of it is that you don't need the most efficient algorithms: since all the work is done once and for all during compilation, being more readable and maintainable could very well be the right choice.

Here's a quickly-written constexpr answer to your problem: https://wandbox.org/permlink/qAtXS15Ir9c4vYgG

avoid duplicating code

Copy-and-paste is an anti-pattern because it is hard to maintain: if you find an improvement in your fibonacci function, you'll need to replicate it in the iccanobif function; at some point, you'll forget to copy, or to modify your copy. That's why you should try to factorize your code. In this case, both functions share most of their code; the only thing iccanobif does in addition is to reverse the previous terms. So you can rewrite both functions into one that decides whether to reverse the previous terms according to a function parameter.