It is known that ln2 = a, ln3 = b. Express log18 24 in terms of a and b.
a) 3a + b b) 3a + b / a + 2b c) a3 + b / a + b2 d) a + 3b / 2a + b
Entry level (2 points)
Which of the following numbers does the set of values include y = 16-x + 4?
a) 4 b) –0.5 c) 5 d) 1
Entry level (1 point)
Which of the following numbers is the solution of the inequality cos x < 1/2?
a) 3 b) 6 c) –1 d) 1
Entry level (1 point)
Cowboy John hits a fly on the wall with a probability of 0.9 if he shoots with an adjusted revolver.
If John fires an unadjusted revolver, then he hits a fly with a probability of 0.3. There are 10 revolvers on the table,
only two of them are adjusted. Cowboy John sees a fly on the wall, grabs the revolver at random, and shoots the fly.
Find the probability of John missing.
a) 0.58 b) 0.42 c) 0.7 d) 0.1
Entry level (2 points)
Let |p⃗| = 2, |q⃗| = 5, cos(p⃗, q⃗) = -0.3. Which of the following is the scalar square of the vector 3p⃗ − q⃗?
a) 59 b) 69 c) 79 d) 89
Intermediate level (5 points)
Which of the following is the sum of even numbers belonging to the increasing interval of the function y = (x - 15)2 / (x - 12)3 + 23/81?
a) 44 b) 54 c) 64 d) 74
Intermediate level (5 points)
In some tree, the degree of each vertex is either 1 or 5. The number of vertices of degree 5 is 30.
Each vertex of degree 5 is connected either to four vertices of degree 1 and one of degree 5, or to five vertices of degree 5.
Such vertices are called weak and strong, respectively. Answer the following:
1. How many vertices are there in such a tree?
2. Find the number of the strong vertices.
3. Let the length of each edge be 1. Assuming that each strong vertex is adjacent to at most two other strong vertices,
calculate the greatest path length between the two weak vertices.
1. How many vertices are there in such a tree? 2. Find the number of the strong vertices. 3. Calculate the greatest path length between the two weak vertices.
Advanced level (14 points)
Computer Science and Information Systems
Two-digit consecutive binary numbers 00, 01, 10, 11, were used to encode the letters A, B, C, and D, respectively. Which number will represent the sequence DBAC, if the result is provided in hexadecimal notation?
a) A1 b) B2 c) C3 d) D2
Entry level (2 points)
A message was encoded using a variable-length cipher: A – 10, B – 11, C – 100, D – 101. After encoding, the resulting binary cipher was converted to hexadecimal and received: B7216. Which of the following is the encrypted message?
a) DABCA b) ADABC c) BCADA d) DABDA
Entry level (2 points)
Binary codes are assigned to five letters of the Latin alphabet, with some letters using two-bit codes and others using three-bit codes. These codes are shown in the table below:
a) acdbe b) acdeb c) cadeb d) daceb
Entry level (2 points)
Consider a three-letter alphabet {K, O, T}. How many different five-character-long sequences containing exactly two O's are possible?
a) 70 b) 80 c) 90 d) 100
Entry level (2 points)
List all decimal natural numbers not exceeding 17 that end in two identical digits when written in the ternary number system. Provide the numbers in ascending order and separate them with commas.
a) 5, 9, 12, 13, 17 b) 5, 9, 11, 12, 16 c) 4, 8, 9, 13, 17 d) 4, 10, 12, 13, 16
Entry level (2 points)
An image with dimensions of 128 by 256 pixels requires 24 KB of memory (excluding compression). Determine the maximum number of colors that can be used in the image palette.
a) 32 b) 64 c) 128 d) 256
Intermediate level (3 points)
There are 𝑛 points with integer coordinates on a number line. A grasshopper starts at the leftmost point and needs to reach the rightmost point. It can make jumps of the same length, but must land on one of the specified points with each jump. The grasshopper can make no more than 𝑛 jumps. Find the minimum jump length that allows the grasshopper to reach the rightmost point.
Example #1
Standard input Standard output 5 3 2 1 2 3 4 5
Example #2
Standard input Standard output 9 3 4 1 3 4 5 7 8 9 10 13
Solution:
Let us consider all possible jump lengths: the distance from the first point to the second point, the distance from the first point to the third point, and so on. For each jump length, points should be connected, starting from the first point and checking whether a point exists at the position equal to the sum of the coordinate of the current point and the length of the jump. If such a point does not exist, it is impossible to get to the rightmost point; otherwise, we should move to the point whose existence is established. If it is possible to reach the rightmost point in this way, covering no more than k segments, the jump length in question is the answer.
A = input().split()
n = int(A[0])
k = int(A[1])
x = input().split()
for i in range(n):
x[i] = int(x[i])
for i in range(1, n):
len = int(x[i]) - int(x[0])
cnt = 0
now = x[0]
# We try to consistently reach the end with such jumps
while (now != x[n - 1]):
now += len
if now not in x:
cnt = -1
break
cnt = cnt + 1
# If the answer is found at any step, we interrupt the loop.
if cnt != -1 and cnt <= k:
print(len)
break
Answer: The program implements the logic to find the correct minimum jump length.
Evaluation criteria:
A syntactically correct program is worth 2 points.
A program implementing a suboptimal (slow) algorithm earns 4 points.
A program implementing an optimal (fast) algorithm earns 4 points.
Advanced level (10 points)
Computer Science and Artificial Intelligence
Which function is used in Python to convert a string or tuple to a list?
a) zip() b) map() c) sum() d) list()
Entry level (1 point)
Determine the output of the following Python program:
string = "Cossack treasure boar pose awl treasure pose retelling awl carp pose treasure"
keyword = "sure"
found_words = []
for word in string.split():
if not keyword in word:
found_words.append(word)
count = [0] * len(found_words)
i = 0
res = []
for word1 in found_words:
for word2 in found_words:
if word1 == word2:
count[i] = count[i] + 1
if count[i] > 2:
if not word1 in res:
res.append(word1)
i = i + 1
print(res)
a) pose b) treasure c) awl d) Cossack
Intermediate level (3 points)
A function describing the operation of a single-layer neural network is written in Python:
def simple_perceptron(input_data : list) -> float:
if len(input_data) > 2:
raise Exception("Invalid input data length!")
weight = [0.5, 0.2]
result = 0.0
for x, w in zip(input_data, weight):
result = result + x * w
result = result - 0.4
if result > 0:
return 1
else:
return 0
a) Inputs: [0, 0], [1, 1]; Outputs: 0, 1 b) Inputs: [0, 0], [0, 1]; Outputs: 0, 1 c) Inputs: [0, 0], [1, 0]; Outputs: 0, 1 d) Inputs: [0, 0], [1, 1, 1]; Outputs: 0, 1
Intermediate level (3 points)
A Python function calculates the standard deviation for each of two features within each of two classes ('A' and 'B').
X = [[-1, -1], [-2, -2], [1, 1], [2, 2]] #
y = ['A', 'A', 'B', 'B']
classes = ['A','B']
cls_counts = [2, 2]
n_classes = 2
priors = [c_i / len(y) for c_i in cls_counts]
sum_class_a = [0]*2
sum_class_b = [0]*2
for x_i, y_i, i in zip(X, y, range(len(y))):
if y_i == 'A':
sum_class_a[0] = sum_class_a[0] + x_i[0]
sum_class_a[1] = sum_class_a[1] + x_i[1]
else:
sum_class_b[0] = sum_class_b[0] + x_i[0]
sum_class_b[1] = sum_class_b[1] + x_i[1]
X_cls_mean = []
X_cls_mean.append([s / cls_counts[0] for s in sum_class_a])
X_cls_mean.append([s / cls_counts[1] for s in sum_class_b])
sum2_class_a = [0]*2
sum2_class_b = [0]*2
for x_i, y_i, i in zip(X, y, range(len(y))):
if y_i == 'A':
sum2_class_a[0] = sum2_class_a[0] + (x_i[0] - X_cls_mean[0][0])**2
sum2_class_a[1] = sum2_class_a[1] + (x_i[1] - X_cls_mean[0][1])**2
else:
sum2_class_b[0] = sum2_class_b[0] + (x_i[0] - X_cls_mean[1][0])**2
sum2_class_b[1] = sum2_class_b[1] + (x_i[1] - X_cls_mean[1][1])**2
X_stds = []
X_stds.append([(s / cls_counts[0]) ** 0.5 for s in sum2_class_a])
X_stds.append([(s / cls_counts[1]) ** 0.5 for s in sum2_class_b])
print("X_stds",X_stds)
a) X_stds[0] = [0.7071067811865476, 0.7071067811865476] b) X_stds[1] = [0.5, 0.5] c) X_stds[0] = [0.5, 0.5] d) X_stds[1] = [0.7071067811865476, 0.7071067811865476]
Intermediate level (3 points)
Interdisciplinary Applications of Computer Science
Vasya is creating 5-letter words using the letters A, B, C, and D, with the constraint that the letter A must appear exactly once. The other letters (B, C, D) can appear any number of times or not at all. A word is any valid sequence of letters, not necessarily meaningful. Determine the number of such possible words.
a) 230 b) 118 c) 225 d) 405
Entry level (1 point)
Olga is creating a table of code words for transmitting messages, each message having its own code word. She uses as code words 4-letter words that contain only the letters A, B, C, D, X, and Y. The first letter of a code word must be X or Y, and neither of these two letters can appear in any other position in the code word. How many different code words can Olga use?
a) 192 b) 128 c) 256 d) 214
Entry level (2 points)
What is the minimum amount of storage (in KB) required to save a 128×128 pixel bitmap image that can use 256 different colors?
a) 10 b) 16 c) 128 d) 64
Entry level (1 point)
After converting a bitmap image file, its size was reduced by half. Determine the maximum number of colors that could have been in the original palette, given that the converted bitmap image, which has the same resolution, uses a 16-color palette.
a) 64 b) 128 c) 256 d) 512
Intermediate level (3 points)
Computer Science and Software Engineering
Which is the correct order of use for software development tools?
a) linker; debugger; compiler; editor; profiler b) editor; compiler; linker; debugger; profiler c) profiler; linker; debugger; compiler; editor d) editor; linker; compiler; debugger; profiler
Entry level (1 point)
Arrange the following Git commands in the correct order for performing a typical update of a program code on the server:
a) git push; git add; git commit; b) git commit; git push; git add; c) git add; git commit; git push;
Entry level (1 point)
Which of the following is the lowest base of a number system, where the number 50 is written in two digits?
a) 2 b) 6 c) 8 d) 10
Intermediate level (3 points)
An automatic camera takes bitmap images with a resolution of 640 × 480 pixels. The size of an image file cannot exceed 320 KB, and the data is uncompressed. What is the maximum number of colors that can be used in the palette?
a) 32 b) 16 c) 128 d) 256
Intermediate level (3 points)
A k-nearest neighbors algorithm assigns an object to the class that most of its k nearest neighbors belong to. Uncertainty is considered an error. Write a k-nearest neighbors algorithm for points on a plane, assuming that 𝑛 is an odd number and there are only two classes, labeled 0 and 1.
Input data format
In the first line, an integer is the number of points for which a class value is given.
In the second line, an integer is the number of neighbors.
In the third line, two integers represent the coordinates of the point whose class is to be defined.
In each subsequent line, there are three integers: the first two are the coordinates of the object, and the third is the class number.
Output data format
A number: the number of the class to which the algorithm has assigned the object (the number 0 or 1).
Example
Standard Input
Standard Output
4
0
1
1 1
1 2 0
2 5 0
4 8 1
1 5 0
Solution:
For the point you want to classify, measure all the distances to other points. Select k points with the smallest distances. Indicate the class to which most of the selected k points belong.
Answer:
n = int(input())
k = int(input())
x0, y0 = map(int, input().split())
coordinates = []
class_labels = []
for i in range(n):
x, y, point_class = map(int, input().split())
class_labels.append(point_class)
coordinates.append([x, y])
def distance(x1, x2):
return ((x1[0]-x2[0])**2 + (x1[1]-x2[1])**2)**(0.5)
nearest_neighbors = []
neighbors_distances = []
neighbors_classes = []
for i in range(k):
nearest_neighbors.append(coordinates[i])
neighbors_distances.append(distance([x0, y0], coordinates[i]))
neighbors_classes.append(class_labels[i])
'''
Searching for k nearest neighbors.
'''
for i in range(k, n):
for j in range(k):
if distance([x0, y0], coordinates[i]) < neighbors_distances[j]:
neighbors_distances[j] = distance([x0, y0], coordinates[i])
nearest_neighbors[j] = coordinates[i]
neighbors_classes[j] = class_labels[i]
point_class = 0
if neighbors_classes.count(1) > neighbors_classes.count(0):
point_class = 1
print(point_class)
Evaluation criteria:
A syntactically correct program earns 2 points.
A program implementing a suboptimal (slow) algorithm earns 4 points.
A program implementing the optimal (fast) algorithm is worth 4 points.
Advanced level (10 points)
Computer Science, Hardware, and Architecture
Which of the following methods is used for long-term storage of user information?
a) external storage devices b) catalogs and libraries c) processors d) floppy disks e) random access memory
Entry level (1 point)
Which device is shown in the picture?
a) processor b) solid state drive c) random access memory d) network card e) video card
Entry level (1 point)
Which of the following is NOT a part of the microprocessor?
a) access Point Management Module (OSDP) b) arithmetic logic unit (ALU) c) control unit (CU) d) read-only memory (ROM)
Entry level (1 point)
Which of the following represents the number 26586 in the hexadecimal system?
a) 67AD b) 673F c) 65AC d) 67DA e) 642D f) 66411
Intermediate level (3 points)
Telecommunications
To encode a message consisting only of the letters A, B, C, D, and E, a non-uniform binary code is used:
A: 000, B: 11, C: 01, D: 001, E: 10.
Which (only one!) of the four received messages was transmitted without errors and can be decoded (specify the message number):
a) 110000010011110 b) 110000011011110 c) 110001001001110 d) 110000001011110
Entry level (1 point)
To encode a message consisting of the letters X, W, Y, and Z, the following two-digit binary numbers were used:
00 for X, 01 for W, 10 for Y, and 11 for Z. What will one obtain by encoding the character sequence YXZXWX in this way and writing the result in the hexadecimal code?
a) 434 b) 4B8 c) 8B4 d) 8X4
Entry level (1 point)
To encode the letters K, L, M, and N, four-digit consecutive binary numbers from 1000 to 1011, respectively, were used.
What will one obtain by encoding the KMLN characters in this way and writing the result in octal code?
a) 846138 b) 1052338 c) 123458 d) 7763258
Entry level (1 point)
How many seconds does it take a modem sending messages at 14400 bps to transmit a 640 × 480 pixel color bitmap image, assuming that the color of each pixel is encoded in 24 bits?
a) 64 b) 128 c) 256 d) 512
Intermediate level (3 points)
