26

Re: The job from Unified State Examination on computer science

27

Re: The job from Unified State Examination on computer science

Hello, crawling-web-crawler, you wrote: CWC> we Search for a maximum from product of a current element (behind a window on the right) on a maximum from viewed (behind a window at the left). If answer N this product a [i] * a [j] at i + k <= j, we find the decision, survey an element with an index j, because a [j] * max (a [0]..., a [j-k])> = a [j] * a [i]. Yes, idea absolutely correct (the first gave it watchmaker). About implementation. In the full decision well to consider that numbers arrive on one (for example from a file): the Input data is presented as follows. In the first line number N - total of elements of sequence is set. It is guaranteed that N> 8. In each of following N of lines one nonnegative integer number - the next element of sequence is set. I.e. well to make usage example max_product which does not use O (N) storage. In your code the list in the size N is used just. And direct usage max_product results with reading of numbers in the list that at once gives 3 points instead of 4.

28

Re: The job from Unified State Examination on computer science

Hello, Serg27, you wrote: S> Hello, crawling-web-crawler, you wrote: CWC>> we Search for a maximum from product of a current element (behind a window on the right) on a maximum from viewed (behind a window at the left). If answer N this product a [i] * a [j] at i + k <= j, we find the decision, survey an element with an index j, because a [j] * max (a [0]..., a [j-k])> = a [j] * a [i]. S> Yes, idea absolutely correct (the first gave it watchmaker). About implementation. In the full decision well to consider that numbers arrive on one (for example from a file): S> S> the Input data is presented as follows. In the first line number N - total of elements of sequence is set. It is guaranteed that N> 8. In each of following N of lines one nonnegative integer number - the next element of sequence is set. S> I.e. well to make usage example max_product which does not use O (N) storage. In your code the list in the size N is used just. And direct usage max_product results with reading of numbers in the list that at once gives 3 points instead of 4. Me the algorithmic task interested, and these are insignificant details . If it is necessary, it is possible to store k elements in a cyclic buffer, whence the last element will leave for recomputation of a maximum of the viewed elements.

29

Re: The job from Unified State Examination on computer science

E> 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? In Unified State Examination check - all is simple. There are docks for experts, where is absolutely unambiguous , for what to give a maximum. It is the linear algorithm and an array of the minimum size. Enough big list of possible errors \CORRIGENDAS for which it is not necessary to reduce is thus registered. Your decision pulls on 3 points. E> 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? Here at oral examination I without questions would deliver 5 points,  the decision together with you, would look, whether it is possible is better. And on Unified State Examination - no more than 3 points. For nested loops are. And an array not the minimum size. Therefore on written Unified State Examination-control to search better. On oral - it is possible to tell that it is ready.

30

Re: The job from Unified State Examination on computer science

Hello, Serg27, you wrote: S> Last night the daughter asked to help with the task from examination of Unified State Examination in computer science for which it prepares. At school anybody from them could not, the teacher told something clever - and nobody understood it. Language - Python. I at first perceived the task on hearing and solved S> [q] 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. Value of each element of sequence does not exceed 1000. The amount of elements of sequence does not exceed 10000. Sorry, just noted an amusing problem. Also did not understand, why nobody offered such variant? It it is possible and on storage , but already laziness. # - * - coding: utf-8 - * - import numpy as np s = np.array ([10, 100, 45, 55, 245, 35, 25, 10, 10, 10, 26]) result = 0 max_prev = s [0] for i in range (8, len (s)): result = max (result, s [i] * max_prev) max_prev = max (max_prev, s [i - 7]) print (result) O. Badly searched. At crawling-web-crawler exactly such. Sorry.

31

Re: The job from Unified State Examination on computer science

Hello, Andrey Ushakov, you wrote: > Sorry, just noted an amusing problem. Also did not understand, why nobody offered such variant? It it is possible and on storage , but already laziness. > O. Badly searched. At crawling-web-crawler exactly such. Sorry. You optimized on time, but not on storage. Would receive on Unified State Examination 3 points instead of 4. But also not 2 points if resulted a straight line the decision with O (N*N) on time.

32

Re: The job from Unified State Examination on computer science

Hello, Serg27, you wrote: S> Hello, Andrey Ushakov, you wrote: >> Sorry, just noted an amusing problem. Also did not understand, why nobody offered such variant? It it is possible and on storage , but already laziness. >> O. Badly searched. At crawling-web-crawler exactly such. Sorry. S> you optimized on time, but not on storage. Would receive on Unified State Examination 3 points instead of 4. But also not 2 points if resulted a straight line the decision with O (N*N) on time. I wrote that is possible and on storage (it is necessary to store only last 8 elements in collections.deque), but laziness. Well, if insist: # - * - coding: utf-8 - * - from collections import deque from io import StringIO file = StringIO (' 10\n100\n45\n55\n245\n35\n25\n10\n10\n10\n26\n ') with file: n = int (file.readline ()) result = 0 max_prev = int (file.readline ()) container = deque ([int (file.readline ()) for i in range (7)]) for _ in range (n-8): this = int (file.readline ()) result = max (result, this*max_prev) max_prev = max (max_prev, container.popleft ()) container.append (this) print (result)