International Schools Software Competition 99 Tasks

1. Black on Left, White on Right

You are given a long chain of black and white balls. An example of a chain of ten balls is shown below

You are allowed only to swap two neighboring balls, for instance, ball 1 with ball 2, or ball 2 with ball 3, but not ball 3 with ball 5, or ball 10 with ball 1.

Determine the minimal number of swap you would need in order to get all the black balls on the left of the chain, and all the white balls on the right.

You are to read from an input text file. The first line of the file contain the number of balls n (where 5 ≤ n ≤ 200), and the next line contains n characters, each of which is either b (for black ball) or w (for white ball). You are to write the answer, the minimal number of swaps needed, into an input file.

The sample input and output files for the above example are shown below.

Sample input:
10
bwwbwwbbbw

Sample output:
14

2. Longest Repeated Sub-string

You are given a string with at most 100 characters, each character is an upper-case letter A to Z. You are to find the length of the longest sub-string that appears at least twice in the string. Below are 4 examples, where each example shows the given string, the longest sub-string that occurs at least twice in the string, and the length of the longest sub-string.

String	Longest sub-string	Length
ABCDEABC	ABC	3
XYXYX	XYX	3
AXAYAZA	A	1
GHI		0

The sample input and output files for the first example are shown below.

Sample input:
ABCDEABC

Sample output:
3

3. Smallest Loop

In a small town with n (where 4 ≤ n ≤ 20) bus-stops, the bus stops are labeled 1, 2, 3, ., n. The routes of the bus service are given as a list of directed segments. For example, the following diagram shows a town with 5 bus-stops, and 6 segments:

Every segment links two different bus-stops, and no segment is duplicated.

You are to determine the length of the shortest loop in the route. There are two loops in the example, one loops through bus-stops 1, 2, 4 and hence has a length of 3; and another loops through bus-stops 1, 2, 4, 3, and has a length of 4. The length of the shortest loop is hence 3.

If there is no loop in the routes, you are to input:
There is no loop.

Note that the smallest loop possible has length 2, one that starts from bus-stop x, goes to bus-stop y, and back to x.

The input file contains 2 ingredients, n and k, on the first line: n is the number of bus-stops, and the k is number of segments. The segments are given in the subsequent k lines, with each segment represented by the bus-stop where it ends. You are to write the answer into a output file. The sample input and output files for the above example are shown below.

Sample input:
5 6
1 2
2 5
4 1
3 1
2 4
4 3

Sample output:
3

4. Unique-Index Multidimensional Array Elements

A unique-index element of a multidimensional array is an element with no duplicate subscripts. For example, A[2] [1], B[13] [4] [6], and C[111] [22] [3] [4444] [55] are unique-index elements, whereas A[2] [2], B[13] [4] [4] and C [111] [22] [3] [4444] [3] are not.

Your task is to determine the number of unique-index elements there are within a specified portion of a multidimensional array.

For example, for the portion of a two-dimensional array A [i] [j] where 3<= i<=6 and 4<=j<=5, the unique-index elements are:

A [3] [4], A[3] [5], A [4] [5], A [5] [4], A [6] [4], A [6] [5].

Since there are 6 such elements, the answer is 6.

The first line of the input file is a positive integer representing the number of dimensions in the array. Each remaining line of the input file will have two positive integers (with the second integer greater than or equal to the first) which specify the range of the respective subscript.

You may assume that:
- Every number in the input file is a ppositive integer less than 100
- The total number of array elements inn the specified portion of the multidimensional array is less than 10,000.

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:
2
3 6
4 5

Sample output:
6

Back