## Description

Problem 1

The input for this problem consists of two integers n and k, where 1 ≤ k ≤ 10 and a sequence of distinct

numbers c1 < c2 < . . . < ck, where each ci

is an integer between 1 and 10. Your program needs to output the

number of ways one can write n as a sum of integers from the set {c1, c2, . . . , ck}. You only have to output

the number of different partitions, not the partitions themselves. Furthermore, you can output either (the

choice is up to you):

• The number itself (note, that it can be very large).

• The last digit of this number (note that in this case it suffices to always take the recurrence mod 10 in

each step).

Run your program for the following five inputs:

1. n = 103

, k = 2, c1 = 1, c2 = 2.

2. n = 103

, k = 3, c1 = 1, c2 = 3, c3 = 5.

3. n = 2 · 103

, k = 3, c1 = 2, c2 = 3, c3 = 5.

4. n = 103

, k = 10, c1 = 1, c2 = 2, c3 = 3, c4 = 4, c5 = 5, c6 = 6, c7 = 7, c8 = 8, c9 = 9, c10 = 10.

5. n = 2 · 103

, k = 4, c1 = 2, c2 = 4, c3 = 5, c4 = 6.

1

Example: Input: n = 5, k = 3, c1 = 1, c2 = 3, c3 = 4.

Output: 6.

Partitions:

1. 1 + 1 + 1 + 1

2. 1 + 1 + 3

3. 1 + 3 + 1

4. 3 + 1 + 1

5. 4 + 1

6. 1 + 4

Problem 2

You are given a set of jobs. Each job i has a start time si and a finish time fi

. It also has a weight wi

.

Two jobs are compatible if their start-finish intervals don’t overlap. The goal is to find the maximum weight

subset of mutually compatible jobs (a subset with the maximum sum of weights).

Run your program on the two inputs provided. You have to output only the maximum weight, not the

actual subset. Each input file contains multiple lines, where each line contains three numbers describing a

job: si

, fi

, wi

. Each of these numbers is an integer between 1 and 200. See example below:

Input: 1 2 50

3 5 30

6 19 100

2 100 200

Output: 250

2