SPECIFICATION
control measuring materials
Unified State Exam 2019
in computer science and ICT

1. Purpose of KIM Unified State Exam

The Unified State Exam (hereinafter referred to as the Unified State Exam) is a form of objective assessment of the quality of training of persons who have mastered educational programs secondary general education, using tasks of a standardized form (control measuring materials).

The Unified State Examination is conducted in accordance with the Federal Law of December 29, 2012 No. 273-FZ “On Education in the Russian Federation.”

Control measuring materials make it possible to establish the level of mastery by graduates of the Federal component of the state standard of secondary (complete) general education in computer science and ICT, basic and specialized levels.

The results of the unified state exam in computer science and ICT are recognized by educational organizations of secondary vocational education and educational organizations of higher professional education as the results of entrance tests in computer science and ICT.

2. Documents defining the content of the Unified State Exam KIM

3. Approaches to selecting content and developing the structure of the Unified State Exam KIM

The content of the assignments is developed on the main topics of the computer science and ICT course, combined into the following thematic blocks: “Information and its coding”, “Modeling and computer experiment”, “Number systems”, “Logic and algorithms”, “Elements of the theory of algorithms”, “Programming” "," Computer Architecture and computer networks", "Processing of numerical information", "Technologies for searching and storing information."
The content of the examination paper covers the main content of the computer science and ICT course, its most important topics, the most significant material in them, which is clearly interpreted in most versions of the computer science and ICT course taught at school.

The work contains both tasks of a basic level of complexity, testing knowledge and skills provided for by the basic level standard, and
and tasks of increased and high levels of complexity, testing knowledge and skills provided for by the profile level standard. The number of tasks in the CMM version should, on the one hand, provide a comprehensive test of the knowledge and skills of graduates acquired over the entire period of study in the subject, and, on the other hand, meet the criteria of complexity, stability of results, and reliability of measurement. For this purpose, CMM uses two types of tasks: with a short answer and a detailed answer. The structure of the examination paper ensures an optimal balance of tasks different types and varieties, three levels of difficulty, testing knowledge and skills at three different levels: reproduction, application in a standard situation, application in a new situation. The content of the examination paper reflects a significant part of the content of the subject. All this ensures the validity of the test results and the reliability of the measurement.

4. Structure of KIM Unified State Exam

Each version of the examination paper consists of two parts and includes 27 tasks that differ in form and level of difficulty.

Part 1 contains 23 short answer questions.

The examination paper offers the following types of short-answer tasks:

tasks for choosing and recording one or more correct answers from the proposed list of answers;
tasks to calculate a certain value;
tasks to establish the correct sequence, presented as a string of characters according to a specific algorithm.

The answer to the tasks of Part 1 is given by the corresponding entry in the form of a natural number or a sequence of characters (letters and numbers), written without spaces or other separators.

Part 2 contains 4 tasks with detailed answers.

Part 1 contains 23 tasks of basic, advanced and high difficulty levels. This part contains short-answer tasks that require you to independently formulate and write the answer in the form of a number or a sequence of characters. The assignments test the material of all thematic blocks. In part 1, 12 tasks belong to the basic level, 10 tasks to an increased level of complexity, 1 task to a high level of complexity.

Part 2 contains 4 tasks, the first of which is of an increased level of complexity, the remaining 3 tasks are of a high level of complexity. The tasks in this part involve writing a detailed answer in free form.

Demonstration versions of the Unified State Examination in computer science for grade 11 for 2004 - 2014 consisted of three parts. The first part included tasks in which you need to choose one of the proposed answers. The tasks from the second part required a short answer. For the tasks from the third part it was necessary to give a detailed answer.

In 2013 and 2014 in demo versions of the Unified State Exam in computer science the following were introduced changes:

was in the second part of the work.

In 2015 in demo version in computer science was the structure of the variant has been changed and optimized generally:

The option became consist of two parts(part 1 - short answer assignments, part 2 - ).

Numbering tasks became through throughout the entire version without letter designations A, B, C.

Was The form of recording the answer in tasks with a choice of answers has been changed: The answer now needs to be written down in a number with the number of the correct answer (rather than marked with a cross).

Was the total number of tasks has been reduced (from 32 to 27); was reduced from 40 to 35 maximum quantity primary points.

The number of tasks was reduced due to enlargement of assignment topics, information related to the topic and complexity of tasks in one position. Such enlarged positions became: No. 3 (storing information in a computer), No. 6 (formal execution of algorithms), No. 7 (technology of calculations and data visualization using spreadsheets) and No. 9 (transmission speed of sound and graphic files) . IN demo version 2015 presented some examples of each of tasks 3, 6, 7 and 9. In real options for each of these positions it was proposed only one exercise.

Was the sequence of tasks has been changed.
That part of the work that contained long-answer assignments, hasn't changed.

IN demo version of the Unified State Exam in computer science 2016 compared to the 2015 computer science demo no significant changes: Only the sequence of tasks 1-5 has been changed.

IN demo version of the Unified State Exam in computer science 2017 compared to the 2016 computer science demo there were no changes.

IN demo version of the 2018 Unified State Exam in computer science compared to the 2017 demo version in computer science, the following were introduced changes:

In task 25 removed opportunity writing an algorithm in natural language,

Examples texts of programs and their fragments in the conditions of tasks 8, 11, 19, 20, 21, 24, 25 in C language are replaced with examples in C++ language.

IN demonstration Unified State Exam options 2019-2020 in computer science compared to the 2018 computer science demo there were no changes.

Secondary general education

Informatics

Demo version of the Unified State Exam 2019 in computer science and ICT

We bring to your attention an analysis of the demo version of the 2019 Unified State Exam in computer science and ICT. This material contains explanations and a detailed solution algorithm, as well as recommendations for the use of reference books and manuals that may be needed when preparing for the Unified State Exam.

You can download the demo version of the Unified State Examination in computer science for graduates of 2019 using the link below:

Read about innovations in exam options in other subjects.

The manual contains tasks that are as close as possible to the real ones used on the Unified State Exam, but distributed by topic in the order they are studied in the 10th-11th grades of high school. By working with the book, you can consistently work through each topic, eliminate gaps in knowledge, and systematize the material being studied. This structure of the book will help you prepare more effectively for the Unified State Exam.

Demo-KIM Unified State Exam 2019 in computer science has not undergone any changes in its structure compared to 2018. This significantly simplifies the teacher’s work and, of course, the student’s already built (I’d like to count on it) plan for preparing for the exam.

In this article we will consider the solution to the proposed project (at the time of writing this article is still a PROJECT) KIM Unified State Exam in computer science.

Part 1

The answers to tasks 1–23 are a number, a sequence of letters or numbers that should be written in ANSWER FORM No. 1 to the right of the number of the corresponding task, starting from the first cell, without spaces, commas or other additional characters. Write each character in a separate box in accordance with the samples given in the form.

Task 1

Calculate the value of the expression 9E 16 – 94 16.

In your answer, write the calculated value in decimal system Reckoning.

Solution

Simple arithmetic in hexadecimal:

Obviously, the hexadecimal digit E 16 corresponds to the decimal value 14. The difference in the original numbers gives the value A 16. The solution has, in principle, already been found. Following the condition, we present the found solution in the decimal number system. We have: A 16 = 10 10.

Answer: 10.

Task 2

Misha filled out the truth table of the function (¬x /\ ¬y) \/ (y≡z) \/ ¬w, but only managed to fill out a fragment of three different lines, without even indicating which column of the table corresponds to each of the variables w, x , y, z.

Determine which table column each variable w, x, y, z corresponds to.

In your answer, write the letters w, x, y, z in the order in which their corresponding columns appear (first the letter corresponding to the first column; then the letter corresponding to the second column, etc.). Write the letters in the answer in a row; there is no need to put any separators between the letters.

Example. If the function were given by the expression ¬x \/ y, depending on two variables, and the table fragment would look like

then the first column would correspond to the variable y, and the second column would correspond to the variable x. The answer should have been written yx.

Answer: ___________________________.

Solution

Let's note that the function (¬x /\ ¬y) \/ (y≡z) \/ ¬w is essentially a disjunction of three “terms”:

Let us recall the truth table of the operation of logical “addition” (disjunction): the sum is “true” if at least one term is “true”, and “false” if both terms are “false”. This means that from the conditions of the task we conclude that each of the terms must be false. The third term - (¬w) - must be false, which gives us our first clue: the fourth column must be the variable w, since based on the values of the first, second and third columns, none of them can be the variable w.

Let's consider the second term of the function - (y≡z), - it should also be equal to 0. Therefore, it is necessary that in our columns of variables y and z there be different meanings. Taking into account the first term of the function (¬x /\ ¬y), we note that the variable z corresponds to the first column. The first term also indicates that the empty cells of the second and third columns should contain 1. Immediately, taking into account the second term, we will make another conclusion that the empty cell in the first column is equal to 1. It is this conclusion that allows us to make the final the conclusion that the second column corresponds to the variable y, and, accordingly, the third to the variable x.

Answer: zyxw.

Task 3

The figure on the left shows a road map of the N-rayon; in the table, an asterisk indicates the presence of a road from one settlement to another. The absence of an asterisk means that there is no such road.

Each settlement on the diagram corresponds to its number in the table, but it is not known which number. Determine which numbers of settlements in the table can correspond to settlements B and C in the diagram. In your answer, write down these two numbers in ascending order without spaces or punctuation.

Answer: ___________________________.

Solution

The diagram shows that each of points B and C is connected to three other points. This means that we need to find those numbers in the table settlements, opposite which there are three “stars” in rows (or in columns, taking into account symmetry). This condition corresponds to lines 2 and 6 (columns 2 and 6, respectively).

Answer: 26.

Task 4

Below are two fragments of tables from the database about residents of the microdistrict. Each row of table 2 contains information about the child and one of his parents. The information is presented by the value of the ID field in the corresponding row of Table 1. Based on the data provided, determine the largest difference between the birth years of the siblings. When calculating the answer, take into account only the information from the given fragments of the tables.

Answer: ___________________________.

Solution

The first thing you should pay attention to and not get confused is that we exclude male representatives (more precisely, we do not take them into account when counting female children): these are lines 64, 67, 70, 75, 77, 86 of Table 1.

Going through the fields of the tables, we find pairs of girl children:

Year of birth	Year of birth	Difference between years of birth

In response, we enter the largest of the two values of the difference between the years of birth.

Answer: 6.

Task 5

To encode a certain sequence consisting of the letters A, B, C, D, D, E, we decided to use a non-uniform binary code that satisfies the Fano condition. For the letter A, the code word 0 was used; for the letter B – code word 10. What is the smallest possible sum of the lengths of the code words for the letters B, D, D, E?

Note. The Fano condition means that no codeword is the beginning of another codeword. This makes it possible to unambiguously decrypt encrypted messages.

Answer: ___________________________.

Solution

To solve the problem, let's build a graph:

A codeword of length 2 - 11, or any of the codewords of length 3, will inevitably become the beginning of one of the words of length 4. The choice of length 4 is due to the fact that there was a need for encoding four letters. The resulting codewords together give a length of 16.

Answer: 16.

Task 6

The input of the algorithm is a natural number N. The algorithm constructs a new number R from it as follows.

A binary representation of the number N is constructed.
Two more digits are added to this entry on the right according to the following rule: if N is even, first zero and then one are added to the end of the number (on the right). Otherwise, if N is odd, first one is added to the right, and then zero.

For example, the binary representation 100 of the number 4 will be converted to 10001, and the binary representation 111 of the number 7 will be converted to 11110.

The record obtained in this way (it has two digits more than in the record of the original number N) is a binary record of the number R - the result of the work of this algorithm.

Specify the minimum number R that is greater than 102 and can be the result of this algorithm. In your answer, write this number in the decimal number system.

Answer: ___________________________.

Solution

Let's represent the number 102 in binary form: 1100110 2. We are interested in the number that will be greater. We will move “up” by adding one at a time:

1100111 2 – 103 10 – binary representation does not correspond to the algorithm;

1101000 2 – 104 10 – binary representation does not correspond to the algorithm;

1101001 2 – 105 10 – binary representation corresponds to the algorithm.

Answer: 105.

Task 7

Given fragment spreadsheet. The formula was copied from cell C3 to cell D4. When copying, the cell addresses in the formula automatically changed. What is the numerical value of the formula in cell D4?

Note. The $ sign denotes absolute addressing.

Answer: ___________________________.

Solution

When we copy the formula in cell D4, we get: =$B$3+E3. Substituting the values we get the desired result:

400+700, i.e. 1100.

Answer: 1100.

Task 8

Write down the number that will be printed as a result of the following program. For your convenience, the program is presented in five programming languages.

Answer: ___________________________.

Solution

Let's follow the changes in the values of the variables:

s = 0, n = 75 – values before the cycle;

s + n (75)< 150, s = s + 15 = 15, n = n – 5 = 70 – значения после первой итерации;

s + n (85)< 150, s = s + 15 = 30, n = n – 5 = 65 – значения после 2 итерации;

s + n (95)< 150, s = s + 15 = 45, n = n – 5 = 60 – значения после 3 итерации;

s + n (105)< 150, s = s + 15 = 60, n = n – 5 = 55 – значения после 4 итерации;

s + n (115)< 150, s = s + 15 = 75, n = n – 5 = 50 – значения после 5 итерации;

s + n (125)< 150, s = s + 15 = 90, n = n – 5 = 45 – значения после 6 итерации;

s + n (135)< 150, s = s + 15 = 105, n = n – 5 = 40 – значения после 7 итерации;

s + n (145)< 150, s = s + 15 = 120, n = n – 5 = 35 – значения после 8 итерации;

the loop is interrupted at the next step, the program displays the desired value.

Answer: 35.

Task 9

Automatic camera produces raster images size 200x256 pixels. The same number of bits are used to encode the color of each pixel, and the pixel codes are written to the file one after the other without gaps. The size of the image file cannot exceed 65 KB without taking into account the size of the file header. Which maximum quantity colors can be used in the palette?

Answer: ___________________________.

Solution

Let's start with some simple calculations:

200 × 256 – number of pixels of the raster image;

65 KB = 65 × 2 10 × 2 3 bits – the upper threshold for file size.

The ratio to will allow us to get the color depth of the pixel, i.e. the number of bits that are allocated to color coding for each pixel.

And finally, the desired value, which we determine using the classical formula:

2i = n, 2 10 .

Answer: 1024.

Task 10

Vasya composes 5-letter words that contain only the letters Z, I, M, A, and each word has exactly one vowel letter and it appears exactly 1 time. Each of the valid consonants can appear in a word any number of times or not at all. A word is any valid sequence of letters, not necessarily meaningful. How many words are there that Vasya can write?

Answer: ___________________________.

Solution

If it were not for the condition “there is exactly one vowel letter and it occurs exactly 1 time,” the problem would be solved quite simply. But there is this condition, and there are two different vowels.

This vowel can be in one of 5 positions. Let's assume she's in first position. Possible options in this case there are exactly 2 vowels in this position. In the remaining four positions we have two consonant options. Total options for the first case:

2 × 2 × 2 × 2 × 2 = 2 5 = 32

I repeat, there are exactly 5 options for the location of a vowel in our word. Total:

Answer: 160.

Task 11

Below, the recursive algorithm F is written in five programming languages.

Write down in a row, without spaces or separators, all the numbers that will be printed on the screen when calling F(4). The numbers must be written in the same order in which they are displayed on the screen.

Answer: ___________________________.

Solution

For clarity, let's build a tree:

Moving along this recursion tree, we obtain the value that will be the desired solution.

Answer: 1231412.

Task 12

In TCP/IP network terminology, a network mask is called binary number, which determines which part of the IP address of a network host refers to the network address, and which part refers to the address of the host itself in this network. Typically, the mask is written according to the same rules as the IP address - in the form of four bytes, and each byte is written in the form decimal number. In this case, the mask first contains ones (in the highest digits), and then from a certain digit there are zeros. The network address is obtained by applying a bitwise conjunction to the given host IP address and mask.

For example, if the host IP address is 231.32.255.131 and the mask is 255.255.240.0, then the network address is 231.32.240.0.

For a node with an IP address of 117.191.37.84, the network address is 117.191.37.80. What is the smallest possible value of the last (rightmost) byte of the mask? Write your answer as a decimal number.

Answer: ___________________________.

Solution

Let's write one below the other the binary representation of the last right byte of the IP address, network address and mask in accordance with the definition (in the top line, for convenience in further reference, the bits are numbered):



Mask – ?
Network address

We will move from right to left, substituting the bit values in the mask. At the same time, let’s take into account that in our mask “first (in the highest digits) there are ones, and then from a certain digit there are zeros.”

Starting from the 0th bit (from right to left), we will select the values of the network mask taking into account the bitwise conjunction:



Mask – ?
Network address

In the 4th bit it is obvious that a zero value is no longer suitable and there should be a 1 (one). Starting from this position and then moving to the left, we will have all the units:



Mask – ?
Network address

The desired value of the rightmost byte is 111100002, which corresponds to the value 24010 in decimal notation.

Answer: 240.

Task 13

When registering in computer system Each user is given a password consisting of 7 characters and containing only characters from the 26-character set of uppercase Latin letters. The database allocates the same and minimum possible integer number of bytes to store information about each user. In this case, character-by-character encoding of passwords is used; all characters are encoded with the same and minimum possible number of bits. In addition to the password itself, additional information is stored in the system for each user, for which an integer number of bytes are allocated; this number is the same for all users.

To store information about 30 users, 600 bytes were required. How many bytes are allocated for storage additional information about one user? In your answer, write down only an integer - the number of bytes.

Answer: ___________________________.

Solution

Each user's information is stored

600 ÷ 30 = 20 bytes.

Encoding 26 characters requires a minimum of 5 bits of memory. Therefore, a password of 7 characters is required

5 × 7 = 35 bits.

35 bits require a minimum of 5 bytes of memory.

The required number of bytes to store additional information about one user is:

20 bytes – 5 bytes = 15 bytes.

Answer: 15.

Task 14

Executor Editor receives a string of numbers as input and converts it. The editor can execute two commands, in both commands v and w represent strings of numbers.

A) replace (v, w).

This command replaces the first left occurrence of the string v with the string w. For example, running the command

replace (111, 27)

converts string 05111150 to string 0527150.

If there are no occurrences of v in a string, then executing the replace (v, w) command does not change that string.

B) found (v).

This command checks whether the string v occurs in the executor's line Editor. If it is encountered, the command returns the boolean value “true”, otherwise it returns the value “false”. The executor's line does not change.

BYE condition

sequence of commands

END BYE

is executed as long as the condition is true.

In design

IF condition

TO team1

END IF

command1 is executed (if the condition is true).

In design

IF condition

TO team1

ELSE command2

END IF

command1 is executed (if the condition is true) or command2 (if the condition is false).

What string will be obtained by applying the following program to a string consisting of 82 consecutive digits 1? Write down the resulting string in your response.

SO far found (11111) OR found (888)

IF found (11111)

TO replace (11111, 88)

IF found (888)

TO replace (888, 8)

END IF

END BYE

Answer: ___________________________.

Solution

Let’s “visualize” the situation:

82 units can be roughly represented as 16 groups of 5 units, as well as one group of two units. The first call to the conditional operator gives us 16 groups of pairs of eights - that's 32 eights, or 10 groups of three eights, plus another free pair of eights. Obviously, the last two units will remain untouched by the performer. And the 12 remaining eights, grouped by three, are already 4 eights. One more iteration - 2 eights and 2 ones remain.

Answer: 8811.

Task 15

The figure shows a diagram of roads connecting cities A, B, C, D, D, E, F, Z, I, K, L, M. On each road you can only move in one direction, indicated by the arrow.

How many different paths are there from city A to city M, passing through city L?

Answer: ___________________________.

Solution

Let's look at our diagram again. This time on the diagram we see marks arranged in a certain order.

To begin with, we note that the paths from point I to point M - a straight line and through point K - are highlighted in color. This was done because, according to the conditions of the problem, it is necessary to determine the number of paths only through point A.

Let's start from starting point A - this is a special point, no road leads there, formally you can only get there from there. Let us assume that the number of paths into it is 1.

The second point B is obvious that it can only be reached from one point and only one way. The third point cannot be either B or D - the number of paths to point B cannot be determined without determining the number of paths in G, and in D - without determining the number of paths in D. D is the third point on our path. The number of paths that lead to it is equal to 1. Let us continue this chain of inferences, determining the number of paths leading to a given point as the sum of the number of paths at previous points leading directly to the current one. Point I is a critical point - the number of paths leading to it is equal to the sum of 5 (E) + 16 (F) + 7 (G) and equal to 28. The next point is L, the road leads to it only through I, there is no other way, but therefore, the number of paths also remains equal to 28. And, finally, the finishing point - M - according to the conditions of the problem, only one road leads to it, which means the desired value will also remain equal to 28.

Answer: 28.

Task 16

The value of the arithmetic expression 9 7 + 3 21 – 9 is written in the number system with base 3. How many digits “2” are there in this notation?

Answer: ___________________________.

To solve the problem, let’s rewrite the original expression and also rearrange the terms:

3 21 + 3 14 – 3 2 .

Let us recall that in the ternary number system the number 3 10 itself is written 10 3. K-th power of 10 n essence 1 and K zeros. And it is also obvious that the first term 3 21 does not affect the number of twos in any way. But the difference can have an effect.

Answer: 12.

Task 17

In search engine query language to denote logical operation The symbol “|” is used for “OR”, and the symbol “&” is used to denote the logical operation “AND”.

The table shows the queries and the number of pages found for a certain segment of the Internet.

How many pages (in hundreds of thousands) will be found for the query? Throat | Ship | Nose? It is believed that all queries were executed almost simultaneously, so that the set of pages containing all the searched words did not change during the execution of the queries.

Answer: ___________________________.

Solution

Of course, the OR operation indicates the operation of adding the values of the found pages for each word separately: 35+35+40. But for some queries there were pages common to each pair of words - they need to be excluded, i.e. you need to subtract 33 from the previously found sum.

Answer: 77.

Task 18

For what is the largest non-negative integer number A the expression

(48 ≠ y + 2x) \/ (A< x) \/ (A < y)

is identically true, i.e. takes the value 1 for any non-negative integer x and y?

Answer: ___________________________.

Solution

The problem is purely mathematical...

The expression given in the task condition is the disjunction of three terms. The second and third terms depend on the desired parameter:

Let's represent the first term differently:

y = –2x+ 48

Points on a line (graph of a function) with integer coordinates are those values of the variables x and y at which it ceases to be true. Therefore, we need to find an A that would ensure the truth of or at these points.

Or, for different x and y, belonging to the straight line, they will alternately (sometimes simultaneously) take on the true value for any A in the range. in this regard, it is important to understand what parameter A should be for the case when y = x.

Those. we get the system:

The solution is easy to find: y=x=16. And the largest integer that suits us for parameter A=15.

Answer: 15.

Task 19

The program uses a one-dimensional integer array A with indices from 0 to 9. The values of the elements are 2, 4, 3, 6, 3, 7, 8, 2, 9, 1, respectively, i.e. A = 2, A = 4, etc. Determine the value of a variable c after executing the following fragment of this program, written below in five programming languages.

Answer: ___________________________.

Solution

A program fragment executes a repeat loop. The number of iterations is 9. Each time the condition is met, the variable With increases its value by 1, and also swaps the values of two array elements.

Initial sequence: 2, 4, 3, 6, 3, 7, 8, 2, 9, 1. In the record, you can construct the following iteration scheme:

Iteration step:	Condition check	After replacement	Variable With






	2<2 – НЕТ

	2<1 – НЕТ

Answer: 7.

Task 20

The algorithm is written below in five programming languages. Given a natural decimal number x as input, this algorithm prints two numbers: L and M. Specify the largest number x, when entered, the algorithm prints first 21 and then 3.

Answer: ___________________________.

Solution

A little code analysis:

We must display the values of the variables L and M. The variable M, this can be seen by studying the code a little, indicates the number of iterations of the loop, i.e. The body of the loop must be executed three times exactly.
The value of the number L, which should be printed first, is the product equal to 21. In the product, 21 can be obtained from 7 and 3. Note also that the product is possible only if the value of the variable is odd x in the current iteration.
The conditional operator indicates that one time out of three the value of the variable will be even. The remaining two times with an odd value of the variable x, we get the remainder of dividing x by 8 to be one time 3 and another time 7.
Variable value x is reduced three times by 8 by the integer division operation.

Combining everything said earlier, we get two options:

x 1 = (7 × 8 + ?) × 8 + 3 and x 2 = (3 × 8 + ?) × 8 + 7

Instead of a question mark, we need to choose a value that will be no more than 8 and will be even. Let’s not forget about the condition in the task – “the largest x”. The greater is even, not exceeding 8 – 6. And from x1 and x2, it is obvious that the first is greater. Having calculated, we get x=499.

Answer: 499.

Task 21

Determine the number that will be printed as a result of the following algorithm. For your convenience, the algorithm is presented in five programming languages.

Note. The abs and iabs functions return the absolute value of their input parameter.

Answer: ___________________________.

Solution

Let's write our function in the usual form:

To make the picture clearer, let’s also plot this function:

Taking a closer look at the code, we note the following obvious facts: until the loop is executed, the variable is M=-20 and R=26.

Now the cycle itself: twenty-one iterations, each depending on the fulfillment (or non-fulfillment) of a condition. There is no need to check all the values - the graph will help us a lot here. Moving from left to right, the values of the variables M and R will change until the first minimum point is reached: x=-8. Further and up to the point x=8, the condition check gives false values and the values of the variables do not change. At point x=8 the values will change for the last time. We get the desired result M=8, R=2, M+R=10.

Answer: 10.

Task 22

Executor Calculator converts the number written on the screen. The performer has three teams, which are assigned numbers:

Add 2
Multiply by 2
Add 3

The first of them increases the number on the screen by 2, the second multiplies it by 2, the third increases it by 3.

A Calculator program is a sequence of commands.

How many programs are there that convert the original number 2 into the number 22 and at the same time the program's computation path contains the number 11?

A program's computation trajectory is a sequence of results from the execution of all program commands. For example, for program 123 with the initial number 7, the trajectory will consist of the numbers 9, 18, 21.

Answer: ___________________________.

Solution

To begin with, let’s solve the problem simply, without taking into account the additional condition “contains the number 11”:

The program is short, and it also does not calculate the value 11 in its trajectory. And here it is worth breaking the problem into two small tasks: determining the number of paths from 2 to 11 and from 11 to 22. The final result, obviously, will correspond to the product of these two values. Constructing complex diagrams with trees is not a rational waste of time in the exam. There are not many numbers in our range, so I suggest considering the following algorithm:

Let's write down all the numbers from the starting number to the last one inclusive. Under the first one we will write 1. Moving from left to right, we will consider the number of ways to get to the current position using the commands given to us.

You can immediately remove obvious positions that do not affect the decision: 3 can be crossed out - it is clear that it cannot be reached from the starting position using one of the commands available to us; 10 – through it we cannot in any way get to our intermediate, and most importantly, mandatory position 11.

We can get to 4 using two command paths: x2 and +2, i.e. through 4 there are 2 paths. Let's write this value under 4. There is only one way to get to 5: +3. Let's write the value 1 under 5. The only way to get to 6 is through 4. And under it we have the value 2. Accordingly, it is along these two paths that by passing 4 we will get from 2 to 6. We write under 6 the value 2. In 7 you can get from the two previous positions using the commands we have, and to get the number of paths that are available to us to get to 7, we add the numbers that were indicated under these previous positions. Those. in 7 we get 2 (from under 4) + 1 (from under 5) = 3 ways. Proceeding according to this scheme, we further obtain:

Let's move to the right half of the conditional center - 11. Only now in the calculation we will take into account only those paths that pass through this center.

Answer: 100.

Task 23

How many different sets of values of the logical variables x1, x2, ... x7, y1, y2, ... y7 are there that satisfy all the conditions listed below?

(y1 → (y2 /\ x1)) /\ (x1 → x2) = 1

(y2 → (y3 /\ x2)) /\ (x2 → x3) = 1

(y6 → (y7 /\ x6)) /\ (x6 → x7) = 1

The answer does not need to list all the different sets of values of the variables x1, x2, ... x7, y1, y2, ... y7 for which this system of equalities is satisfied. As an answer, you need to indicate the number of such sets.

Answer: ___________________________.

Solution

A fairly detailed analysis of this category of problems was published at one time in the article “Systems of logical equations: solution using bit chains.”

And for further discussion, we recall (for clarity, we write down) some definitions and properties:

Let's now look at our system again. Please note that it can be rewritten a little differently. To do this, first of all, note that each of the selected factors in the first six equations, as well as their mutual product, are equal to 1.

Let's work a little on the first factors of the equations in the system:

Taking into account the above considerations, we obtain two more equations, and the original system of equations will take the form:

In this form, the original system is reduced to the standard tasks discussed in the previously mentioned article.

If we consider separately the first and second equations of the new system, then the sets correspond to them (let us leave a detailed analysis of this conclusion for the reader):

These arguments would lead us to possible 8 × 8 = 64 solutions if not for the third equation. In the third equation, we can immediately limit ourselves to considering only those variants of sets that are suitable for the first two equations. If we substitute the first set into the third equation y 1…y 7, consisting of only 1, then it is obvious that only one set will correspond to it x 1…x 7, which also consists of only 1s. Any other set that contains at least one 0 is not suitable for us. Consider the second set y1…y7 – 0111111. For x 1, both possible values are acceptable - 0 and 1. The remaining values, as in the previous case, cannot be equal to 0. We have two sets that meet this condition. The third set y1…y7 – 011111 will match the first three sets x 1…x 7. Etc. Arguing in a similar way, we find that the required number of sets is equal to

1 + 2 + … + 7 + 8 = 36.

Answer: 36.

Part 2

To record answers to tasks in this part (24–27), use ANSWER FORM No. 2. First write down the task number (24, 25, etc.), and then the complete solution. Write down your answers clearly and legibly.

Further, we don’t see the need to come up with something different from the official content of the KIM demo version. This document already contains “the content of the correct answer and instructions for assessment”, as well as “instructions for assessment” and some “notes for the assessor”. This material is given below.

Task 24

A natural number not exceeding 109 is received for processing. You need to write a program that displays the minimum even digit of this number. If there are no even digits in the number, you need to display “NO” on the screen. The programmer wrote the program incorrectly. Below this program is presented in five programming languages for your convenience.

Do the following in sequence.

1. Write what this program will output when you enter the number 231.

2. Give an example of a three-digit number, when entered, the above program, despite errors, produces the correct answer.

3. Find the mistakes made by the programmer and correct them. The error correction should only affect the line where the error is located. For each error:

write down the line in which the error was made;
indicate how to correct the error, i.e. give the correct version of the line.

It is known that exactly two lines in the program text can be corrected so that it starts working correctly.

It is enough to indicate the errors and how to correct them for one programming language.

Please note that you need to find errors in an existing program, and not write your own, possibly using a different solution algorithm.

The solution uses a Pascal program notation. It is possible to use the program in any of the four other programming languages.

1. The program will print the number 1.

2. The program gives the correct answer, for example, for the number 132.

Note for the reviewer. The program does not work correctly due to incorrect initialization and incorrect checking for missing even digits. Accordingly, the program will produce the correct answer if the entered number does not contain 0, contains at least one even digit, and the smallest even digit of the number is not greater than the lowest (rightmost) digit of the number (or is simply the last one).

3. There are two errors in the program.

First error: incorrect response initialization (minDigit variable).

Error line:

minDigit:= N mod 10;

Correct fix:

Any integer greater than 8 can be used instead of 10.

Second error: incorrect check for missing even digits.

Error line:

if minDigit = 0 then

Correct fix:

if minDigit = 10 then

Instead of 10, there may be another number greater than 8, which was put into minDigit when correcting the first error, or checking that minDigit > 8

Assessment Guidelines	Points
Pay attention! The task required four steps: 1) indicate what the program will output given a specific input number; 2) indicate an example of an input number at which the program produces the correct answer; 3) correct the first error; 4) fix the second error. To check the correct execution of step 2), you need to formally execute the original (erroneous) program with the input data specified by the examinee, and make sure that the result produced by the program will be the same as for the correct program. For steps 3) and 4), the error is considered corrected if both of the following conditions are met: a) the line with the error is specified correctly; b) a new version of the line is specified such that when correcting another error, the correct program is obtained
All four required steps have been completed and no valid rows have been reported as incorrect
The conditions for giving 3 points have not been met. One of the following situations occurs: a) three of the four necessary actions have been completed. No valid line is listed as error; b) all four necessary actions have been completed. No more than one correct line is indicated as erroneous
The conditions for giving 2 or 3 points have not been met. Two of the four required steps have been completed
The conditions for giving 1, 2 or 3 points have not been met

Task 25

Given an integer array of 30 elements. Array elements can take natural values from 1 to 10,000 inclusive. Describe an algorithm in one of the programming languages that finds the minimum among the elements of an array that are not divisible by 6, and then replaces each element that is not divisible by 6 with a number equal to the found minimum. It is guaranteed that there is at least one such element in the array. As a result, you need to display the changed array, each element is displayed on a new line.

For example, for an initial array of six elements:

the program should output the following array

The source data is declared as shown below in examples for some programming languages. It is prohibited to use variables not described below, but it is permitted not to use some of the described variables.

As an answer, you need to provide a fragment of the program, which should be located in the place of the ellipsis. You can also write the solution in another programming language (indicate the name and version of the programming language used, for example Free Pascal 2.6). In this case, you must use the same input data and variables that were proposed in the condition (for example, in a sample written in Algorithmic language).

In Pascal

In Python

In BASIC

In C++

In Algorithmic Language

Assessment Guidelines	Points
General instructions. 1. An algorithm written in a programming language may contain individual syntax errors that do not distort the intent of the program author. 2. The effectiveness of the algorithm is not important and is not evaluated. 3. It is allowed to write the algorithm in a programming language different from the languages given in the condition. In this case, variables similar to those described in the condition should be used. If a programming language uses typed variables, the variable declarations must be similar to the variable declarations in the Algorithmic language. The use of untyped or undeclared variables is possible only if the programming language allows it; in this case, the number of variables and their identifiers must correspond to the conditions of the problem. 4. An array output format other than the one specified is allowed, for example, in a line
A correct algorithm has been proposed that modifies the original array and outputs the modified array as a result.
The conditions for scoring 2 points have been met. At the same time, a generally correct solution is proposed, containing no more than one error from the following: 1) the loop goes beyond the array boundary; 2) the minimum is not initialized or is initialized incorrectly; 3) the test for divisibility by 6 is carried out incorrectly; 4) divisibility by 6 is checked not of the array element, but of its index; 5) in comparison with the minimum, the “more” and “less” signs are mixed up; 6) comparison with the minimum is performed for the index of the array element, and not for its value; 7) the logical condition is incorrectly composed (for example, or is used instead of and); 8) the original array does not change; 9) not all required elements are changed (for example, only the first or last of them); 10) there is no response output, or the response is not completely output (for example, only one element of the array due to a skipped cycle for outputting elements or operator brackets); 11) a variable is used that is not declared in the variable description section; 12) the cycle termination condition is not specified or is specified incorrectly;
There are two or more errors listed in paragraphs 1–13, or the algorithm is formulated incorrectly (including in the absence of an explicit or implicit search cycle for the required element)
Maximum score

Task 26

Two players, Petya and Vanya, play the following game. In front of the players are two piles of stones. The players take turns, Petya makes the first move. In one turn, the player can add one stone to one of the piles (of his choice) or increase the number of stones in the pile three times. For example, let there be 10 stones in one pile and 7 stones in another; We will denote such a position in the game by (10, 7). Then in one move you can get any of four positions:

(11, 7), (30, 7), (10, 8), (10, 21).

In order to make moves, each player has an unlimited number of stones.

The game ends when the total number of stones in the piles becomes at least 68. The winner is the player who made the last move, i.e. the first to obtain a position in which the piles contain 68 or more stones.

At the initial moment there were six stones in the first pile, S stones in the second pile; 1 ≤ S ≤ 61.

We will say that a player has a winning strategy if he can win with any moves of his opponent. To describe a player's strategy means to describe what move he should make in any situation that he may encounter with different plays from the opponent. The description of a winning strategy should not include moves of a player playing according to this strategy that are not unconditionally winning for him, i.e. not winning regardless of the opponent's play.

Complete the following tasks.

Task 1

c) Indicate all such values of the number S for which Petya can win in one move.

d) It is known that Vanya won with his first move after Petya’s unsuccessful first move. Specify the minimum value of S when this situation is possible.

Task 2

Specify the value of S at which Petya has a winning strategy, and two conditions are simultaneously satisfied:

Petya cannot win in one move;
Petya can win with his second move, regardless of how Vanya moves.

For the given value of S, describe Petit's winning strategy.

Task 3

Specify the value of S at which two conditions are simultaneously satisfied:

Vanya has a winning strategy that allows him to win with the first or second move in any of Petya’s games;
Vanya does not have a strategy that will allow him to be guaranteed to win on his first move.

For the given value of S, describe Vanya's winning strategy.

Construct a tree of all games possible with this winning strategy of Vanya (in the form of a picture or table).

In tree nodes, indicate positions; on edges, it is recommended to indicate moves. The tree should not contain games that are impossible if the winning player implements his winning strategy. For example, the complete game tree is not the correct answer to this task.

Task 1

a) Petya can win with 21 ≤ S ≤ 61.

Task 2

Possible value of S: 20. In this case, Petya obviously cannot win with his first move. However, he can get position (7, 20). After Vanya’s move, one of four positions can arise: (8, 20), (21, 20), (7, 21), (7, 60). In each of these positions, Petya can win in one move, tripling the number of stones in the second pile.

Note for the reviewer. Another possible value of S for this task is the number 13. In this case, Petya’s first move must triple the number of stones in the smaller pile and get the position (6 * 3, 13) = (18, 13). With this position, Vanya cannot win with his first move, and after any of Vanya’s moves, Petya can win by tripling the number of stones in the larger pile. It is enough to indicate one value of S and describe a winning strategy for it.

Task 3

Possible value of S: 19. After Petya’s first move, the following positions are possible:
(7, 19), (18, 19), (6, 20), (6, 57). In positions (18, 19) and (6, 57) Vanya can win with his first move by tripling the number of stones in the second pile. From positions (7, 19) and (6, 20) Vanya can get position (7, 20). This position is discussed in paragraph 2. The player who received it (now this is Vanya) wins with his second move.

The table shows a tree of possible games (and only them) for Vanya’s described strategy. The final positions (Vanya wins them) are highlighted in bold. In the figure, the same tree is depicted graphically (both ways of depicting a tree are acceptable).

Note to the expert. The tree of all parties can also be depicted as a directed graph - as shown in the figure, or in another way. It is important that the set of complete paths in the graph be in one-to-one correspondence with the set of games possible with the strategy described in the solution.

Rice. 1. Tree of all games possible under Vanya’s strategy. Petit's moves are shown with a dotted line; Vanya's moves are shown in solid lines. The rectangle indicates the positions at which the game ends.

Note for the reviewer. It is not a mistake to specify only one final move for a winning player in a situation where he has more than one winning move.

Assessment Guidelines	Points
The task requires you to complete three tasks. Their difficulty increases. The number of points generally corresponds to the number of tasks completed (see below for more details). An error in the solution that does not distort the main idea and does not lead to an incorrect answer, for example, an arithmetic error when calculating the number of stones in the final position, is not taken into account when evaluating the solution. Task 1 is completed if both points are completed: a) and b), i.e. for item a) all values of S that satisfy the condition are listed (and only them), for item b) the correct value of S is indicated (and only it). Task 2 is completed if the winning position for Petit is correctly indicated and the corresponding Petit strategy is described - as it was done in the example solution, or in another way, for example, using a tree of all possible games for the chosen Petit strategy (and only them). Task 3 is completed if the winning position for Vanya is correctly indicated, and a tree of all games possible under Vanya’s strategy (and only them) is constructed. In all cases, strategies can be described as in the example solution, or in another way
Completed tasks 1, 2 and 3
The conditions for scoring 3 points have not been met, and one of the following conditions has been met. 1. Task 3 completed. 2. Completed tasks 1 and 2
The conditions for giving 3 or 2 points have not been met, and one of the following conditions has been met. 1. Task 1 completed. 2. Task 2 completed
None of the conditions for giving 3, 2 or 1 point have been met

Task 27

The program input is a sequence of N positive integers, all numbers in the sequence are different. All pairs of different elements of the sequence located at a distance of at least 4 are considered (the difference in the indices of the elements of the pair must be 4 or more, the order of the elements in the pair is unimportant). It is necessary to determine the number of such pairs for which the product of elements is divisible by 29.

Description of input and output data

The first line of the input data specifies the number of numbers N (4 ≤ N ≤ 1000). Each of the next N lines contains one positive integer not exceeding 10,000.

As a result, the program should output one number: the number of pairs of elements located in the sequence at a distance of at least 4, in which the product of the elements is a multiple of 29.

Example input data:

Example output for the example input above:

Explanation. From 7 given elements, taking into account the permissible distances between them, you can create 6 products: 58 4, 58 1, 58 29, 2 1, 2 29, 3 29. Of these, 5 works are divided into 29.

It is required to write a time and memory efficient program to solve the described problem.

A program is considered time efficient if, with an increase in the number of initial numbers N by a factor of k, the running time of the program increases by no more than k times.

A program is considered memory efficient if the memory required to store all program variables does not exceed 1 kilobyte and does not increase with N.

The maximum score for a correct (not containing syntax errors and giving the correct answer for any valid input data) program that is time and memory efficient is 4 points.

The maximum score for a correct program that is effective only in time is 3 points.

The maximum score for a correct program that does not meet the efficiency requirements is 2 points.

You can take one program or two problem-solving programs (for example, one of the programs may be less effective). If you take two programs, each of them will be graded independently of the other, and the final grade will be the higher of the two grades.

Before writing the program text, be sure to briefly describe the solution algorithm. Please indicate the programming language used and its version.

The product of two numbers is divisible by 29 if at least one of the factors is divisible by 29.

When entering numbers, you can count the number of numbers that are multiples of 29, not counting the last four. Let's denote them n29.

Reviewer Note. The numbers themselves, except for the last four, do not need to be stored.

We will consider the next number read as a possible right element of the desired pair.

If the next read number is divisible by 29, then the number of numbers before it should be added to the answer, not counting the last four (including the read number).

If the next number read is not divisible by 29, then n29 should be added to the answer.

To build a memory-efficient program, note that since the processing of the next input data element uses values four elements earlier, it is sufficient to store only the last four elements or information about them.

Below is a program that implements the described algorithm in Pascal (the PascalABC version is used)

Example 1. Program in Pascal language. The program is time and memory efficient

const s = 4; (required distance between elements)

a: array of longint; (storing last s values)

a_:longint; (next value)

n29: longint; (number divisible by 29 elements, not counting the last s)

cnt: longint; (number of pairs sought)

(Input of first s numbers)

for i:=1 to s do readln(a[i]);

(Entering the remaining values, counting the required pairs)

for i:= s + 1 to n do

if a mod 29 = 0 then n29:= n29 + 1;

if a_ mod 29 = 0 then cnt:= cnt + i - s

cnt:= cnt + n29;

(shift the elements of the auxiliary array to the left)

for j:= 1 to s - 1 do a[j] := a;

a[s] := a_ (we write the current element to the end of the array)

The official website of FIPI presented for review demo versions of the 2020 Unified State Exam in all subjects, including computer science.

Preparation for the Unified State Exam in computer science includes several mandatory stages. First of all, you need to familiarize yourself with the demo versions. An open task bank will help you conduct comprehensive preparation for each task.

Structure of KIM Unified State Exam 2020 in computer science.

Each version of the examination paper consists of two parts and includes 27 tasks that differ in form and level of difficulty.

Part 1 contains 23 short answer tasks. The examination paper offers the following types of short-answer tasks:

– tasks to calculate a certain value;

– tasks to establish the correct sequence, presented as a string of characters according to a certain algorithm.

The answer to the tasks of Part 1 is given by the corresponding entry in the form of a natural number or a sequence of characters (letters or numbers), written without spaces or other delimiters.

Part 2 contains 4 tasks with detailed answers.

In part 1, 12 tasks are at the basic level, 10 tasks are at an increased level of complexity, 1 task is at a high level of complexity.

The tasks in Part 2 are aimed at testing the development of the most important skills in recording and analyzing algorithms. These skills are tested at advanced and high difficulty levels. Also, skills on the topic “Programming Technology” are tested at a high level of complexity.

Changes in KIM Unified State Exam 2020 in computer science compared to the 2019 CMM.

There are no changes to the 2020 Unified State Exam KIM in computer science and ICT.

The examination paper consists of two parts, including 27 tasks.

Part 1 contains 23 short answer tasks. Answers to tasks 1–23 are written as a number, a sequence of letters or numbers.
Part 2 contains 4 tasks with detailed answers. Tasks 24–27 require a detailed solution.

All Unified State Exam forms are filled out in bright black ink. You can use a gel or capillary pen. When completing assignments, you can use a draft. Entries in the draft, as well as in the text of control measurement materials, are not taken into account when evaluating the work.

3 hours 55 minutes (235 minutes) are allotted to complete the examination work in computer science and ICT.

The points you receive for completed tasks are summed up. Try to complete as many tasks as possible and score the most points.

Points for computer science assignments

1 point - for 1-23 tasks
2 points - 25.
3 points - 24, 26.
4 points - 27.

Total: 35 points.