# ACSL Contest 1

In ACSL Contest 1, questions would mainly cover the following three topics.

Question Type | Number of Questions |
---|---|

Computer number systems | 2 |

Recursive Functions | 2 |

What does this program do | 1 |

These topics would be covered in the following pages.

**Next page: Computer Number Systems**

[latexpage]

## Computer Number Systems

In this part of the contest, you would mainly be required to calculate and convert between different number systems. The number of systems that would be covered in the contest mainly includes the following four number system:

- Binary (Base-2)
- Octonary (Base-8)
- Denery (Base-10)
- Hexidecimal (Base-16)

Since we have covered the conversion of binary, denary and hexadecimal in here, I would only talk about a little bit of octonary.

### Conversion between Octonary and Denary

When converting a number from denary into octonary, what you could do is by constantly dividing the denary number by 8 to obtain the results: Let’s look at the following example:

$$

1034_{10}=?_{8}

$$

In this case, we will have to convert the denary number 1034 to octonary. Therefore, we could just constantly divide the number by 8 and finds the remainder we have. From there we could read the numbers bottom-up to find the answer as the graph suggests:

From there we could obtain the result that:

$$

1034_{10}=2012_{8}

$$

We could check our answer using the conversion the other way round. When converting the octonary numbers back to denary, you could just multiply each digit by $8^{n}$, where n represents the position of the bit and 0 at the right. Hence, the octonary number $2012_{8}$ would be equal to $2\times8^{0}+1\times8^{1}+0\times8^{2}+2\times8^{3}$. The result would give you $1034_{10}$, which is the same as our initial result.

### Converting Between Octanary and Binary

When converting octonary to binary, you could just simply convert every digit of the octonary into the corresponding binary. Let’s look at the following example:

$$

315_{8}=?_{2}

$$

To solve this, you could just simply convert every digit and make it into binary. which would give the following:

\begin{align*}

3_{8}&=011_{2} \\

1_{8}&=001_{2} \\

5_{8}&=101_{2} \\

\end{align*}

Combining the digits in order gives you the result:

$$

315_{8}=011001101_{2}=11001101_{2}

$$

When converting the other way, consider the value of the binary number from the right side, convert every three digits into octonary and add leading zeros when needed. For example, consider the following conversion:

$$

1110010001_{2}=?_{8}

$$

When converting the number system, what you would consider doing would be converting every three bits. This would look like the following:

$$1110010001_{2}=|001|110|010|001|_{2}$$

\begin{align*}

001_{2}&=1_{8} \\

010_{2}&=2_{8} \\

110_{2}&=6_{8} \\

001_{2}&=1_{8} \\

\end{align*}

Hence the result of the conversion is:

$$

1110010001_{2}=1621_{8}

$$

### Converting between Octonary and Hexadecimal

When converting between octonary and hexadecimal bases, you could not change directly in most cases. Hence you should consider using binary as a “bridge”. In this way, the amount of calculation required would be lower.

### Question Examples

By understanding the above four number systems, you could complete nearly 90% of the questions which are purely number system conversions. Some other questions would include conversions of other number systems and some would be including mathematics. Here we would give three examples, one for each type of question.

#### Example 1: Conversion between the four main number systems

To solve this question the easiest way is by first convert the hexadecimal number into a binary number and convert the binary number back to octonary. Hence the process would look like this:

#### Example 2: Conversion between other number systems and the four main number system

To solve this question you could first convert the octonary into denary number and then convert it to the base 20 system. This could be done like this:

#### Example 3: Others

This example is only an example, there are way more other examples and they are all different. But the way to approach is the same. Let’s look at an example:

This is basically a question that asks you to list all the possible answers. Hence it could look like this:

Denary number | Binary Number | Does it satisfy the question? |
---|---|---|

$1_{10}$ | $1_{2}$ | Y |

$2_{10}$ | $10_{2}$ | N |

$3_{10}$ | $11_{2}$ | Y |

$4_{10}$ | $100_{2}$ | N |

$5_{10}$ | $101_{2}$ | Y |

$6_{10}$ | $110_{2}$ | Y |

$7_{10}$ | $111_{2}$ | Y |

$8_{10}$ | $1000_{2}$ | N |

$9_{10}$ | $1001_{2}$ | N |

$10_{10}$ | $1010_{2}$ | N |

$11_{10}$ | $1011_{2}$ | Y |

$12_{10}$ | $1100_{2}$ | N |

$13_{10}$ | $1101_{2}$ | Y |

$14_{10}$ | $1110_{2}$ | Y |

$15_{10}$ | $1111_{2}$ | Y |

$16_{10}$ | $10000_{2}$ | N |

$17_{10}$ | $10001_{2}$ | N |

$18_{10}$ | $10010_{2}$ | N |

$19_{10}$ | $10011_{2}$ | Y |

$20_{10}$ | $10100_{2}$ | N |

$21_{10}$ | $10101_{2}$ | Y |

$22_{10}$ | $10110_{2}$ | Y |

$23_{10}$ | $10111_{2}$ | Y |

$24_{10}$ | $11000_{2}$ | N |

$25_{10}$ | $11001_{2}$ | Y |

$26_{10}$ | $11010_{2}$ | Y |

$27_{10}$ | $11011_{2}$ | Y |

$28_{10}$ | $11100_{2}$ | Y |

$29_{10}$ | $11101_{2}$ | Y |

$30_{10}$ | $11110_{2}$ | Y |

$31_{10}$ | $11111_{2}$ | Y |

Hence there are a total of 20 numbers available.

**Next page: Recursive functions**

[lataxpage]

## Recursive functions

The next topic in the contest covers recursive functions. For this part, there is barely any skill or knowledge to learn. All you have to know about is mathematics and how to prevent calculation errors without a calculator. Therefore, I would just jump to the questions and let’s learn by example:

### Example 1

To solve this question, the easiest approach is just simply to calculate the answer.

Hence we could obtain the following:

\begin{align*}

f(20)&=f(f(20-2))+1=f(f(18))+1 \\

f(18)&=f(f(18-2))+1=f(f(16))+1 \\

f(16)&=f(f(16-2))+1=f(f(14))+1 \\

f(14)&=f(\lfloor14/2\rfloor)-1=f(7)-1 \\

f(7)&=\lfloor7/2\rfloor=3 \\

f(14)&=3-1=2 \\

f(16)&=f(2)+1 \\

f(2)&=\lfloor2/2\rfloor=1 \\

f(16)&=1+1=2 \\

f(18)&=f(2)+1=1+1=2 \\

f(20)&=f(2)+1=1+1=2

\end{align*}

Hence the solution for this problem would be 2.

### Example 2

The only approach for this would be to try to approach it to step by step:

\begin{align*}

f(12,7)&=f(11,9)+3 \\

f(11,9)&=f(10,11)+3 \\

f(10,11)&=2\cdot f(11,10)-5 \\

f(11,10)&=f(10,12)+3 \\

f(10,12)&=2\cdot f(11,11)-5 \\

f(11,11)&=11\cdot11+11=132 \\

f(10,12)&=2\cdot132-5=259 \\

f(11,10)&=259+3=262 \\

f(10,11)&=2\cdot262-5=519 \\

f(11,9)&=519+3=522 \\

f(12,7)&=522+3=525

\end{align*}

Hence the answer for the question is 525.

Besides this type of ~~easy~~ straight forward questions, there is still some type of questions where you would have to apply your knowledge to different application questions. Here are two examples for you to consider.

### Example 3

At first glance, these questions seemed to have no relationship with recursive functions. You could solve this problem by using only mathematics. You could just simply list down the heights and the total heights to find the result like this:

Hence you could know the result easily.

### Example 4

For this question, we could layout a table to consider what the figure would look like.

Figure No. | 1-side perimeter | 2-sided perimeters | Number of triangles |
---|---|---|---|

1 | 3 | 0 | 1 |

2 | 6 | 0 | 4 |

3 | 6 | 3 | 10 |

4 | 9 | 3 | 19 |

5 | 9 | 6 | 31 |

6 | 12 | 6 | 46 |

7 | 12 | 9 | 64 |

Hence the answer would be 64.

**Next page: What Does This Program Do?**

## What Does This Program Do?

Being the last section of the first contest, this is, in fact, the easiest question in the whole paper. The question consists of a question writing in pseudocode and asks you to find its output. Being much easier than the pseudocode in CIE, this code is similar to Python. The only differences are: they use `output`

for output, and use `↑`

to represent a power statement, while the number at the front represents the base and the number at the back represents the exponential. An example could help you to understand how to deal with this type of question:

To solve this problem, we could draw out the following trace table:

a | b | c | d | e | f | Output |
---|---|---|---|---|---|---|

0 | 2 | 2 | -1 | 4 | ||

0 | 2 | 2 | -1 | 4 | 2 | |

0 | 4 | 2 | -1 | 4 | 2 | |

16 | 4 | 2 | -1 | 4 | 2 | |

4 | 4 | 2 | -1 | 4 | 2 | |

4 | 4 | 2 | -1 | 24 | 2 | |

6 | 4 | 2 | -1 | 24 | 2 | |

6 | 20 | 2 | -1 | 24 | 2 | |

6 | 10 | 2 | -1 | 24 | 2 | |

36 | 10 | 2 | -1 | 24 | 2 | |

36 | 10 | 4 | -1 | 24 | 2 | |

36 | 10 | 4 | -1 | 24 | 2 | 4 |

Hence the answer to this question is 4.