Informatics exam online tests. B2: logic functions. Appointment of KIM USE

Unified State Examination Decision Informatics

1. Task. How many ones are there in binary notation for the hexadecimal number 12F0 16 ?

Explanation.

Let's translate the number 12F0 16 to binary number system: 12F0 16 = 1001011110000 2 .

Let's count the number of units: there are 6 of them.

Answer: 6.

2. Task Boolean function F is given by the expression (¬ z ) ∧ x ∨ x ∧ y . Determine which column of the truth table of the function F corresponds to each of the variables x, y, z.

Variable one	Variable 2	Variable 3	Function

Write the letters in your answer. x, y, z in the order in which their corresponding columns appear (first, the letter corresponding to the 1st column; then, the letter corresponding to the 2nd column; then, the letter corresponding to the 3rd column). Write the letters in the answer in a row, you do not need to put any separators between the letters. Example. Let the expression x → y , depending on two variables x and y , and the truth table:

Variable one	Variable 2	Function

Then the 1st column corresponds to the variable y , and the 2nd column corresponds to the variable x . In your answer, write: yx.

Explanation.

This expression is a disjunction of two conjunctions. We can notice that in both terms there is a factor x . That is, for x = 0 the sum will be equal to 0. So, for the variable x only the third column fits.

In the eighth row of the table x = 1, and the value of the function is 0. This is possible only when z = 1, y = 0, i.e. variable1 − z , and variable2 − y .

Answer: zyx

3. Task In the figure on the right, the road map of the N-sky district is shown as a graph; the table contains information about the lengths of these roads (in kilometers).

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

Explanation.

Point B is the only point with five roads, so it corresponds to P6, and point E is the only one with four roads, so it corresponds to P4.

The length of the road from P6 to P4 is 20.

Answer: 20.

4. Task The database fragment provides information about relationships. Based on the given data, determine how many direct descendants (i.e. children and grandchildren) Pavlenko A.K. are mentioned in table 1.

Table 1
	Surname_I.O.	Floor
2146	Krivich L.P.
2155	Pavlenko A.K.
2431	Khitruk P. A.
2480	Krivich A. A.
2302	Pavlenko E. A.
2500	Sokol N. A.
3002	Pavlenko I. A.
2523	Pavlenko T. Kh.
2529	Khitruk A.P.
2570	Pavlenko P.I.
2586	Pavlenko T. I.
2933	Simonyan A. A.
2511	Sokol V. A.
3193	Biba S. A.

table 2
Parent_ID	Child_ID
2146	2302
2146	3002
2155	2302
2155	3002
2302	2431
2302	2511
2302	3193
3002	2586
3002	2570
2523	2586
2523	2570
2529	2431
2529	2511
2529	3193

For batch operations with files, file name masks are used. The mask is a sequence of letters, numbers, and other characters allowed in file names, which may also contain the following characters:

Symbol "?" (question mark) means exactly one arbitrary character.

The symbol "*" (asterisk) means any sequence of characters of arbitrary length, including "*" can also specify an empty sequence.

The directory contains 6 files:

maverick.map

maverick.mp3

taverna.mp4

revolver.mp4

vera.mp3

zveri.mp3

Below are eight masks. How many of them match exactly four files from the given directory?

ver.mp*	?ver?.mp?	?ver.mp?*	vr?.m?p
??????.mp	??????.m	a.a	a.p

Explanation.

From table 2 we see that Pavlenko A.K. (ID 2155) has two children, their IDs are 2302 and 3002.

Pavlenko E. A. (ID 2302) has three children, and Pavlenko I. A. (ID 3002) has two.

Thus, Pavlenko A.K. has seven direct descendants: two children and five grandchildren.

Answer: 7.

Consider each mask:

1. By mask *ver*.mp* five files will be selected:

maverick.mp3

taverna.mp4

revolver.mp4

vera.mp3

zveri.mp3

2. By mask *?ver?*.mp? three files will be selected:

maverick.mp3

taverna.mp4

zveri.mp3

3. By mask?*ver*.mp?* four files will be selected:

maverick.mp3

taverna.mp4

revolver.mp4

zveri.mp3

4. By mask *v*r*?.m?p* one file will be selected:

maverick.map

5. By mask???*???.mp* three files will be selected:

maverick.mp3

taverna.mp4

revolver.mp4

6. The mask ???*???.m* will select four files:

maverick.map

maverick.mp3

taverna.mp4

revolver.mp4

7. By mask *a*.*a* one file will be selected:

maverick.map

8. By mask *a*.*p* four files will be selected:

maverick.map

maverick.mp3

taverna.mp4

vera.mp3

That is, three masks that correspond to exactly four files from the given directory.

Answer: 3.

Answer: 7|3

5. Task Messages containing only four letters are transmitted over the communication channel: P, O, S, T; for transmission, a binary code is used that allows unambiguous decoding. For the letters T, O, P, the following code words are used: T: 111, O: 0, P: 100.

Specify the shortest code word for the letter C, at which the code will allow unambiguous decoding. If there are several such codes, indicate the code with the smallest numerical value.

Explanation.

The letter C cannot be encoded as 0 because 0 is already taken.

The letter C cannot be encoded as 1, since the encoding of the letter T begins with 1.

The letter C cannot be encoded as 10, since the encoding of the letter P begins with 10.

The letter C cannot be encoded as 11, since the encoding of the letter T begins with 11.

The letter C can be encoded as 101, which is the smallest possible value.

Answer: 101.

6. Quest The input of the algorithm is a natural number N. The algorithm builds 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:

A) all the digits of the binary notation are added, and the remainder of dividing the sum by 2 is added to the end of the number (on the right). For example, entry 11100 is converted to entry 111001;

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

The record obtained in this way (it contains two digits more than in the record of the original number N) is a binary record of the desired number R.

Specify the smallest number N for which the result of the algorithm is greater than 125. In your answer, write this number in decimal notation.

The performer Calculator has two teams that are assigned numbers:

1. add 2,

2. multiply by 5.

When performing the first of them, the Calculator adds 2 to the number on the screen, and when performing the second, it multiplies it by 5.

For example, program 2121 is program

multiply by 5

add 2,

multiply by 5

add 2,

which converts the number 1 to the number 37.

Write the order of commands in a program that converts the number 2 to the number 24 and contains no more than four commands. Specify only command numbers.

Explanation.

This algorithm assigns at the end of the number either 10 if it originally had an odd number of ones in its binary notation, or 00 if it was even.

126 10 = 1111110 2 can be obtained as a result of the algorithm from the number 11111 2 .

11111 2 = 31 10 .

Answer: 31.

Let's solve the problem from the reverse, and then write down the received commands from right to left.

If the number is not divisible by 5, then received through command 1, if it is divisible, then through command 2.

22 + 2 = 24(team 1)

20 + 2 = 22(team 1)

4 * 5 = 20(team 2)

2 + 2 = 4(team 1)

Answer: 1211.

Answer: 31|1211

7. Task. A fragment of a spreadsheet is given. A formula was copied from cell E4 to cell D3. When copying the addresses of the cells in the formula, they automatically changed. What is the numerical value of the formula in cell D3?





					=$B2 * C$3

Note: The $ sign denotes absolute addressing.

A fragment of a spreadsheet is given.



=(A1-3)/(B1-1)	=(A1-3)/(C1-5)	C1/(A1 – 3)

What integer must be written in cell A1 so that the chart built on the values of cells in the range A2:C2 matches the figure? It is known that all cell values from the considered range are non-negative.

Explanation.

The formula, when copied to cell D3, changed to =$B1 * B$3.

B1 * B3 = 4 * 2 = 8.

Answer: 8.

Substitute the values of B1 and C1 into formulas A2:C2:

A2 = (A1-3)/5

B2 = (A1-3)/5

C2 = 10/(A1-3)

Since A2 = B2, then С2 = 2 * A2 = 2 * B2

Substitute:

10/(A1-3) = 2*(A1-3)/5

A1 - 3 = 5

A1 = 8.

Answer: 8.

8. Task 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.

BASIC	Python
DIM S, N AS INTEGER S=0 N=0 WHILE S S=S+8 N=N+2 WEND PRINT N	s = 0 n=0 while s s = s + 8 n = n + 2 print(n)
Algorithmic language	Pascal
alg early integer n, s n:=0 s:= 0 nc bye s s:= s + 8 n:= n + 2 kts output n con	var s, n: integer; begin s:= 0; n:=0; while s begin s:= s + 8; n:= n + 2 end; writeln(n) end.
Xi
#include int main() ( int s = 0, n = 0; while (s printf("%d\n", n); return 0;

Explanation.

The while loop is executed as long as the condition s is true

Answer: 28.

9. Task. What is the minimum amount of memory (in KB) that must be reserved to be able to store any 64×64 pixel bitmap, assuming that 256 different colors can be used in the image? In the answer, write down only an integer, you do not need to write a unit of measurement.

The musical fragment was recorded in mono format, digitized and saved as a file without using data compression. The size of the resulting file is 24 MB. Then the same piece of music was re-recorded in stereo (two-channel recording) and digitized with a resolution 4 times higher and a sampling rate 1.5 times lower than the first time. Data compression was not performed. Specify the size of the file in MB resulting from the rewrite. In the answer, write down only an integer, you do not need to write a unit of measurement.

Explanation.

One pixel is encoded with 8 bits of memory.

Total 64 * 64 = 2 12 pixels.

The amount of memory occupied by the image 2 12 * 8 = 2 15 bits = 2 12 bytes = 4 KB.

Answer: 4.

When recording the same file in stereo format, its volume is increased by 2 times. 24 * 2 = 48

When its resolution is increased by 4 times, its volume also increases by 4 times. 48 * 4 = 192

When the sampling rate is reduced by 1.5 times, its volume is reduced by 1.5 times. 192 / 1.5 = 128.

Answer: 128.

Answer: 4|128

10. Task Igor makes a table of code words for message transmission, each message has its own code word. Igor uses 5-letter words as code words, in which there are only letters P, I, R, and the letter P appears exactly 1 time. Each of the other valid letters may occur any number of times in the codeword, or not at all. How many different code words can Igor use?

Explanation.

Igor can make up 2 4 words by putting the letter P in the first place. Similarly, you can put it in second, third, fourth and fifth place. We get 5 * 2 4 = 80 words.

Answer: 80.

11. Task Below, two recursive functions (procedures) are written in five programming languages: F and G.

BASIC	Python
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) IF n > 0 THEN G(n - 1) END SUB SUB G(n) PRINT "*" IF n > 1 THEN F(n - 3) END SUB	def F(n): If n > 0: G(n - 1) def G(n): Print("*") If n > 1: F(n - 3)
Algorithmic language	Pascal
alg F(integer n) early If n > 0 then G(n - 1) All con alg G(integer n) early Conclusion "*" If n > 1 then F(n - 3) All con	procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin If n > 0 then G(n - 1); end; procedure G(n: integer); begin writeln("*"); If n > 1 then F(n - 3); end;
Xi
void F(int n); void G(int n); void F(int n)( If (n > 0) G(n - 1); void G(int n)( printf("*"); If (n > 1) F(n - 3);

How many asterisks will be printed on the screen when calling F(11)?

Explanation.

Let's simulate the work of the program:

F(11)

G(10): *

F(7)

G(6): *

F(3)

G(2): *

F(-1)

Answer: 3.

12. Quest In TCP/IP networking terminology, a netmask is a binary number that determines which part of a host's IP address refers to the network address and which part refers to the address of the host itself on that network. Usually, 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. At the same time, in the mask, first (in the highest digits) there are ones, and then from a certain digit - 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 host with an IP address of 111.81.208.27, the network address is 111.81.192.0. What is the smallest possible value of the third byte from the left of the mask? Write your answer as a decimal number.

Explanation.

Let's write the third byte of the IP address and network address in binary notation:

208 10 = 11010000 2

192 10 = 11000000 2

We see that the first two bits of the mask on the left are ones, which means that in order for the value to be the smallest, the remaining bits must be zero. We get that the third byte of the mask from the left is 11000000 2 = 192 10

Answer: 192.

13. Task When registering in a computer system, each user is given a password consisting of 15 characters and containing only characters from the 12-character set: A, B, C, D, E, F, G, H, K, L, M, N. In the database data for storing information about each user is allocated the same and the minimum possible integer number of bytes. In this case, character-by-character coding of passwords is used, all characters are encoded with the same and the 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 is allocated; this number is the same for all users. It took 400 bytes to store information about 20 users. How many bytes are allocated to store additional information about one user? In the answer, write down only an integer - the number of bytes.

Explanation.

According to the condition, 12 letters can be used in the number. It is known that with the help of N bits it is possible to encode 2N different variants. Since 2 3 4 , then 4 bits are required to write each of the 12 characters.

To store all 15 characters of the password, you need 4 15 = 60 bits, and since an integer number of bytes is used for writing, we take the nearest no less value, a multiple of eight, this number is 64 = 8 8 bits (8 bytes).

Let the amount of memory allocated for additional sessions be x , then:

20 * (8+x) = 400

x=12

Answer: 12.

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

A) replace (v, w).

This command replaces the first occurrence of v on the left in a string with w. For example, executing the command

replace (111, 27)

converts the string 05111150 to the string 0527150. If the string contains no occurrences of the string v, then executing the replace (v, w) command does not change the string.

B) found (v).

This command checks if the string v occurs in the line of the executor Editor. If it occurs, then the command returns the logical value "true", otherwise it returns the value "false". Line

the performer is not changed.

Cycle

BYE condition

Command sequence

END BYE

Executes while the condition is true.

In design

IF condition

TO team1

ELSE team2

END IF

Command1 (if condition is true) or command2 (if condition is false) is executed.

What string will result from applying the following

program to a string consisting of 68 consecutive digits 8? In response

write down the resulting string.

START

YET Found (222) OR Found (888)

IF found (222)

TO replace (222, 8)

ELSE replace (888, 2)

END IF

END BYE

THE END

Explanation.

In 68 consecutive numbers 8 there are 22 groups of three eights, which will be replaced by 22 twos and two eights will remain.

68(8) = 22(2) + 2(8)

22(2) + 2(8) = 1(2) + 9(8)

1(2) + 9(8) = 4(2)

4(2) = 1(2) + 1(8) = 28

Answer: 28.

15. Quest The figure shows a diagram of roads connecting cities A, B, C, D, D, E, G, H, 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 city A to city M?

Explanation.

Let's start counting the number of paths from the end of the route - from the city M. Let N X is the number of different paths from city A to city X, N is the total number of paths. City M can be reached from L or K, so N = N M \u003d N L + N K. (*)

Similarly:

N K \u003d N And;

N L \u003d N And;

N I \u003d N E + N F + N Z

N K \u003d N E \u003d 1.

Let's add more vertices:

N B \u003d N A \u003d 1;

N B \u003d N B + N A + N G \u003d 1 + 1 + 1 \u003d 3;

N E \u003d N G \u003d 1;

N G \u003d N A \u003d 1.

Substitute in the formula (*): N = N M = 4 + 4 + 4 + 1 = 13.

Answer: 13.

Answer: 56

16. Quest Arithmetic expression value: 9 8 + 3 5 - 9 - recorded in number systems with base 3. How many digits "2" are contained in this entry?

Explanation.

Let's transform the expression:

(3 2 ) 8 + 3 5 - 3 2

3 16 + 3 5 - 3 2

3 16 + 3 5 = 100...00100000

100...00100000 - 3 2 = 100...00022200

There are three 2s in the resulting number.

Answer: 3

17. Task In the search engine query language, the symbol "|" is used to indicate the logical operation "OR", and the symbol "&" is used to indicate the logical operation "AND". The table shows queries and the number of pages found by them for a certain segment of the Internet.

How many pages (in thousands) will be found for the queryHomer & Odyssey & Iliad?It is believed that all requests were executed almost simultaneously, so that the set of pages containing all the searched words did not change over time.

execution of requests.

Explanation.

The number of requests in this area will be denoted by Ni. Our target is N5.

Then from the table we find that:

N5 + N6 = 355,

N4 + N5 = 200,

N4 + N5 + N6 = 470.

From the first and second equations: N4 + 2N5 + N6 = 555.

From the last equation: N5 = 85.

Answer: 85

18. Task Denote by m&n bitwise conjunction of non-negative integers m and n . So, for example, 14&5 = 1110 2 &0101 2 = 0100 2 = 4.

What is the smallest non-negative integer And the formula

x&25 ≠ 0 → (x&17 = 0 → x&A ≠ 0)

is identically true (i.e. takes the value 1 for any non-negative integer value of the variable X )?

Explanation.

Let us introduce the notation:

(x ∈ A) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.

Transforming, we get:

¬P ∨ ¬(Q ∧ ¬A) ∨ ¬P = ¬P ∨ ¬Q ∨ A.

The logical OR is true if at least one of the statements is true. Condition ¬P∨ ¬Q = 1 satisfy the rays (−∞, 40) and (60, ∞). Since the expression ¬P∨ ¬Q ∨ A must be identically true, the expression A must be true on the interval . Its length is 20.

Answer: 20.

Answer: 8

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

Determine the value of a variable c after executing the following fragment of this program(written below in five programming languages).

BASIC	Python
C=0 FOR i = 1 TO 9 IF A(i) C=c+1 T = A(i) A(i) = A(0) A(0) = t ENDIF NEXT i	C=0 For i in range(1,10): If A[i] C=c+1 t = A[i] A[i] = A A=t
Algorithmic language	Pascal
c:= 0 nc for i from 1 to 9 if A[i] c:= c + 1 t:= A[i] A[i] := A A := t all kts	c:=0; for i:= 1 to 9 do if A[i] begin c:= c + 1; t:= A[i]; A[i] := A; A := t; end;
Xi
c = 0; for (i = 1;i if (A[i] { c++; t = A[i]; A[i] = A; A=t; }

Explanation.

If A[i] is an array element less than A, then the program swaps them and increases the value of the variablecby 1. The program will be executed twice, the first time swapping A and A, since 3 withbecomes equal to 2.

Answer: 2.

20. QuestThe algorithm is written in five programming languages below. Having received a numberx, this algorithm prints a numberM. It is known thatx> 100. Indicate the smallest such (i.e. greater than 100) numberx, upon entering which the algorithm prints 26.

BASIC	Python
DIM X, L, M AS INTEGER INPUT X L=X M=65 IF L MOD 2 = 0 THEN M=52 ENDIF WHILE L M IF L > M THEN L=L-M ELSE M=M-L ENDIF WEND PRINT M	x = int(input()) L=x M=65 if L % 2 == 0: M=52 while L != M: if L > M: L=L-M else: M=M-L print(M)
Algorithmic language	Pascal
alg early integer x, L, M input x L:= x M:= 65 if mod(L,2)=0 then M:= 52 all nc while L M if L > M then L:= L - M otherwise M:= M - L all kts terminal M con	var x, L, M: integer; begin readln(x); L:=x; M:= 65; if L mod 2 = 0 then M:= 52; while L M do if L > M then L:= L - M else M:= M - L; writeln(M); end.
Xi
#include void main() { intx, L, M; scanf("%d", &x); L=x; M=65; if (L % 2 == 0) M=52; while (L != M)( if(L > M) L = L - M; else M = M - L; } printf("%d", M); }

Explanation.

In the body of the loop, the numbers M and L decrease until they become equal. In order to print 26 in the end, both numbers must be equal to 26 at some point. Let's go from the end to the beginning: in the previous step, one number was 26, and the other 26 + 26 = 52. One step earlier, 52 + 26 = 78 and 52. Until then, 78 + 52 = 130 and 52. That is, the smallest possible number is 130. And since the found number is even, M will be assigned the value 52, which will lead to the desired result.

Answer: 130.

21. QuestWrite in your answer the smallest value of the input variablek, at which the program produces the same answer as with the input valuek= 10. For your convenience, the program is presented in five programming languages.

BASIC	Python
DIM K, I AS LONG INPUT K I = 1 WHILE F(I) I = I + 1 WEND PRINT I FUNCTION F(N) F=NNN END FUNCTION FUNCTION G(N) G = 2*N + 3 END FUNCTION	def f(n): return nnn def g(n): return 2*n+3 k = int(input()) i = 1 while f(i) i+=1 print(i)
Algorithmic language	Pascal
alg early integer i, k input k i:= 1 nc while f(i) i:= i + 1 kts output i con alg integer f(int n) early val:= n * n * n con alg integer g(int n) early value:= 2*n + 3 con	var k, i: longint; function f(n: longint): longint; begin f:= n * n * n; end; function g(n: longint): longint; begin g:= 2*n + 3; end; begin readln(k); i:= 1; while f(i) i:=i+1; writeln(i) end.
Xi
#include long f(long n) ( return nnn; } long g(long n) ( return 2*n + 3; } int main() { long k, i; scanf("%ld", &k); i = 1; while(f(i) i++; printf("%ld", i); return 0; }

Explanation.

This program compares and and adds toiunit until . And prints the first value of the variableiunder which

With k = 10, the program will print the number 3.

Let's write down the inequality: hence we get that the smallest valuek = 3.

Answer: 3.

22. QuestMay15 performer converts the number on the screen. The performer has two teams that are assigned numbers:

1. Add 1

2. Multiply by 2

The first command increases the number on the screen by 1, the second one multiplies it by 2. The program for the May15 performer is a sequence of commands. How many programs are there for which, with the initial number 2, the result is the number 29 and the calculation trajectory contains the number 14 and does not contain the number 25?

The trajectory of a program is the sequence of results

execution of all program commands. For example, for program 121, with the initial number 7, the trajectory will consist of the numbers 8, 16, 17.

Explanation.

For addition, the commutative (commutative) law is valid, which means that the order of the instructions in the program does not matter for the result.

All commands increase the initial number, so the number of commands cannot exceed (30 − 21) = 9. In this case, the minimum number of commands is 3.

Thus, there can be 3, 4, 5, 6, 7, 8, or 9 commands. Therefore, the order of the commands does not matter, each number of commands corresponds to one set of commands, which can be arranged in any order.

Let's consider all possible sets and calculate the number of options for placing commands in them. Set 133 has 3 possible locations. Set 1223 - 12 possible arrangements: this is the number of permutations with repetitions (1+2+1)!/(1! · 2! · 1!). Set 12222 - 5 options. Set 111222 - 20 possible options. Set 11123 - 20 options. Set 111113 - 6 options, set 1111122 - 21 options, set 11111112 - 8 options, set 111111111 - one option.

In total we have 3 + 12 + 5 + 20 + 20 + 6 + 21 + 8 + 1 = 96 programs.

Answer: 96.

Answer: 13

23. QuestHow many different sets of boolean values are therex1 , x2 , ...x9 ,y1 ,y2 , ... y9 that satisfy all of the following conditions?

(¬ (x1 ≡ y1 )) ≡ (x2 ≡ y2 )

(¬ (x2 ≡ y2 )) ≡ (x3 ≡ y3 )

…

(¬ (x8 ≡ y8 )) ≡ (x9 ≡ y9 )

The answer does not need to list all the different sets of variable valuesx1 , x2 , ...x9 ,y1 ,y2 , ... y9 , under which this system of equalities holds. As an answer, you need to indicate the number of such sets.

Explanation.

From the last equation, we find that there are three possible values of x8 and y8: 01, 00, 11. Let's build a tree of options for the first and second pairs of values.

Thus, we have 16 sets of variables.

Option tree for value pair 11:

We get 45 options. Thus, the system will have 45 + 16 = 61 different sets of solutions.

Answer: 61.

Answer: 1024

24. QuestA positive integer not exceeding 10 is being processed.9 . You need to write a program that displays the sum of digits of this number less than 7. If there are no digits less than 7 in the number, you need to display 0 on the screen. The programmer wrote the program incorrectly. Below this program for your convenience is given in five programming languages.

BASIC	Python
DIM N, DIGIT, SUM AS LONG INPUT N SUM = 0 WHILE N > 0 DIGIT=NMOD 10 IF DIGIT SUM = SUM + 1 END IF N=N\10 WEND PRINT DIGIT	N = int(input()) sum = 0 while N > 0: digit = N% 10 if digit sum = sum + 1 N = N // 10 print(digit)
Algorithmic language	Pascal
alg early integer N, digit, sum input N sum:= 0 nc while N > 0 digit:= mod(N,10) if digit sum:= sum + 1 all N:=div(N,10) kts digit output con	var N, digit, sum: longint; begin readln(N); sum:= 0; while N > 0 do begin digit:= N mod 10; if digit sum:= sum + 1; N:= N div 10; end; writeln(digit) end.
Xi
#include int main() { int N, digit, sum; scanf("%d", &N); sum = 0; while (N > 0) { digit = N% 10; if (digit sum = sum + 1; N = N / 10; } printf("%d",digit); return0; }

Do the following in sequence.

1. Write what this program will display when you enter the number 456.

2. Give an example of such a three-digit number, when entered, the program gives the correct answer.

3. Find all errors in this program (there may be one or more). It is known that each error affects only one line and can be fixed without changing other lines. For each error:

1) write out the line where the error was made;

2) indicate how to fix the error, i.e. give the correct version of the string.

It is enough to indicate the errors and the way to correct them for one programming language. Please note that you need to find errors in the existing program, and not write your own, possibly using a different solution algorithm. Correcting a bug should only affect the line that contains the bug.

Explanation.

The solution uses a Pascal program entry. You can use the program in any of the four other languages.

1. The program will print the number 4.

2. An example of a number, when entered, the program gives the correct answer: 835.

Note for the reviewer. The program does not work correctly due to the wrong displayed variable and the wrong increase in the amount. Accordingly, the program will work correctly if the highest digit (leftmost) in the number is equal to the sum of digits less than 7.

3. There are two errors in the program.

First mistake. Wrong amount increase.

Error line:

sum:= sum + 1;

Correct fix:

sum:= sum + digit;

Second mistake. Incorrect display of the response on the screen.

Error line:

writeln(digit)

Correct fix:

writeln(sum)

25. QuestGiven an integer array of 20 elements. Array elements can take integer values from -10000 to 10000 inclusive. Describe in natural language or in one of the programming languages an algorithm that allows you to find and display the number of pairs of array elements in which at least one number is divisible by 3. In this problem, a pair means two consecutive array elements. For example, for an array of five elements: 6; 2; nine; -3; 6 - answer: 4.

The initial data is declared as shown below in examples for some programming languages and natural language. It is forbidden to use variables not described below, but it is allowed not to use some of the variables described.

BASIC	Python
CONST N AS INTEGER = 20 DIM A (1 TO N) AS INTEGER DIM I AS INTEGER, J AS INTEGER, K AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I ... END	# also allowed # use two # integer variables j and k a = n=20 for i in range(0, n): a.append(int(input())) ...
Algorithmic language	Pascal
alg early integer N = 20 celtab a integers i, j, k nc for i from 1 to N input a[i] kts ... con	const N = 20; var a: array of integers; i, j, k: integer; begin for i:= 1 to N do readln(a[i]); ... end.
Xi	natural language
#include #define N 20 int main() ( int a[N]; int i, j, k; for (i = 0; i scanf("%d", &a[i]); ... return 0; }	We declare an array A of 20 elements. We declare integer variables I, J, K. In a loop from 1 to 20, we enter the elements of array A from the 1st to the 20th. …

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

k:=k+1

all

kts

output k

Pascal

k:= 0;

for i:= 1 to N-1 do

if (a[i] mod 3=0) or (a mod 3=0) then

inc(k);

writeln(k);

k = 0;

for (i = 0; i

if (a[i]%3 == 0 || a%3 == 0)

k++;

printf("%d", k);

natural language

We write the initial value equal to 0 to the variable K. In the loop from the first element to the penultimate one, we find the remainder from dividing the current and next element of the array by 3. If the first or second of the resulting remainders is 0, increase the variable K by one. After the loop is completed, we display the value of the variable K

26. QuestTwo players, Petya and Vanya, play the following game. There are two piles of stones in front of the players. Players move in turn, Petya makes the first move. In one move, the player can add one stone to one of the piles (of his choice) or double the number of stones in the pile. For example, let there be 10 stones in one pile and 7 stones in another; such a position in the game will be denoted by (10, 7). Then in one move you can get any of the four positions: (11, 7), (20, 7), (10, 8), (10, 14). 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 73. The winner is the player who made the last move, i.e. the first to get such a position that there will be a total of 73 stones or more in the piles.

We will say that a player has a winning strategy if he can win for any moves of the opponent. To describe a player's strategy means to describe what move he should make in any situation that he may encounter with different opponent's plays. For example, with initial positions (6, 34), (7, 33), (9, 32), Petya has a winning strategy. To win, he only needs to double the number of stones in the second pile.

Exercise 1.For each of the initial positions (6, 33), (8, 32) indicate which of the players has a winning strategy. In each case, describe the winning strategy; explain why this strategy leads to a win, and indicate the maximum number of moves the winner can take to win with this strategy.

Task 2.For each of the initial positions (6, 32), (7, 32), (8, 31) indicate which of the players has a winning strategy. In each case, describe the winning strategy; explain why this strategy leads to a win, and indicate the maximum number of moves the winner can take to win with this strategy.

Task 3.For the initial position (7, 31), indicate which of the players has a winning strategy. Describe a winning strategy; explain why this strategy leads to a win, and indicate the maximum number of moves the winner can take to win with this strategy. Build a tree of all games possible with the winning strategy you specified. Present the tree in the form of a picture or a table.

(7,31)

Total 38

(7,31+1)=(7,32)

Total 39

(7+1,32)=(8,32)

Total 40

(8+1,32)=(9,32)

Total 41

(9,32*2)=(9,64)

Total 73

(8,32+1)=(8,33)

Total 41

(8,33*2)=(8,66)

Total 74

(8*2,32)=(16,32)

Total 48

(16,32*2)=(16,64)

Total80

(8,32*2)=(8,64)

Total 72

(8,64*2)=(8,128)

Total 136

(7+1,31)=(8,31)

Total 39

(8,31+1)=(8,32)

Total 40

(8+1,32)=(9,32)

Total 41

(9,32*2)=(9,64)

Total 73

(8,32+1)=(8,33)

Total41

(8,33*2)=(8,66)

Total 74

(8*2,32)=(16,32)

Total 48

(16,32*2)=(16,64)

Total 80

(8,32*2)=(8,64)

Total 72

(8,64*2)=(8,128)

Total 136

(7*2,31)=(14,31)

Total 45

(14,31*2)=(14,62)

Total 76

(7,31*2)=(7,62)

Total 69

(7,62*2)=(7,124)

Total 131

Exercise 1.In the initial positions (6, 33), (8, 32) Vanya has a winning strategy. With the initial position (6, 33), after Petya's first move, one of the following four positions can be obtained: (7, 33), (12, 33), (6, 34), (6, 66). Each of these positions contains less than 73 stones. Moreover, from any of these positions Vanya can get a position containing at least 73 stones by doubling the number of stones in the second pile. For position (8, 32), after Petya's first move, one of the following four positions can be obtained: (9, 32), (16, 32), (8, 33), (8, 64). Each of these positions contains less than 73 stones. Moreover, from any of these positions Vanya can get a position containing at least 73 stones by doubling the number of stones in the second pile. Thus, Vanya, for any Petya's move

wins on his first move.

Task 2.In the initial positions (6, 32), (7, 32) and (8, 31) Petya has a winning strategy. With the initial position (6, 32) he must first move to obtain the position (6, 33), from the initial positions (7, 32) and (8, 31). Petya after the first move should get position (8, 32). Positions (6, 33) and (8, 32) were considered when analyzing task 1. In these positions, the player who will move second (now this is Petya) has a winning strategy. This strategy was described in the analysis of task 1. Thus, in any game Vanya plays, Petya wins with his second move.

Task 3.In the initial position (7, 31), Vanya has a winning strategy. After Petya's first move, one of four positions can appear: (8, 31), (7, 32), (14, 31) and (7, 62). In positions (14, 31) and (7, 62) Vanya can win in one move by doubling the number of stones in the second pile. Positions (8, 31) and (7, 32) were considered in the analysis of task 2. In these positions, the player who must make a move (now it is Vanya) has a winning strategy. This strategy was described in the analysis of task 2. Thus, depending on Petya's game, Vanya wins on the first or second move.

27. QuestA long-term experiment to study the Earth's gravitational field is being carried out in the physics laboratory. Every minute, a positive integer is transmitted to the laboratory through the communication channel - the current reading of the Sigma 2015 device. The number of transmitted numbers in the series is known and does not exceed 10,000. All numbers do not exceed 1000. The time during which the transmission takes place can be neglected.

It is necessary to calculate the "beta value" of a series of instrument readings - the minimum even product of two readings, between the moments of transmission of which at least 6 minutes have passed. If such a product cannot be obtained, the answer is considered equal to -1.

You are offered two tasks related to this task: task A and task B. You can solve both tasks or one of them according to your choice. The final grade is set as the maximum of grades for tasks A and B. If the solution of one of the tasks is not presented, then it is considered that the grade for this task is 0 points. Task B is a complicated version of task A, it contains additional requirements for the program.

A. Write a program in any programming language to solve the problem, in which the input data will be stored in an array, after which all possible pairs of elements will be checked. Specify the programming language version before the program.

DO indicate that the program is a solution to TASK A.

The maximum score for completing task A is 2 points.

B. Write a program to solve the problem that is efficient in both time and memory (or at least one of these characteristics).

A program is considered efficient in terms of time if the running time

program is proportional to the number of received instrument readings N, i.e. when N increases by k times, the running time of the program should increase by no more than k times.

A program is considered memory efficient if the size of the memory used in the program for storing data does not depend on the number N and does not exceed 1 kilobyte.

Before the program, indicate the version of the programming language and briefly describe the algorithm used.

DO indicate that the program is a solution to TASK B.

The maximum score for a correct program that is efficient in time and memory is 4 points.

The maximum score for a correct program that is time efficient but memory inefficient is 3 points. REMINDER! Do not forget to indicate to which task each of the programs you submitted belongs.

The input data is presented as follows. The first line contains the number N - the total number of instrument readings. It is guaranteed that N > 6. Each of the next N lines contains one positive integer - the next reading of the instrument.

Input example:

The program should display one number - the product described in the condition, or -1 if such a product cannot be obtained.

Example output for the example input above:

Explanation.

Task B (the solution for task A is given below, see program 4). For the product to be even, at least one factor must be even, so when searching for suitable products, even instrument readings can be considered in tandem with any others, and odd ones only with even ones.

For each indication with number k, starting from k = 7, we consider all pairs admissible under the conditions of the problem, in which this indication is obtained second. The minimum product of all these pairs will be obtained if the first in the pair is taken the minimum suitable indication among all received from the beginning of the reception and up to the indication with the number k - 6. If the next indication is even, the minimum among the previous ones can be any, if odd - only even.

To obtain a time-efficient solution, as you enter data, you need to remember the absolute minimum and minimum even readings for each moment of time as you enter data, multiply each newly obtained reading by the corresponding minimum that was available 6 elements earlier, and select the minimum of all such products.

Since each current low reading is used after 6 more items are entered and becomes unnecessary after that, it is sufficient to store only the last 6 lows. To do this, you can use an array of 6 elements and cycle through it as you enter data. The size of this array does not depend on the total number of entered readings, so this solution will be efficient not only in terms of time, but also in terms of memory. To store absolute and even minimums, you need to use two such arrays. Below is an example of such a program written in an algorithmic language.

Example 1. An example of a correct program in an algorithmic language. The program is efficient both in terms of time and memory.

alg

early

integer s = 6 | required distance between readings

integer amax = 1001 | more than the maximum possible reading

integer N

input N

integer a | another instrument reading

celtab mini | current lows of the last s elements

celtab minichet | even minima of the last s elements

target i

| enter the first s readings, fix the minimums

whole ma; ma:= amax | minimum reading

whole rushing; rushing:= amax | minimum even reading

nc for i from 1 to s

input a

ma:= imin(ma, a)

mini := ma

minichet := rush

kts

integer mp = amax*amax | the minimum value of the product

whole p

nc for i from s+1 to N

input a

if mod(a,2)=0

then n:= a * mini

otherwise if it rushes

then n:= a * minieven

otherwise n:= amax*amax;

all

mp:= imin(mp, n)

ma:= imin(ma, a)

if mod(a,2) = 0 then flicker:= imin(flash,a) all

mini := ma

minichet := rush

kts

if mp = amax*amax then mp:=-1 all

output mp

con

Other implementations are also possible. For example, instead of cyclically filling an array, you can shift its elements each time. In the example below, it is not the minimums that are stored and shifted, but the original values. This requires slightly less memory (one array is enough instead of two), but the solution with shifts is less time efficient than with cyclic filling. However, the running time remains proportional to N, so the maximum score for this solution is also 4 points.

Program 2. An example of a correct Pascal program.

The program uses shifts but is time and memory efficient

var

N: integer

a: array of integers; (storage of instrument readings)

a_: integer; (entering the next indication)

p: integer;

i, j: integer;

begin

readln(N);

(Entering the first s numbers)

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

(Entering other values, finding the minimum product)

ma:= amax; me:= amax;

mp:=amax*amax;

for i:= s + 1 to N do begin

readln(a_);

if a

if (a mod 2 = 0) and (a

if a_ mod 2 = 0 then p:= a_ * ma

else if me

else p:= amax* amax;

if (p

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

for j:= 1 to s - 1 do

a[j] := a;

a[s] := a_

end;

if mp = amax*amax then mp:=-1;

writeln(mp)

end.

If instead of a small array of a fixed size (cyclic or shifted), all original data (or all current minima) is stored, the program remains time efficient but becomes memory inefficient as the required memory grows proportionally to N. Below is an example of such a program in the language Pascal. Similar (and similar in essence) programs are evaluated no higher than 3 points.

Program 3. An example of a correct Pascal program. Program is time efficient but memory inefficient

const s = 6; (required distance between readings)

amax = 1001; (greater than the maximum possible reading)

var

N, p, i: integer;

ma: integer; (minimum number without last s)

me: integer; (minimum even number without last s)

mp: integer; (minimum product value)

begin

readln(N);

(Entering all instrument readings)

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

ma:= amax;

me:= amax;

mp:= amax*amax;

for i:= s + 1 to N do

begin

if a

if (a mod 2 = 0) and (a

me:= a;

if a[i] mod 2 = 0 then p:= a[i] * ma

else if me

else p:= amax * amax;

if (p

end;

if mp = amax*amax then mp:= -1;

writeln(mp)

end.

An enumeration solution is also possible, in which the products of all possible pairs are found and the minimum is selected from them. Below (see program 4) is an example of such a solution. This (and similar) solution is neither time nor memory efficient. It is a solution to task A, but not a solution to task B. The score for such a solution is 2 points.

Program 4. An example of a correct Pascal program. The program is neither time nor memory efficient

const s = 6; (required distance between readings)

var

N: integer

a: array of integers; (all instrument readings)

mp: integer; (minimum product value)

i, j: integer;

begin

readln(N);

(Enter instrument values)

for i:=1 to N do

readln(a[i]);

mp:= 1000 * 1000 + 1;

for i:= 1 to N-s do begin

for j:= i+s to N do begin

if (a[i]*a[j] mod 2 = 0) and (a[i]*a[j]

then mp:= a[i]*a[j]

end;

if mp = 1000 * 1000 + 1 then mp:= -1;

writeln(mp)

For high school graduates. It must be taken by those who plan to enter universities for the most promising specialties, such as information security, automation and control, nanotechnology, systems analysis and control, rocket systems and astronautics, nuclear physics and technology, and many others.

Read the general information about the exam and start preparing. There are practically no changes compared to last year in the new version of KIM USE 2019. The only thing is that fragments of programs written in the C language disappeared from the tasks: they were replaced with fragments written in the C++ language. And from task number 25, they removed the opportunity to write an algorithm in natural language as an answer.

USE score

Last year, in order to pass the Unified State Examination in Informatics, at least for the top three, it was enough to score 42 primary points. They were given, for example, for the correctly completed first 9 tasks of the test.

How it will be in 2019 is still not known for sure: you need to wait for an official order from Rosobrnadzor on the correspondence of primary and test scores. Most likely it will appear in December. Considering that the maximum primary score for the entire test has remained the same, the minimum score will most likely not change either. Let's take a look at these tables:

USE test structure

Informatics is the longest exam (the same is the duration of the exam in mathematics and literature), the duration is 4 hours.

In 2019, the test consists of two parts, including 27 tasks.

Part 1: 23 tasks (1-23) with a short answer, which is a number, a sequence of letters or numbers.
Part 2: 4 tasks (24–27) with a detailed answer, the full solution of the tasks is recorded on the answer sheet 2.

All tasks are connected in one way or another with a computer, but it is not allowed to use it to write a program in group C tasks during the exam. In addition, the tasks do not require complex mathematical calculations and the use of a calculator is also not allowed.

Preparation for the exam

Pass the USE tests online for free without registration and SMS. The presented tests are identical in their complexity and structure to the real exams held in the corresponding years.

Download demo versions of the Unified State Examination in Informatics, which will allow you to better prepare for the exam and make it easier to pass it. All proposed tests were developed and approved for preparation for the Unified State Examination by the Federal Institute of Pedagogical Measurements (FIPI). In the same FIPI, all official versions of the exam are being developed.
The tasks that you will see, most likely, will not be found on the exam, but there will be tasks similar to the demo ones, on the same topic or simply with different numbers.

General USE numbers

Year	Min. USE score	Average score	Number of applicants	Did not pass, %	Qty 100 points	Duration- exam length, min.
2009	36
2010	41	62,74	62 652	7,2	90	240
2011	40	59,74	51 180	9,8	31	240
2012	40	60,3	61 453	11,1	315	240
2013	40	63,1	58 851	8,6	563	240
2014	40	57,1				235
2015	40	53,6				235
2016	40					235
2017	40					235
2018

SPECIFICATION
control measuring materials
unified state exam 2016
in Informatics and ICT

1. Appointment of KIM USE

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

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

Control measuring materials allow to establish the level of development by graduates of the Federal component of the state standard of secondary (complete) general education in informatics and ICT, basic and profile levels.

The results of the unified state exam in informatics and ICT are recognized by educational institutions of secondary vocational education and educational institutions of higher professional education as the results of entrance examinations in informatics and ICT.

2. Documents defining the content of KIM USE

3. Approaches to the selection of content, the development of the structure of the KIM USE

The content of the tasks is developed on the main topics of the informatics 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 ”, “Architecture of computers 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 informatics and ICT course, its most important topics, the most significant material in them, which is unambiguously interpreted in most versions of the informatics and ICT course taught at school.

The work contains both tasks of the basic level of complexity, testing the knowledge and skills provided for by the standard of the basic level, and
and tasks of increased and high levels of complexity, testing the knowledge and skills provided for by the profile level standard. The number of tasks in the KIM variant should, on the one hand, provide a comprehensive assessment 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 for complexity, stability of results, and reliability of measurement. For this purpose, two types of tasks are used in KIM: with a short answer and a detailed answer. The structure of the examination work provides an optimal balance of tasks of different types and varieties, three levels of complexity, 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. The structure of KIM USE

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

Part 1 contains 23 short answer tasks.

In the examination paper, the following types of tasks with a short answer are proposed:

tasks for choosing and recording one or more correct answers from the proposed list of answers;
tasks for calculating 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 and numbers), written without spaces and other separators.

Part 2 contains 4 tasks with a detailed answer.

Part 1 contains 23 tasks of basic, advanced and high difficulty levels. This part contains tasks with a short answer, implying independent formulation and recording of the answer in the form of a number or sequence of characters. Tasks check 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 of this part involve writing a detailed answer in an arbitrary form.

K.Yu. Polyakov
USE in Informatics:
2016 and beyond…
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

Structural changes in 2015-2016

B4-1: Tabular databases

USE in Informatics: 2016 and beyond…
12
B4-1: Tabular databases
1) how many descendants (children, grandchildren, great-grandchildren...) does X have?
2) how many ancestors of X are there in the table?
3) Find your maternal grandfather
23
24
25
K.Yu. Polyakov, 2015
34
57
35
42
http://kpolyakov.spb.ru

USE in Informatics: 2016 and beyond…
13

Messages contain the letters P, O, C, T; used
binary code allowing unambiguous
decoding. Code words:
T: 111, O: 0, P: 100.
Enter the shortest code word for the letter C, with
where the code will allow an unambiguous
decoding. If there is more than one such code, please indicate
the code with the smallest numerical value.
1
0
0x10
0xx
O
11
101
P
K.Yu. Polyakov, 2015
0
0
110
1
1
1
0
1
T
http://kpolyakov.spb.ru

B5: encoding and decoding

USE in Informatics: 2016 and beyond…
14
B5: encoding and decoding
Messages contain three vowels: A, E, I - and five
consonants: B, C, D, D, K. Letters are encoded
prefix code. It is known that all code words for
consonants have the same length, and
A -1, E - 01, I - 001.
What is the smallest possible length of code words for
consonants?
0
5 consonants 3 bits 4 bits 5 bits
4:1xx
0
1
2:01x
0
1
BUT
1: 001
1
E
available: 000
000x 000xx
1
2
4
And
K.Yu. Polyakov, 2015
6 bit
000xxx
8
http://kpolyakov.spb.ru

B6-1: automatic

USE in Informatics: 2016 and beyond…
15
B6-1: automatic
parity restored!
Input: natural number N.
1. The parity bit is added to the end of the binary record
(sum of digits mod 2).
2. Another parity bit is added to the received string.
Specify the smallest number for which the result
executing this algorithm will result in a number
more than 125.
!
Step 2 adds 0 2!
Should get even = 126 or 128
After div 2, parity must be preserved!
126 / 2 = 63 = 1111112: - 6 units, even
Answer:
K.Yu. Polyakov, 2015
31
http://kpolyakov.spb.ru

B10: combinatorics

USE in Informatics: 2016 and beyond…
16
B10: combinatorics
How many 5-letter words are there that contain only
letters P, I, R, and the letter P appears exactly 1 time.
P****
*P***
**P**
***P*
****P
K.Yu. Polyakov, 2015
24 = 16 words
Answer: 16 5 = 80.
http://kpolyakov.spb.ru

B14: Draftsman

USE in Informatics: 2016 and beyond…
19
B14: Draftsman
shift by (–3, –3) 1)
REPEAT N TIMES
2)
move to (a, b) 3)
move to (27, 12) 4)
END REPEAT
shift by (–22, -7)
3N x 220
3 N y 7 0
smallest N > 1
largest N
all possible N
the sum of all N
N x 25
N y 10
N = common divisor(25,10)
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B14: Editor

USE in Informatics: 2016 and beyond…
20
B14: Editor
1) replace(v,w)
2) found(v)
YET Found (222) OR Found (888)
IF found (222)
TO replace (222, 8)
ELSE replace (888, 2)
What is the result of processing the string 88888…8 ?
888888888…8
2 2 2
8
K.Yu. Polyakov, 2015
!
In 4 steps
removed
8 eights!
68 - 8 8 = 4
68
8888 28
http://kpolyakov.spb.ru

USE in Informatics: 2016 and beyond…
28
B16: number systems
How many twos are in ternary notation
values of the number 9118 + 3123 - 27?
9118 = 3236
27 = 33
K.Yu. Polyakov, 2015
3236 + 3123 – 33
1
120 deuces
http://kpolyakov.spb.ru

USE in Informatics: 2016 and beyond…
49
C24: error correction
We need to write a program that displays
the maximum digit of a number that is a multiple of 3. If the number does not contain
digits divisible by 3, it is required to display “NO” on the screen.
-1
readln(N);
maxDigit:= N mod 10;
When does it work
while N > 0 do begin
right?
digit:= N mod 10;
if digit mod 3 1)=last
0 then the digit is divisible by 3
if digit > maxDigit
then
2) last
number less than
maxDigit:= desired
digit;result
N:= N div 10;
-1
end;
if maxDigit = 0 then writeln("NO")
else writeln(maxDigit);
?
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C24: error correction

USE in Informatics: 2016 and beyond…
50

For a given sequence of non-negative
integers, you need to find the maximum
product of two of its elements, whose numbers
differ by at least 8. Number of elements
sequence does not exceed 10000.
Task A (2 points). O(N2) in time, O(N) in memory.
Task B (3 points). O(N) in time, O(N) in memory.
Task B (4 points). O(N) in time, O(1) in memory.
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

USE in Informatics: 2016 and beyond…
51
C27: difficult programming problem
Task A (2 points). The data is stored in an array.
var N: integer;
a: array of integers;
i, j, max: integer;
begin
readln(N);
for i:=1 to N do read(a[i]);
max:= -1;
for i:= 9 to N do
for j:= 1 to i-8 do
if (a[j]*a[i] > max) then
max:= a[j]*a[i];
writeln(max)
end.
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: difficult programming problem

USE in Informatics: 2016 and beyond…
52
C27: difficult programming problem
Task B (3 points). Data in array, O(N) time.
i-8
i
a[i]
m
accumulate!
max a[ j ] a[i] max a[ j ] a[i]
j
j
max:= 0;
m:= 0;
for i:= 9 to N do begin
if a > m then m:= a;
if m*a[i] > max then max:= m*a[i];
end;
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: difficult programming problem

USE in Informatics: 2016 and beyond…
53
C27: difficult programming problem

i-8
i
store in an array
var a: array of integer;
x
Initial array filling:
for i:=1 to 8 do read(a[i]);
Promotion:
for i:=1 to 7 do
a[i]:=a;
a:=x;
K.Yu. Polyakov, 2015
!
It's the queue!
http://kpolyakov.spb.ru

C27: difficult programming problem

USE in Informatics: 2016 and beyond…
54
C27: difficult programming problem
Task B (4 points). Memory O(1), time O(N).
a
x
const d = 8; (shift)
... ( already read the first d pieces )
max:= 0;
m:= 0;
for i:=d+1 to N do begin
read(x);
if a > m then m:= a;
if m*x > max then max:= m*x;
for j:=1 to d-1 do
a[j]:= a;
a[d]:= x;
end;
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: difficult programming problem

USE in Informatics: 2016 and beyond…
55
C27: difficult programming problem
Task B (4 points). No shift (queue-ring).
i 0
1
2
3
9
1
5
6
7
k
0
a
4
10
2 11
3 12
4 5
8
9
N-1
10 11 12 13 14 15 16 17 18
7
6
7
8
a:=data[i];
for i:=0 to d-1 do read(a[i]);
for i:=d to N-1 do begin
read(x);
k:= i mod d;
if a[k] > m then m:= a[k];
if m*x > max then max:= m*x;
a[k]:=x;
end;
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: difficult programming problem

USE in Informatics: 2016 and beyond…
56
C27: difficult programming problem
Calculate the maximum even product of two
indications, between the moments of transmission of which
at least 8 minutes have passed.
x
support
1) the maximum of all
2) maximum even
x
even even * any
even any * even
K.Yu. Polyakov, 2015
store in an array
(queue)
http://kpolyakov.spb.ru

C27: difficult programming problem

USE in Informatics: 2016 and beyond…
57
C27: difficult programming problem
for i:=d to N-1 do begin
read(x);
k:= i mod d;
maximum
even
if a[k] > m then m:= a[k];
if ((a[k] mod 2 = 0) and
(a[k] > mEven)) then mEven:= a[k];
if x mod 2 = 1 then begin
received
odd
if mEven*x > max then
max:= mEven*x;
end
received
even
else
if m*x > max then max:= m*x;
a[k]:=x;
end;
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: difficult programming problem

USE in Informatics: 2016 and beyond…
58
findings
!
K.Yu. Polyakov, 2015
Variability!
http://kpolyakov.spb.ru

findings

USE in Informatics: 2016 and beyond…
59
The end of the film
POLYAKOV Konstantin Yurievich
Doctor of Technical Sciences, teacher of computer science
GBOU secondary school No. 163, St. Petersburg

K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

Informatics exam online tests. B2: logic functions. Appointment of KIM USE

USE score

USE test structure

Preparation for the exam

General USE numbers

Structural changes in 2015-2016

B1: binary number system

B1: binary number system

B1: number systems

B2: logic functions

B2: logic functions

B2: logic functions

B3: graph weight matrices

B3: graph weight matrices

B4-1: Tabular databases

B5: encoding and decoding

B6-1: automatic

B10: combinatorics

B12: network addressing

B12: network addressing

B14: Draftsman

B14: Editor

B15: number of paths in columns

B16: number systems

B16: number systems

B16: number systems

B16: number systems

B16: number systems

B16: number systems

B17: queries in search engines

B18: logical operations, sets

B18: logical operations, sets

B18: logical operations, sets

B18: logical operations, sets

B18: logical operations, sets

B18: logical operations, sets

B18: logical operations, sets

B19: array handling

B19: array handling

B19: array handling

B19: array handling

B19: array handling

B20: loops and conditions ("learn the algorithm")

B20: cycles and conditions

B21: cycles and procedures

B21: cycles and procedures

B21: cycles and procedures

B22: programs for performers

C24: error correction

C24: error correction

C27: difficult programming problem

C27: difficult programming problem

C27: difficult programming problem

C27: difficult programming problem

C27: difficult programming problem

C27: difficult programming problem

C27: difficult programming problem

findings