CmsD company produces various kinds of construction toys. Using
a new set, children can build racing speedways for Legocars. The speedways
are closed loops with no self-crossing. They are built by connecting two
type of elements:
-- "A" type elements in a form of a straight line segment by
a unit length;
-- "B" type elements in a form of an arc, which is a quarter
part of a circle by a unit radius.
It is permitted to join together two "A" elements, or one "A"
with one "B" element. It is not permitted to join together two
"B" elements. Using "B" elements, we can build left
or right turns of +90 or -90 degrees.
The following problems are proposed:
Given p "A" type elements and q "B" type elements, built (if possible) n speedways, using the maximal number of "B" elements and no more than p "A" elements.
Save into a text file the results obtained in the previous problem. Render on the computer screen the first k speedways you have built.
Within a plain rectangle with sides i and j, build a speedway as long as possible. Your program should output the speedway, its length and the area of the domain surrounded by the speedway.
Remark: The values of p, q, n, k, i and j, which are integers, are entered by the keyboard.
Tests:
| p | q | n | k | i | j | |
| Test 1 | 3 | 4 | 2 | 2 | 6 | 6 |
| Test 2 | 5 | 5 | 2 | 2 | 7 | 8 |
| Test 3 | 12 | 6 | 6 | 6 | 7 | 8 |
| Test 4 | 10 | 9 | 6 | 6 | 7 | 11 |
A binary tree is called strictly binary (SBT) if each its node has 0 or 2 descenders. Let us consider a SBT having N (N <= 10) leaves (i.e. nodes without descenders), so that each leaf is defined by a path from the root to the leaf itself. Every such path is encoded as a binary string. The sign 0 means a left descender, whereas the sign 1 means a right one. An example is given below.
A ABD -> 00
/ \ ABEH -> 010
B C ABEI -> 011
/ \ / \ ACF -> 10
D E F G ACG -> 11
/ \
H I
In the next problems we suppose that each leaf has an assigned positive integer to itself.
a) Input the data for a given SBT from a text file. Data for each leaf are placed on a separate row of the file and are of the form: Path Delimiter Number, where
Path is a binary string, specifying a path to the leaf.
Delimiter stands for one or more spaces.
Number is a positive integer, which was assigned to the leaf.
b) Render in an appropriate way on the computer screen the tree you have inputted.
After entering a positive interger V by the keybord, create all algebraic expressions having this value V, so that the corresponding binary tree of any such expression is the same as the inputted SBT. Assume the only allowed operations in the expressions are addition, multiplication and integer division.
Create all algebraic expressions having the smallest possible value greater than zero, so that the corresponding binary tree of any such expression is the same as the inputted SBT. Assume the only allowed operations in the expressions are the same as in the previous problem.
Test examples:
Test 1:
0 1
1 3
V = 0, V_min = 3.
Answers:
EXPR = 1/3 ?
EXPR_min = 1*3 / \
1 3
Test 2:
1 10
100 6
101 4
11 10
V = 0, V_min = 1.
Answers:
EXPR = 10+((6/4)/10) ?
EXPR = 10*((6+4)/10) / \
EXPR = 10/((6+4)/10) 10 ?
EXPR_min = 10/((6/4)*10) / \
? 10
/ \
6 4
Test 3:
000 3
001 1
01 2
1 1000
V = 5000, V_min = 1000.
Answers:
EXPR = ((3*1)+2)*1000 ?
EXPR = ((3/1)+2)*1000 / \
EXPR_min = ((3*1)/2)*1000 ? 1000
EXPR_min = ((3/1)/2)*1000 / \
? 2
/ \
3 1
Test 4:
000 0
001 0
010 0 ?
011 0 / \
100 0 ? ?
100 0 / \ / \
101 0 ? ? ? ?
110 0 / \ / \ / \ / \
111 0 0 0 0 0 0 0 0 0
V = 1.
Answers:
No solution.
Source: Obuchenieto po matematika i informatika, journal published by Bulgarian Ministry of Education, n. 5, 1993, pp. 57-59.
© The text is translated from Bulgarian by Emil Kelevedzhiev.
Return to the Home Page of Bulgarian Mathematics and Informatics Competitions.