All-Ukrainian Olympiad in Informatics — Finals (Odesa 2001)

A string S of length N (0 ≤ N ≤ 100) and a dictionary of M words (0 ≤ M ≤ 100) are given, all made of lowercase letters a–z, with no dictionary word longer than S. Find the minimum number of characters to delete from S so that the remaining string can be written as a concatenation of dictionary words, each usable any number of times (the empty string counts as a valid concatenation of zero words).

In the sample, deleting the letters f and t from abafchtdsya gives abachdsya, which splits into the words a, bach, dsy, a.

Input file CIPHER.DAT starts with a line containing two integers N and M, followed by the string S on the next line, followed by M lines each holding one dictionary word. Output file CIPHER.SOL must contain a single natural number: the minimum number of deletions required.

0 ≤ N ≤ 100, 0 ≤ M ≤ 100, dictionary word length ≤ N, alphabet is a–z only.

Input:

11 5
abafchtdsya
aba
a
bach
dsy
zero

Output:

2

A traveler must cross a maze to reach a spring of living water. The maze is an N×N grid of cells, with walls possibly standing along cell edges. The traveler moves one step at a time to a horizontally or vertically adjacent cell, and may pass straight through a wall using magic, but only up to K times in total; the traveler may never step outside the maze. Starting at cell (1, 1), find the minimum number of steps needed to reach the spring at cell (P, Q).

Input file MAZE.DAT starts with a line containing N, K, P, Q (2 ≤ N ≤ 200, 0 ≤ K ≤ 250, 1 ≤ P, Q ≤ N). The next N−1 lines each contain N integers marking horizontal walls between vertically adjacent cells, followed by N lines of N−1 integers each marking vertical walls between horizontally adjacent cells (0 = no wall, 1 = wall present). Output file MAZE.SOL must contain a single line with the minimum number of steps, or −1 if the spring is unreachable.

2 ≤ N ≤ 200, 0 ≤ K ≤ 250, start and target cells are within the grid.

Input:

3 1 2 3
0 0 0
0 1 0
1 0
1 0
0 0

Output:

3

To prepare for an informatics olympiad, the mayor wants reliable power for every school in the city. A line must be run from an alternative power source, "Maybuttya," to any one school, and lines may also connect pairs of schools directly; a school has reliable power if it is connected, directly or through other reliably-powered schools, back to the source. Given the costs of the possible connections between school pairs, compute the total cost of each of the two cheapest such power schemes (the cost of a scheme is the sum of the costs of the connections it uses).

Input file SCHOOLS.DAT starts with a line containing N (3 ≤ N ≤ 100), the number of schools, and M, the number of possible connections. Each of the next M lines contains three numbers Ai, Bi, Ci — a possible connection between schools Ai and Bi at cost Ci (1 ≤ Ci ≤ 300). Output file SCHOOLS.SOL must contain a single line with two natural numbers S1 and S2 (S1 ≤ S2) — the costs of the two cheapest schemes; S1 = S2 only when several minimum-cost schemes exist.

3 ≤ N ≤ 100, connection costs 1 ≤ Ci ≤ 300, the connection graph need not be complete.

Input:

5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

Output:

110 121

A triangle is given by the coordinates of its three vertices on the plane. Find the side length L of the smallest-area square that can contain the triangle, with all three vertices lying inside the square or on its edges. The square may be placed at any position and any rotation. It is enough to find L to within 1e-4.

Input file SQUARE.DAT contains one line with six real numbers X1 Y1 X2 Y2 X3 Y3, separated by spaces — the coordinates of the triangle's vertices (-10000 ≤ each coordinate ≤ 10000). Output file SQUARE.SOL must contain a single number: the side length L of the smallest enclosing square.

Coordinates are bounded by 10000 in absolute value; the answer is accepted with a tolerance of 1e-4.

Input:

0.0 0.0 1.1 0.0 0.0 1.1

Output:

1.1