Fire and Ice
All submissions for this problem are available.
Kingdom Of Fire and Ice
There is a kingdom in land of fire and ice known as westros. The kingdom is ruled by mad king Amen Targareyan. Further more Westros is divided into two territories.
One territory known as ice because it is always snowing and other Fire beacuse of volcano near by area. There is rebellion to overthrow the mad king to bring peace to Westros.
There is a secret attack on red fort by rebellion force lead by Luke Skywalker. There is snitch in rebellion force. He trades the secret attack plan to mad king.
However mad king has superpower to sense disturbance in the force. He sends out his best knights to scout the rebellion force. He got to know that rebel force outmatch city guards
one to hundred. Moreover he came to know that Luke is last jedi who can detroy him.In order to win this battle against rebels, the mad king decided to use N common folks as soldiers.
He select a bunch of people from a territory and train them .Now king can only select odd number of people from land of fire and from land of ice in one go.
He cannot select bunch of people consecutively from either territory.In how may ways the mad king could assemble his army to battle against rebel forces ?
Note: The number of people in each territory is infinte
The first line of input contains an integer T denoting the number of test cases.
Every line of each test case contains a single integer N denoting common folks as soldiers and an integer M also.
For each test case output a single line consisting a single integer denoting the modulo M of the number of ways the king could assemble his army.
subtask#1: N<=30,M<=103(10 points)
subtask#2: N,M<=103(30 points)
subtask#3: original constraints(60 points)
In first test case thenumber of ways to assemble his army are:
1) one from fire, one from ice, one from fire, one from ice
2) one from fire, three from ice
3)one from ice,one from fire,one from ice , one from fire
4)three from ice,one from fire
5)three from fire,one from ice
6)one from ice, three from fire
|Tags||ankurgoel7373, cocr16, fibonacci, medium, recursion|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions
If you are still having problems, see a sample solution here.