Changes in demo versions of the Unified State Exam in computer science. Changes in demo versions of the exam in computer science in Algorithmic language

Secondary general education

Computer science

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

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 work of the teacher and, of course, the already built (I would like to count on this) plan for preparing the student 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.

Exercise 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 settlements in the table may 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 in the table those numbers of settlements opposite which there are three “stars” in the rows (or in the 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:

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 we used a codeword 0; 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 to encode 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.

1. A binary representation of the number N is constructed.
2. 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 larger. 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

A fragment of a spreadsheet is given. 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. What is the maximum number of colors that can be used in a 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, with each byte written as a 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 us write below each other the binary representation of the last right byte of the IP address, network address and mask in accordance with the definition (in top line For convenience in future reference, the bits are numbered):

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:

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:

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 (if the condition is true) or command2 (if the condition is false) is executed.

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 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 - it is obvious that it can be reached only 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 to G, and to G without determining the number of paths to 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 by 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 contained in this entry?

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 the search engine query language, the symbol "|" is used to denote the logical operation "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:

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:

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 greatest number x, when entered, the algorithm prints first 21 and then 3.

Answer: ___________________________.

Solution

A little code analysis:

1. 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.
2. 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.
3. 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.
4. 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 moment 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:

1. Add 2
2. Multiply by 2
3. 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 calculation 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 1. 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:

1. write down the line in which the error was made;
2. 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.

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, it is necessary 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).

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, a 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.

Exercise 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 a 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 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.

At the end of August, demo versions of the KIM Unified State Exam 2019 (including a demo version of the Unified State Exam in computer science) were published on the official website of FIPI.

For graduates, documents that regulate the structure and content of CMMs - the codifier and specification - are of great interest.

Unified State Exam in Computer Science 2019 - demo version with answers and criteria from FIPI

Changes in the 2019 CMM compared to the 2018 CMM.

The 2019 CMM model will not change compared to 2018. The number of tasks, their difficulty levels, tested content elements and skills, and maximum points for completing tasks will remain the same as in 2015–2018.

Structure of KIM Unified State Examination

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 tasks with a short answer: – 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 or numbers), written without spaces or other delimiters. 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 are at the basic level, 10 tasks are at an increased level of complexity, 1 task is at 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.

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.

Duration of the Unified State Examination in computer science and ICT

3 hours 55 minutes (235 minutes) are allotted to complete the examination work. It is recommended to spend 1.5 hours (90 minutes) to complete the tasks of Part 1. It is recommended to devote the rest of the time to completing the tasks of part 2.

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.

Analysis of 2 tasks. Demo version of the exam in computer science 2019 (FIPI):

Misha filled out the truth table of the function

but managed to fill out only a fragment of three different lines, without even indicating which column of the table each variable corresponds to w, x, y, z.

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

Analysis of 3 tasks. Demo version of the exam in computer science 2019 (FIPI):

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 on the diagram. In your answer, write down these two numbers in ascending order without spaces or punctuation.

Analysis of 4 tasks. Demo version of the exam in computer science 2019 (FIPI):

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 represented by the ID field value in the corresponding row of Table 1.
Based on the given data, determine the greatest difference between the years of birth of siblings. When calculating the answer, take into account only the information from the given fragments of the tables.

Analysis of task 5. Demo version of the exam in computer science 2019 (FIPI):

To encode some sequence consisting of letters A B C D E F,decided to use non-uniform binary code, satisfying the Fano condition. For a letter A used a code word 0 ; for a letter B- a codeword 10 .
What is the smallest possible sum of codeword lengths for 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.

Analysis of task 6. Demo version of the exam in computer science 2019 (FIPI):

The input of the algorithm is a natural number N. The algorithm constructs a new number from it R in the following way.

1) A binary representation of the number N is constructed.
2) Two more digits are added to this entry on the right according to the following rule:

If N even, at the end of the number (on the right) is added first zero, and then unit. Otherwise, if N odd, added to the right first unit, 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 contains two digits more than in the record of the original number N) is a binary representation of a number R– the result of this algorithm.

Specify minimum number R, which more than 102 and may be the result of this algorithm. In your answer, write this number in the decimal number system.

Analysis of task 7. Demo version of the exam in computer science 2019 (FIPI):

A fragment of a spreadsheet is given. From cell C3 to cell D4 the formula was copied. When copying, the cell addresses in the formula automatically changed.

What is the numeric value of the formula in the cell? D4?

Analysis of task 8. Demo version of the exam in computer science 2019 (FIPI):

Write down the number that will be printed as a result of the following program.

var s, n: integer; begin s:= 0; n:= 75; while s + n< 150 do begin s:= s + 15; n:= n - 5 end; writeln(n) end.

Analysis of task 9. Demo version of the exam in computer science 2019 (FIPI):

An automatic camera produces raster images of size 200×256 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 excluding the size of the file header.

Which maximum number of colors can it be used in a palette?

Analysis of task 10. Demo exam in computer science 2019 (FIPI):

Vasya makes up 5 letter words that contain only letters WINTER, and each word contains exactly one vowel and she's dating 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?

Analysis of task 11. Demo exam in computer science 2019 (FIPI):

The recursive algorithm F is written below.

Pascal:

procedure F(n: integer); begin if n > 0 then begin F(n - 1); write(n); F(n - 2) end end;

Write everything in a row without spaces or separators 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.

Analysis of task 12. Demo version of the exam in computer science 2019 (FIPI):

In the terminology of TCP/IP networks, a network mask is a binary number that 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 on this network. Typically, the mask is written according to the same rules as the IP address - in the form of four bytes, with each byte written as a 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 117.191.37.84 network address is 117.191.37.80 . What is equal to least possible value of the latter ( rightmost) byte mask? Write your answer as a decimal number.

Analysis of task 13. Demo exam in computer science 2019 (FIPI):

When registering in a computer system, each user is given a password consisting of 7 characters and containing only characters from 26 -character set of capital Latin letters. The database allocates the same and smallest possible integer to store information about each user byte. In this case, character-by-character encoding of passwords is used, all characters are encoded with the same and the minimum possible number bit. 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 required 600 bytes.

How many bytes are allocated for storage additional information about one user? In your answer, write down only an integer - the number of bytes.

Analysis of task 14. Demo version of the exam in computer science 2019 (FIPI):

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 in a string v on a chain w.

For example, running the replace(111, 27) command will convert the string 05111150 to string 0527150.

If there are no occurrences of the string in the string v, then executing the command replace (v, w) does not change this line.
B) found (v).
This command checks if the chain occurs v in the artist line Editor. If it is encountered, the command returns a boolean value "true", otherwise returns the value "lie". The executor's line does not change.

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

START WHILE found (11111) OR found (888) IF found (11111) THEN replace (11111, 88) ELSE IF found (888) THEN replace (888, 8) END IF END IF END BYE END

Analysis of task 15. Demo version of the exam in computer science 2019 (FIPI):

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

How many different ways are there from the city? A in town M passing through the city L?

Analysis of task 16. Demo version of the exam in computer science 2019 (FIPI):

Meaning of an arithmetic expression 9 7 + 3 21 – 9 written in a number system with a base 3 . How many digits "2" contained in this post?

Analysis of task 17. Demo version of the exam in computer science 2019 (FIPI):

In search engine query language to denote a logical operation "OR" symbol used «|» , and to denote a logical operation "AND"- symbol «&» .

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.

Analysis of task 18. Demo version of the exam in computer science 2019 (FIPI):

For what is the largest non-negative integer A expression

identically true, i.e. takes on the value 1 for any non-negative integers x And y?

Analysis of task 19. Demo version of the exam in computer science 2019 (FIPI):

The program uses a one-dimensional integer array A with indexes from 0 before 9 . The element values ​​are equal 2, 4, 3, 6, 3, 7, 8, 2, 9, 1 accordingly, i.e. A=2, A=4 etc.

Determine the value of a variable c after executing the next fragment of this program.

Analysis of task 20. Demo version of the exam in computer science 2019 (FIPI):

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

var x, L, M: integer; begin readln(x); L:= 1; M:= 0; while x > 0 do begin M:= M + 1; if x mod 2<>0 then L:= L * (x mod 8); x:= x div 8 end; writeln(L); writeln(M) end.

Analysis of 21 tasks. Demo version of the exam in computer science 2019 (FIPI):

Determine the number that will be printed as a result of the following algorithm.

Note. abs function returns the absolute value of its input parameter.

Pascal:

var a, b, t, M, R: longint; function F(x: longint) : longint; begin F:= abs(abs(x - 6) + abs(x + 6) - 16) + 2; end; begin a:= -20; b:= 20; M:=a; R:= F(a); for t:= a to b do begin if (F(t)<= R) then begin M:= t; R:= F(t) end end; write(M + R) end.

Analysis of 22 tasks. Demo version of the exam in computer science 2019 (FIPI):

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

1. Add 2
2. Multiply by 2
3. 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 in number 22 and at the same time the trajectory of the program calculations 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.

Analysis of 23 tasks. Demo version of the exam in computer science 2019 (FIPI):

How many different sets of Boolean variable values ​​are there? x1, x2, … x7, y1, y2, … y7, which satisfy all the conditions listed below?

(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1 (y2 → (y3 ∧ x2)) ∧ (x2 → x3) = 1 ... (y6 → (y7 ∧ x6)) ∧ (x6 → x7) = 1 y7 → x7 = 1

In response no need list all different sets of variable values 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.

Analysis of 24 tasks. Demo version of the exam in computer science 2019 (FIPI):

A natural number that does not exceed 109 . You need to write a program that displays minimum even number this number. If there are no even digits in the number, you need to display "NO". The programmer wrote the program incorrectly:

Pascal:

var N, digit, minDigit: longint; begin readln(N); minDigit:= N mod 10; while N > 0 do begin digit:= N mod 10; if digit mod 2 = 0 then if digit< minDigit then minDigit:= digit; N:= N div 10; end; if minDigit = 0 then writeln("NO") else writeln(minDigit) end.

Do the following in sequence:
1. Write what this program will output when you enter a 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:

1) write down the line in which the error was made;
2) 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.

Analysis of task 25. Demo version of the exam in computer science 2019 (FIPI):

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

For example, for an initial array of six elements:

14 6 11 18 9 24

the program should output the following array

9 6 9 18 9 24

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

Analysis of task 26. Demo version of the exam in computer science 2019 (FIPI):

Two players, Petya and Vanya, play the following game. In front of the players lie two piles of stones. The players take turns Petya makes the first move. In one turn, a player can add to one of the piles (of his choice) one stone or triple the number of stones in a pile.

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 at the moment 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:

Exercise 1
A) Specify all such number values S, at which Petya can win in one move.
b) It is known that Vanya won with his first move after Petit's unsuccessful first move. Specify the minimum value S when such a situation is possible.

Task 2
Specify this value S, in which Petya has a winning strategy, and two conditions are simultaneously met:
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 specified value 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.

Analysis of task 27. Demo version of the exam in computer science 2019 (FIPI):

The program input receives a sequence of N positive integers, all numbers in the sequence are different. All pairs of different elements of the sequence are considered,
located at a distance of no less than 4(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 the 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:

7 58 2 3 5 4 1 29

Example output for the example input above:

From 7 given elements, taking into account the permissible distances between them, you can create 6 products: 58 4 = 232:29 = 8 58 1 = 58:29 = 2 58 29 = 1682:29 = 58 2 1 = 2 2 29 = 58:29=2 3 29 = 87:29=3

Of these, 5 works are divided into 29.

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

-> demo version of the Unified State Exam 2019

Task 2. Demo version of the Unified State Exam 2018 computer science (FIPI):

Logic function F is given by the expression ¬x ∨ y ∨ (¬z ∧ w).
The figure shows a fragment of the truth table of the function F, containing all sets of arguments for which the function F is false. Determine which column of the truth table of the function F corresponds to each of the variables w, x, y, z.

AC 1	AC 2	AC 3	AC 4	Function
???	???	???	???	F
1	0	0	0	0
1	1	0	0	0
1	1	1	0	0

Write the letters in your answer w, x, y, z in the order in which the 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.

Task 3. Demo version of the Unified State Exam 2018 computer science (FIPI):
In the figure on the right, the road map of the N-rayon is shown in the form of a graph; the table contains information about the length of each of these roads (in kilometers).

Since the table and diagram were drawn independently of each other, the numbering of settlements in the table is in no way related to the letter designations on the graph. Determine the length of the road from the point A to point G. In your answer, write down the integer as it is indicated in the table.

4 task. Demo version of the Unified State Exam 2018 computer science (FIPI):
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 represented by the value of the ID field in the corresponding row of Table 1. Determine, based on the data provided, how many children had mothers over 22 years of age at the time of their birth. When calculating the answer, consider only the information from
the given fragments of tables.

Task 5. Demo version of the Unified State Exam 2018 computer science (FIPI):
Encrypted messages containing only ten letters are transmitted over the communication channel: A, B, E, I, K, L, R, S, T, U. An uneven binary code is used for transmission. Code words are used for nine letters.


Specify the shortest code word for the letter B, under which the code will satisfy the Fano condition. If there are several such codes, indicate the code with the smallest numerical value.

6 task. Demo version of the Unified State Exam 2018 computer science (FIPI):
The input of the algorithm is a natural number N. The algorithm constructs a new number from it R in the following way.

1. Constructing a binary notation for a number N.

2. Two more digits are added to this entry on the right according to the following rule:

- add up all the digits of the binary notation of a number N, and the remainder of dividing the sum by 2 is added to the end of the number (on the right). For example, record 11100 converted to record 111001 ;

- the same actions are performed on this entry - the remainder of dividing the sum of its digits by 2 is added to the right.

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 desired number R.
Specify the minimum number R, which exceeds the number 83 and may be the result of this algorithm. In your answer, write this number in the decimal number system.

Task 7. Demo version of the Unified State Exam 2018 computer science (FIPI):
A fragment of a spreadsheet is given. From cell B3 to cell A4 the formula was copied. When copying, the cell addresses in the formula automatically changed. What is the numeric value of the formula in the cell? A4?


Note: The $ sign denotes absolute addressing.

Task 8. Demo version of the Unified State Exam 2018 computer science (FIPI):

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.

1 2 3 4 5 6 7 8 9 10 11

var s, n: integer; begin s := 260 ; n:=0; while s > 0 do begin s : = s - 15 ; n : = n + 2 end ; writeln (n) end .

var s, n: integer; begin s:= 260; n:= 0; while s > 0 do begin s:= s - 15; n:= n + 2 end; writeln(n)end.

Task 9. Demo version of the Unified State Exam 2018 computer science (FIPI):

An automatic camera produces raster images of size 640 × 480 pixels. In this case, the size of the image file cannot exceed 320 KB, data is not packed. What is the maximum number of colors that can be used in a palette?

10 task. Demo version of the Unified State Exam 2018 computer science (FIPI):

All 4-letter words made from letters D, E, TO, ABOUT, R, written in alphabetical order and numbered starting with 1 .
Below is the start of the list.

1. DDDD 2. DDDE 3. DDDC 4. DDDO 5. DDDR 6. DDED...

What number in the list is the first word that begins with a letter? K?

11 task. Demo version of the Unified State Exam 2018 computer science (FIPI):

The recursive algorithm is written below in five programming languages F.
Pascal:

1 2 3 4 5 6 7 8 9

procedure F(n: integer) ; begin if n > 0 then begin write (n) ; F(n - 3); F(n div 3 ) end end ;

procedure F(n: integer); begin if n > 0 then begin write(n); F(n - 3); F(n div 3) end end;

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

Task 12. Demo version of the Unified State Exam 2018 computer science (FIPI):

In the terminology of TCP/IP networks, a network mask is a binary number that 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 on this network. Typically, the mask is written according to the same rules as the IP address - in the form of four bytes, with each byte written as a 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 57.179.208.27 network address is 57.179.192.0 . What's it like greatest possible quantity units in the ranks of the mask?

Task 13. Demo version of the Unified State Exam 2018 computer science (FIPI):

When registering in a computer system, each user is given a password consisting of 10 characters. Capital letters of the Latin alphabet are used as symbols, i.e. 26 various symbols. In the database, each password is stored in the same and smallest possible integer byte. In this case, character-by-character encoding of passwords is used, all characters are encoded with the same and minimum possible number of bits.

Determine the amount of memory (in bytes) required to store data about 50 users. In your answer, write down only an integer - the number of bytes.

14 task. Demo version of the Unified State Exam 2018 computer science (FIPI):

Performer The draftsman moves on the coordinate plane, leaving a trace in the form of a line. The draftsman can execute the command move to (a, b), Where a, b – integers. This command moves the Draftsman from a point with coordinates (x,y) to a point with coordinates (x + a, y + b).

The draftsman was given the following algorithm to execute (the number of repetitions and the displacement values ​​​​in the first of the repeated commands are unknown):

START move to (4, 6) REPEAT … ONCE move to (…, …) move to (4, -6) END REPEAT move to (-28, -22) END

As a result of executing this algorithm, the Draftsman returns to starting point. Which greatest could the number of repetitions be indicated in the construction “REPEAT... ONCE”?

Task 15. Demo version of the Unified State Exam 2018 computer science (FIPI):

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 ways are there from the city? A in town M passing through the city AND?

Task 16. Demo version of the Unified State Exam 2018 computer science (FIPI):

Arithmetic expression value: 49 10 + 7 30 – 49 – written in a number system with a base 7 . How many digits? 6 " contained in this entry?

Task 17. Demo Unified State Exam 2018 computer science (FIPI):

In search engine query language, to denote the logical operation " OR» the symbol « is used | ", and to denote the logical operation " AND" - symbol " & ».

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

Request	Pages found (hundreds of thousands)
Butterfly	22
Caterpillar	40
Tractor	24
Tractor | Butterfly | Caterpillar	66
Tractor & Track	12
Tractor & Butterfly	0

How many pages (in hundreds of thousands) will be found for the query? Butterfly & Caterpillar?
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.

Task 18. Demo version of the Unified State Exam 2018 computer science (FIPI):

For what is the largest integer A formula

identically true, that is, takes the value 1 for any non-negative integers x And y?

19 task. Demo version of the Unified State Exam 2018 computer science (FIPI):

The program uses a one-dimensional integer array A with indexes from 0 before 9 . The values ​​of the elements are 3, 0, 4, 6, 5, 1, 8, 2, 9, 7 respectively, i.e. A=3, A=0 etc.

Determine the value of a variable c after executing the following fragment of this program:

1 2 3 4 5 6 7 8 9

c := 0 ; for i : = 1 to 9 do if A[ i- 1 ] > A[ i] then begin c : = c + 1 ; t := A[i] ; A[ i] : = A[ i- 1 ] ; A[ i- 1 ] : = t; end ;

c:= 0; for i:= 1 to 9 do if A > A[i] then begin c:= c + 1; t:= A[i]; A[i] := A; A := t; end;

20 task. Demo version of the Unified State Exam 2018 computer science (FIPI):

The algorithm is written below in five programming languages. Having received a number as input x, this algorithm prints two numbers: L And M. Enter the smallest number x, when entered, the algorithm prints first 5 , and then 7 .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

var x, L, M: integer ; begin readln(x) ; L:=0; M:=0; while x>0 do begin M : = M + 1 ; if x mod 2<>0 then L : = L + 1 ; x : = x div 2 ; end ; writeln(L); writeln(M); end.

var x, L, M: integer; begin readln(x); L:= 0; M:= 0; while x>0 do begin M:= M + 1; if x mod 2<>0 then L:= L + 1; x:= x div 2; end; writeln(L); writeln(M); end.

21 tasks. Demo version of the Unified State Exam 2018 computer science (FIPI):

Write in your answer the number that will be printed as a result of executing the following algorithm.

Pascal:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

var a, b, t, M, R : longint ; function F(x: longint ) : longint ; begin F: = 2 * (x* x- 1 ) * (x* x- 1 ) + 27 ; end ; begin a: =- 20 ; b: = 20 ; M:=a; R: = F(a) ; for t: = a to b do begin if (F(t)<= R) then begin M: = t; R: = F(t) end end ; write (M+ R) end .

var a, b, t, M, R:longint; function F(x: longint): longint; begin F:= 2*(x*x-1)*(x*x-1)+27; end; begin a:=-20; b:=20; M:=a; R:=F(a); for t:= a to b do begin if (F(t)<= R) then begin M:=t; R:=F(t) end end; write(M+R) end.

Task 22. Demo Unified State Exam 2018 computer science (FIPI):

Executor M17 converts the number written on the screen.
The performer has three teams, which are assigned numbers:
1. Add 1
2. Add 2
3. Multiply by 3

The first of them increases the number on the screen by 1, the second increases it by 2, the third multiplies it by 3. The program for the M17 performer is a sequence of commands.

How many programs are there that convert the original number? 2 in number 12 and the trajectory of the program’s calculations contains the numbers 8 And 10 ? The trajectory must contain both specified numbers.

A program's computation trajectory is a sequence of results from the execution of all program commands. For example, for program 132 with the initial number 7, the trajectory will consist of the numbers 8, 24, 26.

Solution 23 of the Unified State Examination task in computer science, demo version 2018 FIPI:

How many different sets of Boolean variable values ​​are there? x1, x2, … x7, y1, y2, … y7, which satisfy all the conditions listed below?

(¬x1 ∨ y1) → (¬x2 ∧ y2) = 1
(¬x2 ∨ y2) → (¬x3 ∧ y3) = 1
…
(¬x6 ∨ y6) → (¬x7 ∧ y7) = 1

As an answer, you need to indicate the number of such sets.

Solution 24 of the Unified State Examination task in computer science, demo version 2018 FIPI:

A natural number that does not exceed 10 9 . You need to write a program that displays the maximum digit of a number that is a multiple of 5. If the number does not contain multiple digits 5 , you need to display "NO". The programmer wrote the program incorrectly. Below this program is presented in five programming languages ​​for your convenience.
Reminder: 0 is divisible by any natural number.
Pascal:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

var N, digit, maxDigit: longint ; begin readln (N) ; maxDigit: = N mod 10; while N > 0 do begin digit : = N mod 10 ; if digit mod 5 = 0 then if digit > maxDigit then maxDigit : = digit; N := N div 10 ; end ; if maxDigit = 0 then writeln ("NO" ) else writeln (maxDigit) end .

var N, digit, maxDigit: longint; begin readln(N); maxDigit:= N mod 10; while N > 0 do begin digit:= N mod 10; if digit mod 5 = 0 then if digit > maxDigit then maxDigit:= digit; N:= N div 10; end; if maxDigit = 0 then writeln("NO") else writeln(maxDigit) end.

Do the following in sequence:
1. Write what this program will output when you enter a number 132 .
2. Give an example of a three-digit number that, when entered,
the program gives the correct answer.
3. Find all the errors in this program (there may be one or more). It is known that each error affects only one line and can be corrected without changing other lines. For each error:
1) write down the line in which the error was made;
2) indicate how to correct the error, i.e. give the correct version of the line.
It is enough to indicate the errors and how to correct them for one programming language.

Solution 25 of the Unified State Examination task in computer science Demo version 2018:

Given an integer array of 30 elements. Array elements can take integer values ​​from 0 before 10000 inclusive. Describe in one of the programming languages ​​an algorithm that finds the number of array elements large 100 and wherein multiples of 5, and then replaces each such element with a number equal to the quantity found. It is guaranteed that there is at least one such element in the array. As a result, it is necessary to output the changed array, each element of the array is output on a new line.

For example, for an array of six elements: 4 115 7 195 25 106
The program should print the numbers: 4 2 7 2 25 106

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.

Pascal:

1 2 3 4 5 6 7 8 9 10

const N = 30 ; var a: array [ 1 .. N ] of longint ; i, j, k: longint ; begin for i : = 1 to N do readln (a[ i] ) ; ... end .

const N = 30; var a: array of longint; i, j, k: longint; begin for i:= 1 to N do readln(a[i]); ... end.

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.

Analysis of task 26 of the demo version 2018 (FIPI):
Two players, Petya and Vanya, play the following game. There is a pile of stones in front of the players. The players take turns, Petya makes the first move. In one turn, a player can add to the pile one stone or increase the number of stones in the pile twice. For example, having a pile of 15 stones, in one move you can get a pile of 16 or 30 stones. Each player has an unlimited number of stones to make moves.

The game ends when the number of stones in the pile becomes at least 29. The winner is the player who made the last move, that is, the first to receive a pile containing 29 or more stones. At the initial moment there were S stones in the pile, 1 ≤ S ≤ 28.

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. Description of a winning strategy do not do it 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.

Exercise 1
A) Indicate such values ​​of the number S for which Petya can win in one move.
b) Indicate a value of S such that Petya cannot win in one move, but for any move Petya makes, Vanya can win with his first move. Describe Vanya's winning strategy.

Task 2
Specify two such values ​​of S for which Petya has a winning strategy, and:
— Petya cannot win in one move;
- Petya can win with his second move, regardless of how Vanya moves.
For the given values ​​of S, describe Petit's winning strategy.

Task 3
Specify the value of S at which:
— 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 (in the form of a picture or table). On the edges of the tree indicate who is making the move; in nodes - the number of stones in a position

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.

Analysis of task 27 of the demo version 2018 (FIPI):

The program input receives a sequence of N positive integers, all numbers in the sequence are different. All pairs of different elements of the sequence are considered (the elements of the pair do not have to be side by side in the sequence; the order of the elements in the pair is not important). Need to determine number of pairs for which the product of elements is divisible by 26 .

Description of input and output data The first line of input data specifies the number of numbers N (1 ≤ N ≤ 1000). In each of the subsequent N lines contains one positive integer not exceeding 10 000 .
As a result, the program should print one number: the number of pairs in which the product of the elements is a multiple of 26.

Example input data:

4 2 6 13 39

Example output for the example input above:

From four given numbers you can create 6 pairwise products: 2 6 = 12 2 13 = 26 2 39 = 78 6 13 = 78 6 39 = 234 13 39 = 507

Of these, 4 works are divided into 26:

2·13=26; 2·39=78; 6·13=78; 6·39=234

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

-> demo version of the Unified State Exam 2018