Joint Venture of DSIIDC, An undertaking of Delhi Govt. and TCIL, A Govt. of India Enterprise

Under Ministry of Communications

**Definition**

Dynamic programming (DP) is a general algorithm design technique for solving problems with overlapping sub-problems. This technique was invented by American mathematician “Richard Bellman” in 1950s.

**Key Idea**

The key idea is to save answers of overlapping smaller sub-problems to avoid recomputation.

**Dynamic Programming Properties**

*****An instance is solved using the solutions for smaller instances.

*****The solutions for a smaller instance might be needed multiple times, so store their results in a table.

*****Thus each smaller instance is solved only once.

*****Additional space is used to save time.

**Solve Sequential Puzzle**

Niharika was teaching string addition to his little son. Children learn better with practical activities. Keeping this in mind, she gave a puzzle to him. In the puzzle, the first is a target containing the sequence of characters, and the second is a group of words i.e. hints separated by#. The task is to find the two words in hints that when combined will form the target.

**Note**

Words will always be given in a sequential order in the hints to form the target.

**For example**

target=Puzzle

Hints=Pu#asd#jko#le#zz#zzle

Since"Pu"+"zzle"="Puzzle", so correct hints are "Pu" and "zzle". Remember the two correct hints will always be given in the same order in the input as required.

**Constraints**

1<=length of target<=3000

2<=length of hints<=600

1<=length of each hint<=2999

**Input format**

First-line contains the target

Second-line contains the hints separated by#.

Each of the hints and target will contain only alphabets.

**Output format**

Print the two hints fulfilling the condition in two lines. If no such hints exist, print -1.

**Sample Input1**

Puzzle

Pu#asd#jko#le#zz#zzle

**Sample Output1**

Pu

zzle

**Points Earned**

Seerat isavery energetic girl. She loves jumping on horizontal bars. A number is written on each bar. Every time she jumps, she read the number. If it isaperfect square number then she will get points equal to the square root of that number. Find out the number of points earned by her in the run.

**Constraints**

1<=n<=100

2<-number on bars<=10000

**Input format**

First-line contains a number of bars n.

Second-line contains numbers written on each of n bars.

**Output format**

Print the number of points earned by Seerat.

**Sample Input**

3

8169

**Sample Output**

7

**Explanation**

Points earned at the first bar -0

Points earned at the second bar-4

Points earned at the third bar-3

Total points earned -0+4+3=7

**Reverse digits**

Reverse(D)to be the reversal of all digits in D.

For example, Reverse(349)=943, Reverse(93)=39, and Reverse(340)=43.Amrit wants to go to the movies with Nayak on some day D satisfying p<=D<=q, but he knows he only goes to the movies on days he considers to be lucky. Nayak considers a day to be lucky if the absolute value of the difference between d and Reverse(d) is evenly divisible by s.

Given p, q, and s, count and print the number of lucky days when Amrit and Nayak can go to the movies.

**Input Format**

A single line of three space-separated integers describing the respective values of p, q, and s.

**Constraints**

1<p,s,q<10000

**Output Format**

Print the number of beautiful days in the inclusive range between p and q.

**Sample Input**

10 13 6

** Sample Output**

2