Gihyun Kim

Author: Gihyun Kim

Date: January 15th, 2024

Topic: Dynamic Programming (DP)

What is Dynamic Programming (DP)?
Dynamic Programming (DP) is a programming technique used mainly to improve efficiency by solving complex problems by breaking them down into smaller subquestions and using previously obtained answers and substituting them for the answers of the same/similar questions.
DP allows for a faster solving of the problem and makes the algorithm more efficient by avoiding recalculating the same problem multiple times. DP tends to be used for problems such as the Fibonacci Sequence, Longest Common Subsequence, and Shortest Path Algorithms.

Example Question:
A biologist is studying the ecology of a newly discovered paramecium species. Known for being very fertile, this species has the following characteristics: Reproduces asexually, becomes an adult on day a after birth, produces one new individual every day from the day it becomes an adult: the first individual is produced as soon as it becomes an adult, and a new individual is produced every day thereafter. create one by one A new individual also becomes an adult on the a day after birth and creates a new individual.

From the b day after birth, no new individuals are created. Since they produce new individuals from day a to the day before day b, a total of b-a individuals are produced during their lifetime.
It dies on the d day after birth.
Below is a record of the daily observations of a newly born paramecium in the tank at a = 2, b = 4, and d = 6.
The numbers in parentheses are integers representing the number of days since each paramecium in the tank was born.
Date Born: (0) – insert new object
Day 1: (1) – paramecium growth
Day 2: (2, 0) – It is the 2nd day since paramecium is born, so it becomes an adult and creates a new individual.
Day 3: (3, 1, 0) – The paramecium that became an adult on day 2 produces a new individual today.
Day 4: (4, 2, 1, 0) – Paramecium created on the 2nd day creates a new paramecium (parametic paramecium that was initially introduced does not create a new organism)
Day 5: (5, 3, 2, 1, 0, 0)
Day 6: (4, 3, 2, 1, 1, 0, 0) – The first entity you put in dies.

On the 6th day, there are a total of 7 parameciums living in the tank.

For paramecium breeding information a, b, and d, write a program that outputs the remainder of dividing the number of parameciums alive on the Nth day after placing one newly born paramecium in a tank by 1000.​

Input
In the first line, four integers representing a, b, d, and N are given sequentially with a space between them. However, 0<a<b<d≤10,000 and 1≤N≤1,000,000.

Print
On the first line, on the Nth day after putting one paramecium in the tank, the number of live parameciums in the tank is divided by 1,000 and the remainder is output.

Sample Input & Outputs:

Solution Code: