Site Navigation

Home

My Programs

C# Classes Fraction Matrix MazeSolver

VB 6.0 Programs Graph Plotter

C Programs Graph Plotter      C Games Mind Fighter Mind Killer Mind Guesser Mind Reader TicTacToe Puzzle

Articles Fraction Matrix MazeSolver

My Blog

Page for Classmates

Programs by Others

Programming Problems      Software Competitions ISSC 99 Final ISSC 99 Trial ISC 96 ISC 96 Trial ISC 92 ICPC 92 ISC 90 ISC 90 Trial

Programming Forum

Sign my Guestbook

View my Guestbook

Email me

International Software Competition: SEARCC 96

Ambassador Hotel, Bangkok, Thailand.

July 5, 1996 (Trial Day)

Problem 1

Fibonacci Partition

The Fibonacci sequence is defined by the following recurrence.

f₀ = 0,   f₁ = 1    and

f_n = f_n-1 + f_n-2       for n>2

Given a set of distinct nonnegative integers, write a program to divide the set into 2 subsets: one of which all elements are in the Fibonacci sequence and the other of which all elements are not in the Fibonacci sequence.

Example

13        7         21       4          11        5          89        1234

5          13       21       89

4          7         11       1234

The input is defined in the DATA statement, and the output must be displayed to the screen, as in the following example.

Input

DATA 8    <Number of input, the maximum number of input is 100.>

DATA 13, 7, 21, 4, 11, 5, 89, 1234     <The maximum integer value is 30000.>

Output

5    13   21   89       <All elements are in the Fibonacci sequence.>

                        <blank line>

4    7    11   1234     <All elements are not in the Fibonacci sequence.>

Problem 2

Sentence Replacement 

Write a program to translate input sentences using a given replacement rules.

Replacement rules and the input sentences to be translated are given in the input as following.

Input:

Number of replacement rules (n)

word_a1 word_b1

word_a2 word_b2                     (word_ai will be replaced by word_bi for 1 ≤ i ≤ n )

word_an    word_bn

Number of sentences (m)

sentence ₁

sentence ₂

:

sentence _m

Output:

modified sentence ₁

modified sentence ₂

:

modified sentence _m

Assume that 1 ≤ n ≤ 50 and 1 ≤ m ≤ 50. Each sentence is a string of not more than 200 ASCII characters. All replacement rules will be defined such that each word in the given sentence will be replaced at most once.

The input must be read from a file named test2.in as shown in the following example. The result must be written to an output file named test2.out.

Example

Input to be read from a test2.in file:

4

I We

will would

future past

up down

3

I suspect that there will be a significant number of institutions.

It has a lot of promise for the future.

Imagine stepping up to an automatic teller machine.

Output to the file test2.out:

We suspect that there would be a significant number of institutions.

It has a lot of promise for the past.

Imagine stepping down to an automatic teller machine.

Note that the whole word (not part of a word) will be replaced by another word according to he replacement rules. Each word is separated by white spaces which can be spaces, commas, colons, semicolons. dashes and periods.

Problem 3

Sum minimization

The input is a sequence of real numbers x₁, x₂, ..., x_n, such that n is even. Design and implement a program to partition the input into n/2 pairs in the following ways. For each pair, we compute the sum of its numbers. The program should find the partition that minimizes the maximum sum.

Input:

n    <number of inputs, the maximum of n is 500.>

x1

x2

:

xn

Output:

<List of output pairs and their sum>

<The value of the maximum sum for this list>

Example

Input:

DATA 6    <number of inputs>

DATA 25, 10, 5, 20, 3, 24

Output to the screen:

25   3    28   (25+3=28)

10   20   30   (10+20=30)

5    24   29   (5+24=29)

Note that the maximum sum of the above partition is 30.

The other partition for which the maximum sum is not minimized is:

25   10   35   (25+10=35)

5    20   25   (5+20=25)

3    24   27   (3+24=27)

The maximum sum of the above partition is 35.

Problem 4

Points in a polygon

Write a program to determine whether a given point is inside a given polygon or not.

The input consists of a given point and a given polygon. A polygon consists of a set of points (or vertices). The polygon is defined by an integer N > 2, representing the number of vertices in the set, followed by N input lines describing the points in the set. Each point description contains two nonnegative integer x and y separated by comma. The values of x and y will not exceed 100. The output file will contain only the word IN or OUT, representing whether the given point is in the polygon or not.

Assuming that if the given point is located at the corner or on the border line of the polygon, that given point is also considered to be IN the polygon.

Example:

Input:

DATA 50, 60   <The given point to be checked.>

DATA 5        <The number of the vertices of the polygon, the maximum is 300.>

DATA 20, 20   <List of points>

DATA 30, 80

DATA 60, 90

DATA 70, 40

DATA 50, 40

Output to the screen:

IN