ACSL Contest 1

ACSL Nov 24, 2019

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

Question TypeNumber of Questions
Computer number systems2
Recursive Functions2
What does this program do1

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

2018-2019 Intermediate Question 1

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

2018-2019 Senior Question 1

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:

2017-2018 Senior Question 1
2018-2019 Intermediate Question 2

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

Denary numberBinary NumberDoes 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

2018-2019 Intermediate Question 3

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

2017-2018 Intermediate Question 4

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

2018-2019 Senior Question 4

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

2017-2018 Senior Question 3

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

Figure No.1-side perimeter2-sided perimetersNumber of triangles
1301
2604
36310
49319
59631
612646
712964

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:

2017-2018 Senior Question 1

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

abcdefOutput
022-14
022-142
042-142
1642-142
442-142
442-1242
642-1242
6202-1242
6102-1242
36102-1242
36104-1242
36104-12424

Hence the answer to this question is 4.

Daniel Zhao

The greatest pigeon in SCIE who would always gugugu whenever, wherever, and whatever.

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.