Here's another problem... any ideas?

[Nineshadow]

Miruna's passion is to color.She spent her last holiday at her grandmother in a country that is boring and thought to paint the fence at grandma's house.

The fence consists of N boards placed side by side. Miruna found in the grandparents' garage 5 boxes of paint of different colors: white, blue, red, green and yellow. When she painted the fence, Miruna followed these rules:

 

- If a board was painted with white, the following board will be painted mandatorily with blue

- If a board was painted blue, then the next board will be painted with white or red paint

- If a board was painted in red, then the next plank will be painted with blue or green paint

- If a board was painted green, then the next board will be painted with red or yellow paint

- If a board was painted with yellow, then the next board will be painted with green paint

 

After she finished the job Miruna admired her "work of art" and wondered how many different ways she could have painted the grandparents' fence

.

 

Input

Colours.in file contains the first line one integer N (1 <= N <= 5000).

 

Output data

 

Colours.out output file will contain the first line a single integer representing the number of different ways in which Miruna could have painted the grandparents' fence.

 

Restrictions and notes:

• 1 <= N <= 5000;

• For 25% of tests N <= 45.

 

Example

colours.in : 4

 

colours.out : 24

 

Explaination: 

(white, blue, white, blue); (white, blue, red, blue);

(white, blue, red, green); (blue, white, blue, white);

(blue, white, blue, red); (blue, red, blue, white);

(blue, red, blue, red); (blue, red, green, red);

(blue, red, green, yellow); (red, blue, white, blue);

(red, blue, red, blue); (red, blue, red, green);

(red, green, red, blue); (red, green, red, green);

(red, green, yellow, green); (green, red, blue, white);

(green, red, blue, red); (green, red, green, red);

(green, red, green, yellow); (green, yellow, green, red);

(green, yellow, green, yellow); (yellow, green, red, blue);

(yellow, green, red, green); (yellow, green, yellow, green).

_____________________________________________________________________________________________________

 

So...any ideas guys? Actually generating those sequences would not be efficient enough, not even close to efficient enough. I only need to find out the number of possibilities, not all the possibilities themselves. Or I could actually generate them all...let's see. I start with white, then generate all possible combinations with it, then blue, red, green , yellow, etc. Or I could start from the end...

[Midnight]

Use combinatorics.

[MrSuperb]

Use combinatorics.

 

I'd say graph theory does the job quite easily.

 

tips:

- digraph

- adjacency matrix

- number of paths of length

 

[MrSuperb]

a 'problem' is, that numbers get large rather quickly

 

colours.in : 45
colours.out : 1.4644e+11

 

colours.in : 1000
colours.out : 9.6961e+238

[Midnight]

a 'problem' is, that numbers get large rather quickly

 

colours.in : 45

colours.out : 1.4644e+11

 

colours.in : 1000

colours.out : 9.6961e+238

 

Hmm, for these kinds of problems, the problem asks you to make the answer "smaller" via prime modulo, usually 1000000007 (1bil+7).

 

OP, did you forget this or the problem doesn't say?

[Nineshadow]

Hmm, for these kinds of problems, the problem asks you to make the answer "smaller" via prime modulo, usually 1000000007 (1bil+7).

 

OP, did you forget this or the problem doesn't say?

Doesn't say.

[Midnight]

I'd say graph theory does the job quite easily.

 

tips:

- digraph

- adjacency matrix

- number of paths of length

 

 

A possible problem with this is that it might be too slow... If there isn't a time limit of anything, then disregard this comment lol.

[Nineshadow]

A possible problem with this is that it might be too slow... If there isn't a time limit of anything, then disregard this comment lol.

The time limit is 0.2 seconds per test.

[Midnight]

Doesn't say.

 

Really, the answer can get ridiculously big.

 

The time limit is 0.2 seconds per test.

 

Christ, that is really strict. Math it is, then.

[Nineshadow]

Christ, that is really strict. Math it is, then.

Yep.

It's math, exactly what I was saying.

[Ciccioo]

double precision arithmetic stops working for N = 1290, so it's kind of weird that they're asking for such big numbers

the problem is solvable in O(n) time and O(1) space, but the numbers man, the numbers

[Nineshadow]

double precision arithmetic stops working for N = 1290, so it's kind of weird that they're asking for such big numbers

the problem is solvable in O(n) time and O(1) space, but the numbers man, the numbers

Really?

[Ciccioo]

Really?

really: to solve the problem you only care about the last board, because that's the only thing that matters in the decision of what color to paint the next one

you need to see that the graph doesn't really become wide, because at the end of the day you always end up painting in one of those 5 colors

 

edit: actually i don't know for sure if i'm using double precision or single precision, i'm just using javascript

[fizzlesticks]

edit: actually i don't know for sure if i'm using double precision or single precision, i'm just using javascript

afaik all JS numbers are 64 bit doubles so you'd be right.

[MrSuperb]

A possible problem with this is that it might be too slow... If there isn't a time limit of anything, then disregard this comment lol.

 

nono, that is plenty fast.

[Nineshadow]

nono, that is plenty fast.

0.2 sec fast?

[MrSuperb]

0.2 sec fast?

 

it takes less than 0.0005s for N=1000 in matlab

 

that being said, it is not precise!

[MrSuperb]

may I ask again where you got that problem from?

[Nineshadow]

may I ask again where you got that problem from?

Computer Science contest.

[Nineshadow]

Ok guys, found a mathematical solution, I think :

 

S(1)=5

S(2)=8

S(3)=14

 

S(2k) = 3^(k-1) * S(2)  , k > 1

 S(2k+1) = 3^(k-1) * S(3) , k > 1

 

Not too sure though.It was kind of random...

Can you guys compare these results with yours?

[Ciccioo]

 

Ok guys, found a mathematical solution, I think :

 

S(1)=5

S(2)=8

S(3)=14

 

S(2k) = 3^(k-1) * S(2)  , k > 1

 S(2k+1) = 3^(k-1) * S(3) , k > 1

 

Not too sure though.It was kind of random...

 

nope: S(4) should be 42

 

fun fact: S(5000) = 169474956624661457429287215303636757550018332635334437478072087064483577679799480596868212353552667075074293712631593174712425828162955387033019296928926347388987016058741797038541642778290931552332968905243217337927155459614179025008351133882657608159100502745235025476534178924741676143400635549261350165388115320002330400785526963032760800987493724271293125107005440545053692380482565596550498483768387433837368545826941284545770526135596553218818577221867701425997575539932103724608084092216020510465589976057949312416670641860430505271710293850653684039525001560181597269516185149300576215367978552596366507259645550687595667916604120125705842026900005893549990160596454822399586971652671135991244374870758427047961159785160685762848625863802095873066793842071566876481606510805687558597558108936702424020747124062823766162613509635095151419652060599575186257218866481767653769162992462150031367488559909335194313311663864158456978159567729192142346951584294309061882628524609166504774850000842145455501483387203415067806587694691057340586020981944240066175895726892049938678988210089871474519611171439944456538216158145333804419313730341978018157924519895863048906171092390405594368133336

[Nineshadow]

fun fact: S(5000) = 169474956624661457429287215303636757550018332635334437478072087064483577679799480596868212353552667075074293712631593174712425828162955387033019296928926347388987016058741797038541642778290931552332968905243217337927155459614179025008351133882657608159100502745235025476534178924741676143400635549261350165388115320002330400785526963032760800987493724271293125107005440545053692380482565596550498483768387433837368545826941284545770526135596553218818577221867701425997575539932103724608084092216020510465589976057949312416670641860430505271710293850653684039525001560181597269516185149300576215367978552596366507259645550687595667916604120125705842026900005893549990160596454822399586971652671135991244374870758427047961159785160685762848625863802095873066793842071566876481606510805687558597558108936702424020747124062823766162613509635095151419652060599575186257218866481767653769162992462150031367488559909335194313311663864158456978159567729192142346951584294309061882628524609166504774850000842145455501483387203415067806587694691057340586020981944240066175895726892049938678988210089871474519611171439944456538216158145333804419313730341978018157924519895863048906171092390405594368133336

ikr.

That's one hell of a number.

[Nineshadow]

nope: S(4) should be 42

Also, S(4) is 24. It's in the example.

[Ciccioo]

ikr.

That's one hell of a number.

now, find the prime factors

[Ciccioo]

Also, S(4) is 24. It's in the example.

sorry, i meant S(5)