Gandalf the Grey
All submissions for this problem are available.
Gandalf has many great magical powers. Sauron is the 'ONLY' enemy of Gandalf. Gandalf gets news from his secret agent that Sauron is going to attack. Before the final attack Sauron will send 'n' war-machines(distinct) in n boxes(1 in each box).Each box will contain manual for the respective machine.Sauron's orcs are unskilled and inexperienced,so they cannot handle these war-machines without correct manuals. Gandalf decides to change the position of manuals from one box to another using his magic-power so that some or all manuals will be placed in wrong boxes.
Lord Elrond tells Gandalf that if they become successful in placing 'm' manuals at wrong places they will win the war.
Let P be the maximum number of ways to do this. Gandalf will try all the ways and then decide one among them.First try takes 1 magical power unit(mpu) ; 2nd try takes 1 mpu ; 3rd try takes 2 mpu and similarly: mpus required for 'i'th try = mpu taken for (i-1)th try +mpu taken for (i-2)th try
Print the magical power units required for last try,for the given value of n and m. As this value will be large,Print the answer mod 100003 (10^5+3).
- The first line of the input contains an integer T denoting the number of test cases.
- The next T lines contain:
- Each test case contains two integers n and m.
- For each test case, output a single line containing the answer mod 100003.
- 1 ≤ T ≤ 10000
- 1 ≤ n < 20
- 1 ≤ m ≤ n
Input: 1 4 2 Output: 8
For 4 Boxes 1,2,3 and 4 with a,b,c and d as respective manuals; 2 manuals can be placed in wrong boxes in following ways:
1 2 3 4
a b 'd' 'c'
a 'c' 'b' d
'c' b 'a' d
'b' 'a' c d
'd' b c 'a'
a 'd' c 'b'
Thus the sixth try will take 8 magical power units.
|Time Limit:||0.2 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions
If you are still having problems, see a sample solution here.