1

Topic: The job from Unified State Examination on computer science

2

Re: The job from Unified State Examination on computer science

3

Re: The job from Unified State Examination on computer science

Hello, Erop, you wrote: E> it would Seem, for one pass it is found 9 greatest numbers with their positions, well and further it is sorted stupidly out 36 steams? It also was my second variant. For this purpose it is necessary to be able to do lists of tuples (the daughter heard for the first time about tuple from me), introduction of the list of 9 greatest numbers demands or the difficult logic on its update, or knowledge that lists can be sorted (that too a daughter did not know), etc. Besides I reflected - whether sending about 9 greatest numbers with positions is true and started to search for counter-examples... But here I also invented more simple decision.

4

Re: The job from Unified State Examination on computer science

Hello, Serg27, you wrote: S> For the given sequence of nonnegative integer numbers it is necessary to find the maximum product of its two elements which numbers differ not less than on 8 If there is such pair with indexes i <j, product of pair with indexes k, j where k <i, will be no more. That is simply enough to store a maximum from already viewed elements and to multiply only by it. Naturally with a time delay 8. int solve () {const int d = 8; int b [d] = {0}; int n = get_next_int (); int r = 0; int m = 0; for (int i = 0; i <n; ++ i) {int& e = b [i % d]; m = max (m, e); e = get_next_int (); r = max (r, m * e);} return r;}

5

Re: The job from Unified State Examination on computer science

Hello, watchmaker, you wrote: W> If there is such pair with indexes i <j, product of pair with indexes k, j where k <i, will be no more. That is simply enough to store a maximum from already viewed elements and to multiply only by it. Naturally with a time delay 8. Yes, idea absolutely correct. Well only for my daughter implementation - a remainder of division of an index for implementation of a cyclic buffer does not approach and usage of the link it is too difficult. Therefore we use pop and append lists Python.

6

Re: The job from Unified State Examination on computer science

Hello, Serg27, you wrote: S> It also there was my second variant. For this purpose it is necessary to be able to do lists of tuples (the daughter heard for the first time about tuple from me), introduction of the list of 9 greatest numbers demands or the difficult logic on its update, or knowledge that lists can be sorted (that too a daughter did not know), etc. Besides I reflected - whether sending about 9 greatest numbers with positions is true and started to search for counter-examples... But here I also invented more simple decision. And what such "more simple"? Here look, I write from a head: struct xxxFinder {enum {maxDist = 8}; std:: vector <std:: pair <int, int>> data; int curPos; xxxFinder (): curPos (0), data (std:: pair <int, int> (0, 0), maxDist + 1) {}; void pushNumber (int n) {curPos ++; if (n> data [0].first) {int i = 0; while (i <maxDist && data [i+1].first <n) {data [i] = data [i+1]; i ++;} data [i].first = n; data [i].second = curPos;} } int maxProd () {int res = 0; for (int i = 0; i <data.size (); i ++) {for (int j = i + 1; j <data.size (); j ++) {if (abs (data [i].second - data [j].second)> minDist && data [i].first * data [j].first> res) {res = data [i].first * data [j].first> res;}}} return res;}}; It, on idea, both the decision and idle time.

7

Re: The job from Unified State Examination on computer science

Hello, Erop, you wrote: E> It, on idea, both the decision and idle time. Yes, it both the decision and idle time. But the decision which gave watchmaker easier - the code less, is less than expense of time and storage. Certainly if to tell about production that these decisions are equivalent - the main thing to write them correctly...

8

Re: The job from Unified State Examination on computer science

Hello, Serg27, you wrote: S> Yes, it both the decision and idle time. But the decision which gave watchmaker easier - the code less, is less than expense of time and storage. S> is finite if to tell about production that these decisions are equivalent - the main thing to write them correctly... Difference Truth can it will be shown if there will be a number not 8, and tell 100000000. Well it always so if the decision is, and is necessary "another, but it is better", thus it is not clear than better it is difficult to invent as it is not clear to think of what

9

Re: The job from Unified State Examination on computer science

Hello, Serg27, you wrote: S> I Offer for warm-up. Naturally, B.Vpolne's variant is interesting only approaches for interviews. It in a nail into a head to hammer for  bureaucratism of a statement. The decision is quite obvious: a sliding window on a maximum of 8 elements with their positions. s = [10, 100, 45, 55, 245, 35, 25, 10, 10, 10, 26] buffer = [(0, 0)] result = 0 for i in range (len (s)): candid = s [i] * max (map (lambda p: p [1], filter (lambda p: i - p [0]> 8, buffer)), default=0) if candid> result: result = candid if s [i]> max (map (lambda p: p [1], buffer)): buffer.append ((i, s [i])) buffer = buffer [0:8] print (result)

10

Re: The job from Unified State Examination on computer science

S> the Decision gave watchmaker. Wishing to make - do not look its message Task 4. If to make And - too goes. Is practically a question on interview in computer office...

11

Re: The job from Unified State Examination on computer science

Hello, pestis, you wrote: P> It in a nail into a head to hammer for  bureaucratism of a statement. The decision is quite obvious: a sliding window on a maximum of 8 elements with their positions. Idea of the decision the same that at Egor also that mine "the second variant". Implementation hardly another - maximum search becomes at once in a pass cycle. The same lack - implementation is more difficult (than at watchmaker), there are more expenditures on calculations and storages. It is visible that such decision most likely and will be implemented - at once came to mind 3  (I, Egor and you) from 4.

12

Re: The job from Unified State Examination on computer science

Hello, Serg27, you wrote: S> Idea of the decision the same that at Egor also that mine "the second variant". Implementation hardly another - maximum search becomes at once in a pass cycle. The same lack - implementation is more difficult (than at watchmaker), there are more expenditures on calculations and storages. Same a python. On  it would be easier, on  faster, on  is more functional. And what in this decision of such difficult? The schoolboy about  does not know, let makes two arrays and accurately them synchronizes. S> it is visible that such decision most likely and will be implemented - at once came to mind 3  (I, Egor and you) from 4. Logically. In the conditions of examination  decisions . Though examinations became for a long time already not those that before.  under a hand the variant introductory in  local high school so I for 20 minutes solved them in mind about 10 years ago got without being strained at all. In my time the people on half a year intensively prepared,  on 100 tasks in day and all the same the majority could not master 5 tasks from the ticket for led out time.

13

Re: The job from Unified State Examination on computer science

E> Well it always so if the decision is, and is necessary "another, but it is better", thus it is not clear than better it is difficult to invent as it is not clear to think of what There is written, than: storage and in the speed. The square algorithm with  on all numbers is minimum admissible candidate solution. If in it there are no errors you will receive 2 crude points. If you refine, you receive 3 or even 4 crude points - a maximum.

14

Re: The job from Unified State Examination on computer science

Hello, LaptevVV, you wrote: LVV> the Square algorithm with  on all numbers is minimum admissible candidate solution. I gave algorithm linear on time and constant on storage. All  storage - an array from 9 pairs ... The Alternative decision contains an array from 9  and does not contain final running on 36 steams. It it is better. LVV> if in it there are no errors you will receive 2 crude points. LVV> if you refine, you receive 3 or even 4 crude points - a maximum. Why?

15

Re: The job from Unified State Examination on computer science

Hello, Kodt, About search of a maximum among the numbers different on distance no more than on 8? Then it is elementary, a sliding window, width 8. Only one I read in the initial message ?.... It is necessary to find the maximum product of its two elements which numbers differ not less than on 8.

16

Re: The job from Unified State Examination on computer science

LVV>> the Square algorithm with an array on all numbers is minimum admissible candidate solution. E> I gave algorithm linear on time and constant on storage. All  storage - an array from 9 pairs ... E> the Alternative decision contains an array from 9  and does not contain final running on 36 steams. It it is better. Well so it also is the optimal. For it you receive 4 points if there are no errors - they are registered in instructions for the expert. LVV>> if in it there are no errors you will receive 2 crude points. LVV>> if you refine, you receive 3 or even 4 crude points - a maximum. E> why? The square algorithm with an array on all numbers is a decision of the task And. Its improving is a decision of the task of B.Za the task a maximum 4 points if there are no errors.

17

Re: The job from Unified State Examination on computer science

Hello, Kodt, you wrote: Only one you do not read the previous line: S>> I at first perceived the task on hearing and solved "another". Here also it became interesting to me, what other task solved Serg27 Yes, another - on distance no more than 8.

18

Re: The job from Unified State Examination on computer science

Hello, LaptevVV, you wrote: LVV> Well so it also is the optimal. Well so in a subject compare such two decisions

19

Re: The job from Unified State Examination on computer science

LVV>> Well so it also is the optimal. E> well so in a subject compare such two decisions Sorry, the variant of the second companion - is better. At it in an explicit form the single-valued cycle, and at you is enclosed . At it simple pass under the list of numbers, and at you then still additional calculations after pass. And storages at it it is less used.

20

Re: The job from Unified State Examination on computer science

The most simple for the schoolboy implementation of search of 9 greatest numbers and search of all 9 * 9/2 steams looks so: long maxMul (int A [], int N) {int indicies [9]; int maximum [9] = {-1,-1,-1,-1,-1,-1,-1,-1,-1};//find 9 maximums in array and save them for (int i = 0; i <9; i ++) {for (int j = 0; j <N; j ++) if (j! = i && maximum [i] <A [j]) {maximum [i] = A [j]; indicies [i] = j;} A [indicies [i]] =-1;} long maxMul =-1; for (int i = 0; i <9; i ++) for (int j = i + 1; j <9; j ++) {if (abs (indicies [i] - indicies [j])> = 8) {long mul = long (maximum [i]) * long (maximum [j]); maxMul = max (maxMul, mul);}} return maxMul;} At examination without the computer it certainly is difficult.

21

Re: The job from Unified State Examination on computer science

Hello, LaptevVV, you wrote: LVV> At it in an explicit form the single-valued cycle, and at you is enclosed . But I is more obvious. And "nested" it constant. It is iteration of 36 steams - candidates. The number of pairs from N does not depend, since N == 9 LVV> At it simple pass under the list of numbers, and at you then still additional calculations after pass. LVV> and storages at it it is less used. On 9 int' I about that also wrote that in my decision it is not so clear, where it is better. Type for lowering of the expenditure of storage with 18 int' to 8-9 to struggle? Well, that is, here you write any control/examination/interview and . , invented such decision. What further to do, search for the decision better or to pass to other problems, or to say, what it is ready?

22

Re: The job from Unified State Examination on computer science

Hello, iriska2, you wrote: I> the Most simple for the schoolboy implementation of search of 9 greatest numbers and search of all 9 * 9/2 steams look so: you would receive 3 balls For this decision, instead of 4. This decision needs storages O (N) as 9 times transit on an input array and consequently this array should exist in storage. On time it is linear from N, i.e. satisfies to one of two requirements. Therefore 3, instead of 2 points. Remaining decisions above can work with indefinite number input the data, therefore on storage they do not have dependence from N. And authors would receive 4 points for them.

23

Re: The job from Unified State Examination on computer science

Hello, Serg27, you wrote: S> Hello, iriska2, you wrote: I>> the Most simple for the schoolboy implementation of search of 9 greatest numbers and search of all 9 * 9/2 steams look so: S> you would receive 3 balls For this decision, instead of 4. This decision needs storages O (N) as 9 times transit on an input array and consequently this array should exist in storage. On time it is linear from N, i.e. satisfies to one of two requirements. Therefore 3, instead of 2 points. Remaining decisions above can work with indefinite number input the data, therefore on storage they do not have dependence from N. And authors would receive 4 points for them. Yes, you are right, I inattentively read a condition, the array, besides check i thought that on an input already! = j too the superfluous.

24

Re: The job from Unified State Examination on computer science

Hello, Erop, you wrote: E> it would Seem, for one pass it is found 9 greatest numbers with their positions, well and further it is sorted stupidly out 36 steams? A counterexample: 2, 5, 2, 2, 2, 2, 2, 2, 2, 1 That this algorithm worked, it is necessary to take not less than 16 greatest numbers.

25

Re: The job from Unified State Examination on computer science

Hello, Sergei MO, you wrote: SM> the Counterexample: SM> SM> 2, 5, 2, 2, 2, 2, 2, 2, 2, 1 SM> SM> That this algorithm worked, it is necessary to take not less than 16 greatest numbers. The citation from my initial message: Besides the doubt in correctness of a hypothesis which I based on the decision crept in. Only I decided it to prove, how at once found the normal decision... About a hypothesis that it is necessary to search for the decision among 9 greatest numbers, and there was a speech. Well and a counterexample I started to consider about same. But after arrival to a head of the simple decision, desire to suspect this subject disappeared... (Besides it there was very much a late evening). In general it is necessary to prove, well and to find data size (9, 16, 17????)