Codechef: Crazy Malvika discovers Crazy Fibonacci function

Codechef: Crazy Malvika discovers Crazy Fibonacci function

Now I’ve enough karma to start a new thread, so thank you people for upvotes.

I read the CHN08 - Editorial, and after that I came up this solution which works very fine. But I’m not able to understand why I have to add modular(10^7+1) to temp when temp<0. I’m talking about this line.

if(temp<0)
    temp=temp+M;

That is, because the % operator gives negative result for negative numbers. For example -4%10 = -4, but you need 6, so you have to add 10.

It isn’t the same in all programming languages, in some of them, the operator always gives positive result. Find more information here.

1 Like

It is due to this constraint-

Output the answers modulo 10^9+7.

What the setter wanted to convey was, he always wants a positive answer. And since answer may be large, output the remainder with 10^9 +7. In case the number is negative, he did not want you to print the negative remainder, and hence you add 10^9+7 till number becomes positive and proceed.

Alternatively, always taking absolute values should also do fine according to me. 10^9+7 - [abs(f(n) )%10^9+7]

1 Like

Please help me figure out the problem with my code. I am getting runtime error. This is my solution.

link text

Why do I get SIGSEGV runtime error for this code?here is my code
https://www.codechef.com/viewsolution/14165238.check it once

Why do I get SIGSEGV runtime error for this code?here is my code https://www.codechef.com/viewsolution/14165238
check it once

@dimpu123

instead of using bruteforce try to write the efficient code by finding the pattern.pattern repeats for every 6 numbers

I would appreciate if anyone could help me to show me the problem with my code. I got the wrong answer but I think my logic is correct.

code link

Plz check if your code is set to ‘private’. I cant access it.

Now you’re good to go. http://ideone.com/y84Y1d

In problem statement, it’s not distinctly mentioned that f(n) can’t be negative. Then why to make it positive.

Where in problem statement it is written that f(n) can’t be -ve? I don’t see it.

F(n) can be negative, but its of no conern. Theres a difference b/w what f(n) can be and what the setter wants us to print. Check his sample case, he made it clear there that if f(n) is negative, you need to print [f(n)%10^9+7]+10^9+7

Also, why would u make it positive if setter gives “f(n) is never negative.” :wink:

I got it. Thanks

Happy to help dear :slight_smile:

Firstly, why is there a “%c” in your scanf?

Also, your approach, although correct, needs improvement. Since n (or in your program, x) can range from 1 to 10^9, its very easy to exhaust ‘recursion depth’. Infinite/too large recursion can give runtime error/SIGSEV error.