[shkola] zadachite

poslednite zadachi

{JDFU}
__________________________________________
12MB-POP3-WAP-SMS-AHTИCПAM--TOBA-E-mail.bG
------------------------------------------
HOB БEЗПЛATEH AДPEC - http://mail.bg/new/
------------------------------------------
Title: SECOND AUBG PROGRAMMING CONTEST

SECOND AUBG PROGRAMMING CONTEST

Blagoevgrad, April 12 1998

Problem 1. TRIANGULAR MAZE

A triangular maze consists of square rooms, numbered from 1 to N (N<=64000), as shown in Figure 1. The top apex room (number 1) is an entrance of the maze and each room in the bottom line is an exit. As shown by the arrows (for the entrance room) it is possible to move from a given room to its “down” neighbours in the maze - left-down, straight-down and right-down. In some of the rooms M presents are distributed, marked with asterisks in Figure 1 (no more than one present per room).

Given a maze with some distribution of presents, write a program PROG1.EXE to find the maximum number of presents that can be collected during a single trip from the entrance to one of the exits of the maze.

The input data will be in a file named INPUT1.TXT. The first line of that file contains the integers N and M, separated by a space. The next M lines contain the numbers of the rooms with presents - one number per line.

Figure 1

The output file OUTPUT1.TXT must have one line with the maximum number of presents found by the program.

EXAMPLE

INPUT1.TXT

21 5

5

6

8

13

14

OUTPUT1.TXT

3

Problem 2. DICTIONARY

Any finite sequence of the letters a,b,...,z is called a word. Two words are similar if one of the following holds: a) one of the words has exactly one letter that is absent in the second, and all the other letters are equal and ordered in the same way; b) in exactly one place the two words have different letters, and all other letters are equal and ordered in the same way; c) the words consist of the same letters but, in the second, only two consecutive letters of the first are interchanged. Dictionary is a set of words. Two operations with a dictionary are available:

insert <word> and check <word>

where insert and check are the reserved names of the operations and <word> is any argument word. If the argument is in the dictionary, the operation insert does nothing, else it appends the word to the dictionary. The operation check searches the argument in the dictionary. It does not change the dictionary but gives an answer depending of its content as follow: YES - if the argument is in the dictionary; MAY BE - if the argument is not in the dictionary, but is similar to at least one word of the dictionary; NO - if the argument is not in the dictionary and is not similar to any word of the dictionary.

Write a program PROG2.EXE that maintains a dictionary.

The input data will be in a file named INPUT2.TXT. Each line of that file contains one operation. The last line contains only the instruction stop.

The output file OUTPUT2.TXT must contain the arguments of the check operations in the order these operations were read and the answers given separated by a space - one pair per line, starting at the beginning of the line. If the answer is MAY BE, it has to be followed by all the similar words found in the dictionary - one word per line indented by 5 spaces from the beginning of the line.

EXAMPLE

INPUT2.TXT

insert the

check than

insert there

insert that

insert tree

insert threw

check three

check that

stop

OUTPUT2.TXT

than NO

three MAY BE

there

tree

threw

that YES

Problem 3. CLOSED AREA

A square drawing area consists of NxN (N<=200) subsquares or pixels. Each pixel is defined by its coordinates (x,y) - integers from 0 to N-1 and can be either black or white. Horizontal, vertical and diagonal(45o) lines that do not touch each other are available. A vertical line is defined by the pair (a,*), where a is the x-coordinate of the crossing point of the line with the x-axis. A horizontal line is defined by the pair (*,b), where b is the y-coordinate of the crossing point of the line with the y-axis. A diagonal line is defined by the x- and y-coordinate of its crossing points with x-axis and y-axis, respectively. The lines (8,*), (*,28), (-4,4) and (42,42) are given on Figure 3. Two lines touch each other if, and only if, each pixel of one of the lines has a neighbour ing pixel with the other line (up, down, left, right or by diagonal).

Figure 3

Closed is an area that is bounded by parts of the given lines. The surface of a closed area is the number of internal pixels. On the Figure 3, three closed areas are shaded. The corresponding surfaces are 85,16 and 10.

Write a program PROG3.EXE that, given the size N of the drawing area and M lines that do not touch each other, finds the maximum surface of a closed area.

The input data will be in a file named INPUT3.TXT. The first line of that file contains the integers N and that, separated by a space. The next M lines contain the definitions of the given lines. The output file OUTPUT3.TXT must have one line containing the maximum surface.

EXAMPLE

INPUT3.TXT

40 4

8 *

* 28

-4 4

42 42

OUTPUT3.TXT

85

 

Problem 4. TRIP AWARD

The award for the first place in a programming competition is a trip to the fabulous country Tripland. The interesting towns of Tripland are N (N<=50) and they are enumerated from 1 to N. Only some pairs of towns are connected directly, but it is possible to go from each town to each other town through one or more intermediate towns. The winner will choose two towns, A and B, in Tripland and the organizing committee will pay the travel expenses for one of the shortest paths from A to B and one day expenses for each intermediate town on the chosen shortest path. Write a program PROG4.EXE that, given N, the pairs of directly connected towns and the lengths of routes between each pair, finds the most attractive pair of towns, A and B, for the trip - this with as many as possible inter mediate towns on a shortest path.

The input data will be in a file named INPUT4.TXT. The first line will contain the number N. The next lines will contain the list of pairs directly connected by a route. Each line consists of three numbers separated by one space - first town, second town and the length of the corresponding route. The end of the list is the triplet 0 0 0.

The output file OUTPUT4.TXT must contain one line with three numbers separated by one space - the start of the chosen path A, the end of the chosen path B (A<B) and the number of the intermediate towns.

EXAMPLE

INPUT4.TXT

9

1 2 30

1 5 20

1 6 10

2 3 30

2 5 20

3 4 10

4 5 20

4 9 10

5 7 10

5 8 30

6 7 20

6 8 10

8 9 10

0 0 0

OUTPUT4.TXT

1 3 4

Attachment: Image7.gif
Description: GIF image

Attachment: Image8.gif
Description: GIF image

Other related posts: