You are not logged in. Please login at www.codechef.com to post your questions!

×

FICE - Editorial

Problem Links

Practice
Contest

Author: Ankur Goel

Tester: Ankur Goel

Editorialist: Ankur Goel

Difficulty

Medium

Prerequisites

Fibonacci Series, Recursion

Problem

The King wants to select N common folks as solider from the Fire and Ice island in order to win the battle. He can only select odd number of people from land of fire or ice only in one go.He cannot select bunch of people consecutively from either territory.Find the number of ways the mad king could select his army.

Note :The number of people in each territory is infinite.

Quick Explanation

Ans= 2*Fibo(N)%M

Explanation

The Problem is simply based on the Fibonacci Series. Let 0 denotes the people from Land of Ice and 1 denotes the people from Land of Fire then, the number of binary strings of length n without an even number of consecutive 0s or 1s is 2Fn. For example, out of the 16 binary strings of length 4, there are 2F4 = 6 without an even number of consecutive 0s or 1s – they are 0001, 0111, 0101, 1000, 1010, 1110.

Find the Fibonacci using O(Log N) Algorithm and take the modulo M at every step, otherwise your algo may fail due to Time Complexity or due to the Overflow of Fibonacci Number beyond the range of even 64 bit int.

Author's Solution

Author's solution can be found here

Related Problems

Ankur and Coins
This question is marked "community wiki".

asked 08 Oct '16, 20:58

ankurgoel7373's gravatar image

2★ankurgoel7373
112
accept rate: 0%

edited 20 Mar, 22:16

admin's gravatar image

0★admin ♦♦
17.4k347486515

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,235
×1,933
×255
×107
×5
×2

question asked: 08 Oct '16, 20:58

question was seen: 486 times

last updated: 20 Mar, 22:16