International Schools Software Competition Trial 99 Tasks

1. Splitting the Treasure

You and your buddy discovered a long strip of rare metal in a recent trip. The strip was sent to the laboratory and a value index (VI) was determined for every uniform-length segment of a strip. The VI is an integer in the range [-50,50].

You are to split the strip into two portions so that each of you can take a portion home. Both of you must bring home something, and you are not allowed to cut into the middle of a segment, or to make more than one cut. To ensure fairness, the difference between the VI sums of the two portions should be as small as possible.

For example, the figure below shows a 5-segment strip with the VIs indicated on each segment. The best cuts are indicated by the arrows each cut having a VI sum difference of 4:

You are to read data from a text file. The first line of the input file indicates the number of segments n (where 2 ≤ n ≤ 500), and the next n lines indicate the VI of each segment. You are to determine the smallest VI-sum difference achievable, and how many ways to achieve that. In the above example, the answers are 4 and 2 respectively, and these are to be written on a single line.

Sample input:
5
4
8
-4
-6
10

Sample output:
4 2

2. UniqueDigit Integers

A unique-digit integer is a positive (without leading zeroes) with no duplicate digits. For example, 7, 135 and 5689 are unique-digit integers, whereas 33, 2312 and 3004 are not.

Given two 3-digit integers m and n, where m < n, determine how many unique-digit integers are there in the range between m and n inclusive.

For example, if m-100 and n=120, then the unique-digit integers in the range [100,120] are:

102, 103, 104, 105, 106, 107, 108, 109, 120.

Since there are 9 of such integers, the answer is 9.

The input file contains two positive integers, m and n, on a single line. You are to write the answer into an output file. The sample input and output files for the above examples are shown below.

Sample input:
100 120

Sample output:
9

3. Anagram Groups

Words are said to belong to the same anagram group if one word can be changed into each of the other words by rearranging the order of the letters. For example, the words asset and seats are in the same anagram group, since the letters of one word can be arranged to form the other. The words less and sell however are not in the same anagram group.

Given a list of words, your task is to find how many different anagram groups the words in the list belong to.

For example, consider the following list:
tops, pat, pot, stop, pots, tap, apt, seats, done, top, asset, tease, node

These words fall into the following anagram groups:
anagram groups:
apt, pat, tap
asset, seats
done, node
pot, top
pots, stop, tops
tease

Since there are six different anagram groups, the answer is 6.

The first line of the input file contains a single positive integer representing the number of words in the list. Each of the remaining lines in the input file contains a single word. You may assume that there are less than 100 words in the input file, and each word has at least one character and at most 10 characters. All characters are lower-case letters (a to z). You are to write the answer into an output file. The sample input and output files for the above example are shown below.

Sample Input
13
tops
pat
pot
stop
pots
tap
apt
seats
done
top
asset
tease
node

Sample output:
6

4. Making Change

You are given a limited number of coins of various denominations, and a certain amount. You are to compute how many ways there are to pick the coins to add up to that amount. For example, given 12 coins of 1-cent value, 2 coins of 5-cent value and 3 coins of 10-cent value, and an amount of 15 cents, there are 4 combinations:

2 5-cents coins and 5 1-cent coins
1 5-cents coins and 10 1-cent coins
1 10-cent coins and 1 5-cent coin
1 10-cent coins and 5 1-cents coins

The answer therefore should be 4.

The first line of the input file consists of a single positive integer indicating the number of different coin denominations. The next line of the input file consists of a single positive integer representing the total amount. The remaining lines of the input file each consist of a pair of positive integer representing a coin denomination followed by the number of coins of that denomination available. All number are in the range [1, 100].

The sample input and output are shown below.

Sample input:
3
15
1 12
5 2
10 3

Sample output:
4

Back