EGE past and present

Introduction

Hello! I am a student of the Faculty of Mathematics, I study at the 3rd year, and it just so happened that I got carried away with the solution of the Unified State Exam problems of Part C both in mathematics and computer science.

Unfortunately, the exam on computer science pay the least attention. You may ask why I decided that? Yes, at least, because for 7 years the tasks in mathematics change from year to year, and fundamentally, but in computer science they have been and still are. Every year I saw the same tasks. And you know what? This is really tired, because the exam on computer science turns into a kind of - “put your hand on solving the same type of problem and get your top five”.

In 2012, the exam on computer science finally paid attention. And it has changed (with all three parts A, B, C).
')
All who are interested to look at the tasks that have been over 7 years and how they were changed in 2012, please roll up. We will consider the C part, since, precisely, it is of more interest. Although the A and B parts of computer science have also changed very seriously, we will consider them next time if you are interested.

Tasks that were before 2012

C1
Task C1 is a classic problem of hitting a point in a certain area, which is given graphically. I remember how with these puzzles we were steamed up in the first year ...
Actually the condition of the problem:

It was necessary to write a program that, when executed, reads the coordinates of a point on the plane (x, y are real numbers) from the keyboard and determines the belonging of this point to a given shaded area (including borders). The programmer was in a hurry and wrote the program incorrectly.

Pascal program var x, y: real; begin readln (x, y); if y <= x then if y <= - x then if y> = x * x-2 then write ('belongs') else write ('not owned') end.

It is required to perform the following successively:
1) Give an example of such numbers x, y, for which the program incorrectly solves the problem.
2) Indicate how the program needs to be refined so that there are no instances of its malfunctioning. (This can be done in several ways, so you can specify any correct way to refine the source program.)

Let's do each of the items.

1) To solve point 1, it is necessary to understand what the source program is doing. After a bit of reasoning, it can be concluded that it checks whether the dot falls into the area highlighted in red. That is, any point belonging to the gray area and not belonging to the red area is the answer to the question posed. For example, x = 2, y = 2 or x = 0.5, y = 0.5 or x = -0.5, y = 0.5 (a bunch of such points choose any).


2) Since Pascal (Delphi) is the most popular programming language on the Unified State Exam, we will write the correct program on it that determines the belonging of the entered point to the specified area. To do this, we divide the region into two sets of points relative to the ordinate axis (that is, x <= 0, x> = 0)

 var x, y: real;
 begin
   readln (x, y);
     if (y> = x * x-2) and (y <= x) and (x> = 0) or (x <= 0) and (y <= - x) and (y> = x * x-2 ) then
      write ('belongs')
       else 
     write ('does not belong');   
 end.

The first condition in the if - e means the belonging of the lilac area, and the second - the blue, and we take their union.



Well, that's all with task C1, we figured out. Easy, isn't it ?!

C2
Task C2 is a fairly simple task of processing data in an array, something like: calculate the arithmetic average of even elements of the array.
Consider a specific example:

Given an integer array of 30 elements. The elements of the array can take values ​​from 0 to 1000. Describe in Russian or in one of the programming languages ​​an algorithm that allows you to calculate and display the arithmetic average of the elements of the array that have an odd value. It is guaranteed that at least one element in the source array has an odd value.

Decision:

 Const N = 30;
 Var a: array [1..N] of integer;
        i, x, y: integer;
        s: real;
 begin
    for i: = 1 to N do 
       readln (a [i]);
 x: = 0;  y: = 0;
 for i: = 1 to N do
     if (a [i] mod 2 = 1) then 
       begin
         x: = x + a [i];
         y: = y + 1;
       end;
   s: = x / y;
 writeln (s);
 end.

In this problem, I think even the comments are unnecessary, since it is very simple. Although there were modifications to this task more difficult, for example: ... calculate and output the arithmetic average of the elements of the array, the sum of digits, which is an odd number. The task is simple, but say an order of magnitude more difficult.

C3



Perhaps this is the most notorious task. She is fed up with everything: from schoolchildren to teachers. My teacher, who checks the exam, most of all complains about this problem: “Well, what kind of idiot came up with this task? Tired of ... ".

Judging objectively, this task has nothing to do with computer science. Why is she sitting in C for 7 years? Unclear!

Actually, the task is a game in which two players play, making moves. Consider one of these unfortunate problems and the method of its solution. By the way, it was this task that fundamentally changed in 2012.
The condition of the problem is as follows:

Two players play the next game. Before them lie two piles of stones, in the first of which there are 3, and in the second there are 4 stones. Each player has an unlimited amount of stones. Players take turns. A move is that the player either doubles the number of stones in a pile or adds 4 stones to a pile. The player, after the turn, which the total number of stones in two piles becomes more than 25, loses . Who wins in the error-free play of both players — the player making the first move, or the player making the second move? What should be the first move of the winning player? Justify the answer.

To solve the problem, you need to build a game tree. Consider all possible moves of both players, who are obviously not losing (players cannot walk to their own detriment).



It is clear from the game tree that no matter how the first player resembles, the total number of stones in both heaps will be more than 25, and therefore he loses. So, with the right game wins the second player.

Well that's all. With C3, we also figured out! How is she to you? For me - so very boring. If a couple of times to solve problems of this type, then they pose no difficulty!

C4
To be honest, I don’t like the C4 task. One of its condition is half a page worth. Unfortunately, this task does not test the student's algorithmic knowledge, but more technical.
The condition of the problem is as follows:

At the entrance to the program, information is given about the passing of examinations by students of the 9th grade of a certain secondary school. The first line reports the number of students N, which is not less than 10, but not more than 100, each of the following N lines has the following format: <Last name> <First name> <rating>, where <Last Name> is a line consisting of no more than 20 characters, <Name> - a string consisting of no more than 15 characters, <estimates> - three integers separated by a space, corresponding to the estimates of a five-point system. <Last Name> and <First Name>, as well as <First Name> and <assessment> are separated by a single space. Example input line:
Ivanov Peter 4 5 4
It is required to write a program that will display the names and names of the three best students in the average score. If among the rest there are students who scored the same average mark as one of the three best, then their names and surnames should be derived. Required names and surnames can be displayed in any order.

Since it’s very difficult to solve this problem yourself, I’ll give an example from the EGE codifier (sample for verification).


It seems to me that task C4 should have a slightly different character, but, namely: to test, in addition to technical knowledge, the student’s algorithmic knowledge, such as sorting, data structures. In general, I want this task to be easy to implement, but difficult to solve the solution. Now, just the opposite is easy to solve but difficult to write.

Tasks in 2012

C1
It seems that the compilers of the USE decided that the problem of hitting a point in a certain area is too complicated (as for me, this is not at all the case). Task C1 was literally simplified. Now, instead of a coordinate system, the numerical line is considered, and instead of a region, the union of segments is considered. It is necessary to determine the belonging of the segments by the entered number.


It is not clear why it was necessary to simplify this already simple task !?

C2
This task remained unchanged. It is necessary to process the elements of the array.

C3
But this task has changed radically.
The condition is:

The performer Utroitel has two commands that are assigned numbers:
1. add 1
2. multiply by 3.
The first of them increases the number on the screen by 1, the second - triples it. A program for a morning programmer is a sequence of commands.
How many programs have the number 1 converted to the number 29? Justify the answer.

The first thing that came to mind after reading was to write a recursive function that calculates the number of necessary programs. But having read the condition of the problem again, I realized that such an answer would not work. They need a reasonable answer, not a program. It is clear that this problem is about dynamic programming.

I will give the solution from the codifier:
Let R (n) be the number of programs that convert the number 1 to the number n. Denote by t (n) the greatest multiple of three, not exceeding n. Both teams of the artist increase the initial number, therefore the total number of commands in the program cannot exceed 28.
The following relationships are true:
1. If n is not divisible by 3, then R (n) = R (t (n)), since there is a unique way to get n from t (n) - by adding ones.
2. Let n be divisible by 3.
Then R (n) = R (n / 3) + R (n-1) = R (n / 3) + R (n-3) (if n> 3).
For n = 3, R (n) = 2 (two ways: by adding two units or
single multiplication by 3).
Therefore, it is enough to gradually calculate the values ​​of R (n) for all
numbers that are multiples of three and not exceeding 29: we first calculate R (1), then R (3), R (6), etc.
We have:
R (2) = 1
R (3) = 2 = R (4) = R (5)
R (6) = R (2) + R (3) = 1 + 2 = 3 = R (7) = R (8)
R (9) = R (3) + R (6) = 2 + 3 = 5 = R (10) = R (11)
R (12) = R (4) + R (9) = 2 + 5 = 7 = R (13) = R (14)
R (15) = R (5) + R (12) = 2 + 7 = 9 = R (16) = R (17)
R (18) = R (6) + R (15) = 3 + 9 = 12 = R (19) = R (20)
R (21) = R (7) + R (18) = 3 + 12 = 15 = R (22) = R (23)
R (24) = R (8) + R (21) = 3+ 15 = 18 = R (25) = R (26)
R (27) = R (9) + R (24) = 5 + 18 = 23 = R (28) = R (29)
Answer: 23

For me, this task is much more interesting than the game. It requires from the student, at least, an idea of ​​the concept of dynamic programming.
What do you think?

C4
Task C4 this year also improved slightly. Now you do not need to read these names and surnames as in the previous task C4. Actually the condition is:

At the accelerator for a large number of particles, the velocity of each of them is measured. In order for the documentation to qualitatively distinguish one series of experiments from another, each series was decided to be characterized by a number equal to the maximum product of the pairs of velocities of different particles from all the products.
You are invited to write an effective, including the memory used, program that will process the results of the experiment, finding the desired value. In our model, the velocity of a particle is a quantity that can take both positive and negative values. It should be taken into account that there can be a lot of particles, the speed of which is measured, but there can not be less than two.
The input to the program in the first line is the number of particles N. Each of the following N lines contains one signed integer, which in absolute value does not exceed 10,000.
Sample input:
five
123
1000
-12
ten
1000
The program should output a single integer equal to the maximum product of the velocity pairs of different particles from all products.
Sample output for the above sample input:
1,000,000

In this problem, a lot of conditions. First, it is required to write the program as efficiently as possible in time and from memory. Secondly, it says that there can be a lot of data. This is a subtle hint that if we decide to write the input data into an array, we will not get an effective solution. A naive way to solve this problem: write everything into an array and double-cycle through the elements of the array, finding the desired number. Obviously, such an algorithm requires O (n * n) time and O (n) memory. This is bad. ... For this solution you can get a maximum of 2 points out of 4.

With a little thought it can be understood that, since the initial number consists of the product of 2 signed numbers, it will be maximal if these are the two biggest or two smallest of the input numbers. That is, it is necessary to find the two largest and two smallest numbers, then compare their work and give the answer. And all this can be done in one pass without even saving the data into an array.

I think this task is much nicer than C4 tasks of previous years.

Conclusion

Well, here we met with the tasks of the USE of Part C of computer science. I am glad that all the tasks are available for the student who was preparing for the exam. Also I am glad that you can write a program in any programming language (there were Python, PHP, Basic if only the verifier knew this language).

What tasks did you like more old or new?