Problem description.

This problem is simple and will introduce you to the Dynamic Programming.

You will be given an array and a key value.

You will have to find out the occurrences of the key value depending upon the query using Brute Force and Top Down Dynamic Programming.

-----Brute-Force: -----
You will check the query, and calculate the occurrences.

-----DP: -----

You will check the query; check whether the memoized solution is already available.

If the memoized solution is available, no need to calculate the number of occurrences again.

If the memoized solution is not available, then calculate the number of occurrences and memoize it for future use.

-----Pseudo Code for DP:-----
countOccurences(key,from):

if (from = size of array) then
return 0
endif
if dp[from] is availabe then
return dp[from]
endif
if( array[from] == key) then
dp[from] = 1+countOccurences(key,from+1)
else
dp[from] = countOccurences(key,from+1)
endif
return dp[from]

-----Input:-----

The first line of input is the number of test cases (t).

The first line of each test case is the number of array elements (n).

The next will contain n space separated integers.

The next line will have the key element (k).

The next will have number of queries (q).

The next q lines will contain an integer A such that 0<=A < n.

You have to find out the number of occurrences from a to end of the array using both brute force and DP.

Everything will fit into the range of int.

-----Output:-----

For each test case, the output will have q lines with 3 space separated integers.
The first will be the number of occurrences, other will be the loop count/function calls,
using brute force and the last will be the number of loop count/function calls using DP.

-----Sample Input:-----
1
10
1 2 3 1 2 3 1 2 3 1
3
5
2
4
6
8
2

-----Sample output:-----
3 8 9
2 6 1
1 4 1
1 2 1
3 8 1

-----Explanation:-----

For the first query, we have to find the number of occurrences of 3 from index 2.

Using the brute force, the loop will check each element from index 2 to 9. Thus the loop count is 8.

Using DP, the method countOccurences(key,from) will be called like this :

countOccurences(3,2)->countOccurences(3,3)->countOccurences(3,4)->countOccurences(3,5)
->countOccurences(3,6)->countOccurences(3,7)->countOccurences(3,8)
->countOccurences(3,9)->countOccurences(3,10).

When the countOccurences(3,10) is called, it will return 0. Total 9 function calls.

For the second query, the brute force will do the same as above.

But the DP will check whether solution for countOccurences(3,4) is available or not.

As it was calculated while solving the first query, it won’t solve it again and will directly give the answer.

Total 1 function calls.

见题面

见题面