Time Limit: 30 minutes, 2 questions
1. Harry and The Philosopher's Stone
Harry is being chased by an unknown enemy while trying to get the Philosopher's stone to a safe place. He stands on one corner of a giant wizard chess board with the door to escape being at the diagonally opposite end of the board.
Wizard chess boards are always square in shape, and allow anyone to move only one step at a time in any of the four directions: forward, backward, left and right. Some blocks on the board have mark of Voldemort and if Harry steps on any of those blocks, he will instantly die.
Harry is standing at the top-left corner block of the board, and the door is at the bottom right corner block. To avoid capture, Harry needs to get to the escape door as quickly as possible. Help Harry in his quest by writing a program to find out least number of steps needed to reach escape door.
Example
Input:
7
DVDDD
DDDVD
VVVDD
DVVDV
DDDDD
Output:
12
Constraints
1<=Size of board<=100
My approach: Simple iterative BFS would suffice and pass the TC. Store in queue<pair<int,int>>
2. Fibonacci Ways
Given a Fibonacci sequence, a function f(n) represents the number of ways in which the integer n can be represented as a sum of Fibonacci numbers without repetition of any Fibonacci number.
Eg. f(13) = 3, since possible ways are {13}, {8,5}, {8,3,2}. {5, 5, 3} won't be considered since 5 is repeated.
Now, S(n) is defined as sum of all f(k) from k=0 to k=n inclusive.
Write a program to compute S(n) value for a given n.
Example
Input:
10
Output:
18
Constraints
1<=n<=4000
My approach: Tried a variant of Knapsack. Couldn't complete due to very less time.