It's mean you are checking condition if variable N = 45  or N = 5,6,7,8
then go to do statement below your condition

N = 45 -> answer = 2269806340
N = 5 -> answer = 10
N = 6 -> answer = 16
N = 7 -> answer = 26
N = 8 -> answer = 42

15. WBRWBR
16. RBWRBW

Sure, you can see here

http://acm.timus.ru/forum/thread.aspx?id=40348&upd=636512600467084493

As far as I understand, this problem is about combinations and not about fibonacci.

If there was only the first condition, then for any N we have only 2 possibilities to create the flag.
That is, f(1) = 2, f(2) = 2, f(3) = 2, f(4) = 2, ..., f(N) = 2;
This is true, because the choice of the first stripe determines the rest of the flag automatically. If you choose the first stripe to be white-colored then you are destined to choose the red stripe to be the second one. And vice versa. Don't make my words a HOLY WISDOM - think about it till you can feel it yourself. Don't read next, until you fully and completely get it.

The second condition is here to complicate your life. It doesn't do anything to our function f(x) if x equals to 1 or 2. That is, f(1) and f(2) are still equal to 2.
(By the way, I've just noticed that I've pulled the function from under the pillow. Well, in my mind this function returns the amount of different flags that can be created if you need to make it from x stripes. Ok, now we're moving on...)

But it allows us to INSERT the blue stripe between the two: white and red stripes.

This concept of INSERTION is really the key here. Think about it. If you were supposed to gain anything intellectually from solving this task at all, I bet, it was this very concept.

If we have some sequence of 2-colored flag: WRWRWRWRWRWRWR (White and Red), and this sequence contains all the N stripes that we need, then we really don't have any place to INSERT our blue stipe.
You think, ok, that's fair, and remove one of the stipes (e.g. the left-most). Now you have the place for your blue stripe ... and you can insert it in many ways: wBrwrwrwrwr or wrBwrwrwrwr or wrwBrwrwrwr ... well, you get the point :)
This way, by removing one of the stripes you have created X COMBINATIONS. This word is also important, that is why it is all upper-case :)

If you remove ONE MORE stripe (think about removing as n - 1 or better n--), you now have to INSERT 2 blue stripes somewhere in the sequence wrwrwrwrwrwr...
E.g. wBrBwrwrwrwrwrwr, or wBrwrwrwrwrwrwBr. Now there should be more COMBINATIONS than in the previous case (figure out yourself, how many :) ).

The last point I want to make is that you have to know your limits. That is, you have to understand when to stop removing stipes from the flag and stop INSERTING blue stripes in it. When you get to this point (keeping in mind all the previous points), you will figure this out by yourself easily...

Edited by author 20.08.2015 02:16

Edited by author 20.08.2015 02:18

Edited by author 20.08.2015 02:23

Edited by author 20.08.2015 02:23

Edited by author 20.08.2015 02:25

Edited by author 20.08.2015 02:26

Edited by author 20.08.2015 02:27

Edited by author 20.08.2015 02:27

Edited by author 15.10.2016 20:15

Edited by author 15.10.2016 20:16

Edited by author 15.10.2016 20:20

Edited by author 15.10.2016 20:21

Edited by author 15.10.2016 20:21

Some ways may be counted twice, so the ways will be less than 2A

m = f(n) = f(n-1)  + f(n-2)

why f(n-1) :-
put W and [R,...(n-1)] or R and [W,...(n-1)]

why f(n-2) :-
put R,B and [W,..(n-2)] or W,B and [R,...(n-2)]

HTH

Think abstractly! It's very easy!

Edited by author 06.02.2014 05:58

Edited by author 06.02.2014 05:58

You can either take it the mathematical way, and solve it by induction: assume you know the number of ways for 1..N stripes, how to find out the ways for N+1?
Or you can make a brute-force algorithm (backtracking) that simply counts and prints the number of ways for each N between 1 and 10-20 (until it gets too slow), then try to deduce a general rule for N, based on this series.
Good luck!

If n = 1, then the only strip may be Red or White, so answer is 2.
If n = 2, then you can either start with Red or White, but for each, you can only place White or Red respectively for the second strip, so answer is 2 again.

int -> long long

data type

Edited by author 25.06.2013 20:33

Edited by author 25.06.2013 20:33

N, the number of the stripes, stripes isn't a color neither flags, it's just the columns of the table ;)


Edited by author 11.11.2011 20:24

Let red color is 1, white color is 2 and blue color is 3. We can get only 6 positions that correspond to our condition. They are 1321, 2132, 1321,2312,1212,2121, is it right?

1) ...and we get just doubled fibonacci sequence.
2) unsigned long is enough ;)