TopCoder problem "TCU" used in TCCC '03 Semifinals 1 (Division I Level One)

Problem Statement

At TC University, there are a number of different majors. People in these majors occasionally switch from one major to another each year. Additionally, TCU is famous for having students who never graduate. Your task is, given a list of majors, the starting number of people in each major, and the percentages of people who switch from each major to each other major, determine the expected number of people who are in each major after a certain number of years.

The input String[] will be a list of the percentages of people who change to each other major, each year. Element i of percentages is a single space delimited list of integers, where the j^th integer in the list represents the percentage of people in major i who switch to major j each year (the i^th integer in element i is the percentage of people in major i who stay in that major). You will also be given a int[], start representing the intial number of students in each major (the i^th element of start represents the number of people starting in major i).

Thus, if the input String[] were {"90 10","05 95"} this would mean that each year 10% of the people with major 0 become people with major 1, while the remaining 90% keep major 0. Similarly, every year 5% of people with major 1 switch to major 0, while the other 95% of them remain in major 1.

If a fractional number of people would switch majors, add the fractional part onto the number of people who remain in the same major they started in. Thus there are always the same number of total people at TCU. For example, if you end up with 4.7 people switching from one major 0 to major 1, and 3.3 people staying in major 0, then take the 0.7 people, and add them to the number of people who stay in the same major. Thus, in this example, 4 people would switch from major 0 to major 1, and 4 people would stay in the major 0.

Given this information, and the number of years that people are switching, determine how many people there are in each major after the given number of years have passed.

Definition

Class:	TCU
Method:	majors
Parameters:	String[], int[], int
Returns:	int[]
Method signature:	int[] majors(String[] percentages, int[] start, int years)
(be sure your method is public)

Constraints

percentages will contain between 1 and 20 elements, inclusive.

Each element of percentages will contain between 1 and 50 characters, inclusive.

Each element of percentages will be a space delimited list of integers (which may have leading 0's and extra, leading, or trailing spaces).

Each element of percentages will have a number corresponding to every major.

The sum of all the numbers in each element of percentages will be 100.

Each number in each element of percentages will be between 0 and 100, inclusive.

Each element of start will be between 0 and 1,000,000, inclusive.

start will contain the same number of elements as percentages

years will be between 0 and 10,000 inclusive.

Examples

{"99 01","99   001"}

{1000000,0}

Returns: { 990000,  10000 }

At the start there are 1,000,000 people in major 0, and none in major 1.

During the first year, 1% of the people in major 0 switch to major 1. Thus, after one year there are 990,000 people in major 0 and 10,000 people in major 1.

During the second year, 1% of the people in major 0 (0.01 * 990,000 = 9900) switch to major 1. At the same time, 99 percent of the people in major 1 switch to major 0 (0.99 * 10,000 = 9900). Since the same number of people switch from major 0 to major 1 as switch from major 1 to major 0, there is no net change in the number of people in the two majors. Thus, after two years (and after any number of years greater than two), there are 990,000 people in major 0, and 10,000 people in major 1.

{"80 1 5 14","2 76 19 3","1 3 45 51","30 32 26 12"}

{1237,625,9618,13476}

Returns: { 7497,  7212,  5533,  4714 }

After 1 year: {5141, 5089, 8011, 6715}

After 2 years: {6309, 6309, 6574, 5764}

After 3 years: {6968, 6900, 5971, 5117}

After 4 years: {7308, 7129, 5677, 4842}

After 5 years: {7497, 7212, 5533, 4714}

{"80 1 5 14","2 76 19 3","1 3 45 51","30 32 26 12"}

{1237,625,9618,134760}

Returns: { 46162,  41768,  31364,  26946 }

{" 00 100 "," 100 0 "}

{23,37}

Returns: { 37,  23 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=921

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4491&pm=921

Writer:

lars2520

Testers:

brett1479 , schveiguy

Problem categories:

Dynamic Programming, Simulation