Как решить подобную задачу? ЕГЭ 2014 информатика

Не думаю, что мой вопрос вытекает за рамки тематики этого сайта, но заранее прошу прощения.
Попалась такая задача, да такая, что подобных не было ни в одном сборнике, ни в демоверсии. Задание было в реальных кимах 2014 года.
Пишу по памяти, поэтому некоторые детали я опускаю.
С4.
Ученые снимают с аппарата "Тонегава" показания раз в минуту.
На вход подается N - число показаний снятых в этот период и сами показания
Ваша задача - написать программу, которая будет находить минимальное произведение двух элементов, полученных с интервалом не менее 6 минут.
Пример вводных данных:
11
20
12
11
4
5
9
10
24
43
20
7
Пример выходных данных:
28

Ограничение по памяти: 1 килобайт.
Ограничение по времени: при увеличении кол-ва элементов в К раз, время выполнения не должно увеличиться более чем в К раз.
Подскажите хотя бы идею решения. Если нужны какие-либо уточнения - спрашивайте.
  • Вопрос задан
  • 4678 просмотров
Решения вопроса 3
@oxygen3
Тоже писал эту задачу. Поддерживал минимум на префиксе. Стресс-тест дома программа прошла, правда в бланке из-за того, что писал на Pascal, а не на C++ написал for i := 1 to n по привычке, а надо было условие i < n, то есть до n-1;
Итак, если мы находимся в элементе с номером i, то minpref - минимум на отрезке от 1 до i-6, который мы поддерживаем (в каждой итерации смотрим на элемент, который был 6 итераций назад и если a[i-6] < minpref то minpref = a[i-6]), и если a[i] * minpref < minout, то minout = a[i] * minpref. Как сделать это с памятью O(n) очевидно, у меня написан костыль, который работает с константной памятью(массив a), можно было использовать стандартную очередь, но за нее бы не поставили максимум баллов по критериям.
Время работы - O(n).
Кусок с считыванием от 0 до 5 можно запихать и в основной цикл, если предварительно всё заполнено +inf.

Если не понятно, то могу какие-то моменты разъяснить.

Собственно код:
#include <stdio.h>
#include <iostream>
using namespace std;
double a[6];

int main(void){
    int i,n;
    double minpref = 1000000, minout = 1000000, xcur, a[5];

    cin >> n;
    for (int i = 0; i <= 5; i++)
        cin >> a[i];

    for (int i = 6; i < n; i++){
        cin >> xcur;
        minpref = min(minpref, a[i % 6]);
        a[i % 6] = xcur;
        minout = min(minout, xcur * minpref);
    }
    cout << minout << "\n";
    return 0;
}
Ответ написан
Идея решения такая, поддерживаем пару чисел дающих минимальное произведение (пусть они будут называться lhs и rhs) - будем обновлять эту пару при каждом новом прочитанном числе.

Кроме пары дающей минимальное произведение храним так же 6 последних прочитанных чисел. Будем называть их a1, a2, a3, a4, a5, a6, где a1 - самое старое, а a6 - самое новое. При каждом новом прочитанном числе мы будем "сдвигать" эту последовательность.

Плюс нужно хранить еще один элемент m - это минимальный из элементов, которые мы уже просмотрели, и который уже "выпал" из последовательности ai.

Мясо начинается когда у нас прочитано 7 элементов, lhs - первый прочитанный элемент он же m, rhs - последний прочитанный элемент и он же a6. Читаем очередной элемент, назовем его cur, новую пару с минимальным произведением ищем среди этого множества:
{ (lhs, rhs), (lhs, cur), (a1, cur), (min, cur) }.

Пусть найденная пара (x, y), тогда делаем следующее:

lhs = x;
rhs = y;
m = min(m, a1);
a1 = a2;
a2 = a3;
a3 = a4;
a5 = a6;
a6 = cur;

Минимальное произведение в конце алгоритма должно быть равно lhs * rhs, если я нигде не облажался.
Ответ написан
ManWithBear
@ManWithBear
Swift Adept, Prague
Возможны проблемы с одинаковыми значениями данных на далеких позициях друг от друга (Не уверен).

#include <iostream>
using namespace std;
struct elem {
    float data;
    int pos;
};
int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    if (N<7) {
        cout<<"Corrupted data";
    }
    elem minVal[13];
    for (int i=0; i<13; i++) {
        minVal[i] = {10001.0f+i,0};
    }
    float in;
    bool flag = true;
    for (int i=0; i<N; i++) {
        cin>>in;
        flag = true;
        for (int j=0; j<13 && flag; j++) {
            if (minVal[j].data>in) {
                flag = false;
                for (int i2=12; i2>j; i2--) {
                    minVal[i2] = minVal[i2-1];
                }
                minVal[j] = {in, i};
            }
        }
    }
    float result = INT_MAX;
    float mult = .0f;
    int delta = 0;
    for (int i=0; i<12; i++) {
        for (int j=i+1; j<13; j++) {
            mult = minVal[i].data*minVal[j].data;
            delta = abs(minVal[i].pos-minVal[j].pos);
            if (delta>=6 && result>mult) {
                result = minVal[i].data*minVal[j].data;
            }
        }
    }
    cout<<result<<endl;
    return 0;
}

Если алгоритм не совсем понятен, вопросы в комменты :)
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
@jezzit
Циклически движетесь от первого элемента к последнему, по пути считаете произведения, и если последнее посчитанное больше меньше предыдущего минимума, обновляете мин.
Может я что не так понял, но задача детская же? неужто вы изучив все сборники не смогли её написать?
Ответ написан
@Neutro
В дополнение к ответу @jezzit
#include <iostream>
#define TIME 6

using namespace std;

int main() {
    int n,min=0xffffff;
    cin >> n;
    int list[n];
    for(int i=0;i<n;i++) {
        cin >> list[i];
        if(i >= TIME) {
            for(int j=i-TIME;j>=0;j--) {
                if(list[i]*list[j] < min) {
                    min = list[i]*list[j];
                }
            }
        }
    }
    cout << min << endl;
    return 0;
}
Ответ написан
@PiloTeZ
...
Если правильно понял задачу, то, ищите 2 самых маленьких числа по мере получения данных, в конце перемножаете эти два числа
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы