C4 How to solve a similar problem? ЕГЭ 2014 informatics

I do not think that my question is beyond the scope of this site, but I apologize in advance.

There was such a task, but such that there was no such thing in any collection or in the demo version. The task was in real 2014 kimah. I am writing from memory, so I omit some of the details.

C4.

Scientists remove testimony from the Tonegawa apparatus once a minute. The input is N - the number of readings taken during this period and the readings themselves. Your task is to write a program that will find the minimum product of two elements obtained at intervals of at least 6 minutes.

Sample input:

11 20 12 11 4 5 9 10 24 43 20 7

Sample output: 28

Elements of the input is guaranteed to be real. The number of elements is up to 1000. The maximum reading is 10,000.

Memory limit: 1 kilobyte.

Time limit: with an increase in the number of elements by K times, the execution time should not increase by more than K times.

Prompt at least the idea of ​​a solution. If you need any clarification - ask.

  • Yes. And there is. But it is understood that the program will immediately give all the indications at the entrance. - V. Kamenev
  • in my memory at HK there were several problems from C4, for the most part the questioners lied in the wording. "By memory" - does not roll. Look for exact wording. For example, in the form in which you have written, there is more misunderstanding than understanding, at least with me (after four readings). - Yura Ivanov
  • I will be very happy if I made a mistake when I read this task in a panic. I really hope that the CIMs will merge. My cellmates say that I wrote everything correctly. - V. Kamenev
  • @ Vlad Kamenev, didn’t you accidentally misinterpret the wording? If you can have thousands of elements, but at the same time there is a 1 kilobyte limit, you can hardly speak about real numbers - it turns out that each number has one byte. And storage of real numbers in one byte .. theoretically, probably, it is possible, but in practice they don’t do that anywhere - DreamChild
  • I suspect that 1Kb is not related to the input data, but to the use of any additional internal structures by the program. But in this case, it is still not completely clear. - user6550

3 answers 3

  1. we make a queue (fifo, without any problems is implemented on the knee from the array) for the interval - 6 elements, fill it with the first 6 elements from the input.
  2. Starting with the 7th entry element, we start looking for the minimum of the product.
    • At each iteration, we adjust the value of the minimum 1st factor. it is equal to the minimum of the current minimum and the first element in the queue
    • check the product of the obtained minimum and the element from the input array (7th, 8th, etc.), save the minimum product
    • we push the first element out of the queue (we have already taken it into account either at the minimum, or it is more, it means it will not affect the result already), and push the new element (just processed) from the input into the queue

Since the elements are real, it is necessary in § 2.1 and further to take into account not only the minimum element, but also the maximum one in order to take into account negative factors.
Plus check input - the number, range, etc.

Text or demo on javascript'e.

  • <bore> There the first number in the input is the number of elements </ bore> - Veikedo
  • @Veikedo, it was "prompt at least the idea of ​​a solution." - Yura Ivanov

Idea - please :) Optimization is possible ...

#include <limits.h> #include <stdio.h> static unsigned int data[] = { 11, 20, 12, 11, 4, 5, 9, 10, 24, 43, 20, 7 }; #define DATA_LENGTH (sizeof(data)/sizeof(data[0])) #define INTERVAL 6 int main() { unsigned long min = ULONG_MAX; size_t i, j; for( i = 0; i < DATA_LENGTH-INTERVAL; i++ ) { for( j = i+INTERVAL; j < DATA_LENGTH; j++ ) { unsigned long m = data[i] * data[j]; if( m < min ) min = m; } } return printf( "min = %lu\n", min ) == EOF; }
  • one
    The input numbers are real. Plus, the array is not an option, since 1000 real elements is more than 1 kilobyte of memory. + This is not a linear complexity. For such a decision "in the forehead" we get only 2 out of 4 points. I would have written it myself, but I want 4 points, not 2 - V. Kamenev
  • > The input numbers are real What is the difference? > array is not an option. What's the option? This is just an example of where the input data comes from. I do not think that this is a vague "memory limit". - user6550
  1. Get a variable in which you will store the minimum product. At the beginning it is equal to the product of the 1st and 2nd elements
  2. Make a loop in which you will go from the first element of the input sequence to the last
  3. Inside this cycle, make another cycle from the element i + 1 to the element i + 6, where i is the index of the element from the previous cycle
  4. Inside a nested loop, compare the variable from the first step (the one in which you store the minimum product) with the product of the i-th and o-th elements (where j is the index of the element from the nested loop). If the current work is less than the minimum, then update the minimum.

Actually, everything. Do not forget that for i> = N-6 (N is the length of the input sequence) in a nested loop, you need to adjust the range of the nested loop to avoid going beyond the boundaries of the sequence

  • asymptotics is nonlinear - Veikedo