Найти произведение двух наибольших скоростей

Question

Я писал ЕГЭ по информатике, сегодня стали известны результаты. Почему-то в C4 мне поставили всего лишь 1 балл из 4, хотя задача наипростейшая. К сожалению, у меня нет точной формулировки задания, поэтому напишу по памяти. Вводится сначала число N (количество частиц), потом N скоростей частиц (по условию от -10000 до 10000). Нужно вывести произведение двух наибольших из скоростей. Причём это нужно сделать эффективно по памяти и вычислениям. Вот мой код (точь-в-точь из моей работы):

#include <iostream>
using namespace std;

int main()
{
    int N; cin >> N;
    int m[2]={-10000, -10000};
    for(int i=0; i<N; i++)
    {
        int mi=(m[1]<m[0]);
        int v; cin >> v;
        m[mi]=(m[mi]<v)? v: m[mi];
    }
    cout << m[0]*m[1];
    return 0;
}

Проверил на компьютере у себя, всё нормально работает. Программа эффективна, потому что не заносит все числа в массив, а считает всё по мере ввода чисел. Если не найдёте ошибку в алгоритме, пойду на апелляцию. То ли я неправильно понял условие задачи (тут вы мне конечно не поможете), то ли проверяющим не понравился смайлик (m[1]<m[0]), то ли они не проверили мой дополнительный бланк ответов, на котором была написана вторая половина решения.

Обновление

У меня тут другие подозрения появились. Возможно, что мой код вообще не проверяли, потому что организаторша в ППЭ неправильно номер дополнительного бланка написала и жирно исправила цифру 7 на 3. Возможно, что компьютер принял эту цифру за 8 и из-за этого проверили только часть задания на первом бланке, где написан алгоритм программы на русском языке. Это подтверждается тем, что в критериях оценки написано, что один балл ставится, если "по приведённому тексту решения ясно, что экзаменуемый понимает, из каких этапов должно состоять решение задачи". Только факт того, что я скачал в Интернете все свои бланки, этому противоречит.

Обновление 2

Всё, нашёл ошибку (см. мой ответ). Всё прояснилось, на апелляцию не пойду.

northerner

Алгоритм очень плохой. Реально плохой. Как раз на 1 балл. И да, я эксперт ЕГЭ.

А так лучше?

#include <iostream>
using namespace std;

int main()
{
    int N; cin >> N;
    int m[2]={-10000, -10000};
    int n[2]={10000, 10000};
    for(int i=0; i<N; i++)
    {
        int mi=(m[1]<m[0]), ni=(n[1]>n[0]);
        int v; cin >> v;
        if(m[mi]<v) m[mi]=v;
        if(n[ni]>v) n[ni]=v;
    }
    cout << max(m[0]*m[1], n[0]*n[1]);
    return 0;
}

Answer 1

• Мне кажется, что если бы вы написали бы программу, аналогичную вашей, но не занимаясь Code golf'ом, то получили бы 4/4 (если, конечно, условия типа N >= 2 действительно фигурируют в задании). Потенциально еще можно было проверить input на корректность.

#include <iostream>
#include <cassert>
int main(int argc, char* argv[])
{
    static const int MIN_VALUE = -10000;
    static const int MAX_VALUE = 10000;
int n;
std::cin &gt;&gt; n;
assert(n &gt;= 2);

int firstMaximum = MIN_VALUE;
int secondMaximum = MIN_VALUE;
for (int i = 0; i &lt; n; ++i)
{
    int velocity;
    std::cin &gt;&gt; velocity;
    assert(velocity &gt;= MIN_VALUE &amp;&amp;
           velocity &lt;= MAX_VALUE);

    if (velocity &gt; firstMaximum)
    {
        secondMaximum = firstMaximum;
        firstMaximum = velocity;
    }
    else if (velocity &gt; secondMaximum)
    {
        secondMaximum = velocity;
    }
}

std::cout &lt;&lt; firstMaximum * secondMaximum;
return 0;

}

Answer 2

Кое-что узнал в Интернете. Оказывается, я не учёл того, что произведение двух больших по модулю отрицательных чисел может быть больше, чем положительных, а по условию надо было указать именно наибольшее произведение, а не произведение наибольших чисел. Вот блин...

Answer 3

Автор неверно написал в теме условие задачи, необходимо найти максимальное из произведений всех пар скоростей, а не произведение двух наибольших скоростей. В критериях выставления одного балла четко написано:

Предложен лишь частично верный алгоритм решения: в программе ищутся значения только максимальных элементов.

Здесь пошла нездоровая дискуссия о том, что, мол, школьные учителя ничего не понимают в программировании, поэтому работу зарезали. Так вот, я к тому, что в данном случае всё совершенно не так, один балл выставлен справедливо.

Answer 4

@Котик, mi=(m[1]<m[0]) это правильно (по хакерски).

Использование граничных значений для алгоритма - вполне в духе, скажем, Д. Кнута.

А вот к N < 2 действительно можно придраться. Но если не придираться, то IMHO super. Я бы пошел на апелляцию.

Answer 5

вполне вероятно, что во время написания ЕГЭ, вы упустили какую-то важную деталь, которую сочли незначительной. а так как вы воспроизвели задачу по памяти, вероятность того что вы упустили ее при репродукции еще выше...

любые рассмотрения кода не имеют смысла пока не будет представлено точное ТЗ

Answer 6

Алгоритм оч. хороший. Реально хороший. Особенно нравится выражение mi=(m[1]<m[0]) - это заслуживает отдельной похвалы за кодирование полузабытом штиле Кернигана-Ритчи. Надо идти на апелляцию.

Update

@Northener писал:

Автор неверно написал в теме условие задачи, необходимо найти максимальное из произведений всех пар скоростей, а не произведение двух наибольших скоростей.

Это конечно меняет все. В этом случае алгоритм работает неверно, увы. Но автор все равно молодец - я получил эстетическое удовольствие от предложенного алгоритма.

Answer 7

Что то я не видел, что бы кто то писал о отрицательных скоростях. Если оставить в стороне то, что нужен ещё вектор направления, то отрицательная скорость - это просто движения в противоположную сторону. В исходном коде бы исправил начальные значения на int m[2]={0, 0}; и при вводе скорость брал бы по модулю.

Но вот выражение mi=(m[1]<m[0]) на ЕГЭ я бы не писал. При собеседовании - можно (а иногда даже нужно), на ЕГЭ - не стоит.

Answer 8

Не разделяю восторгов по поводу хакерски-керниганского кода.

int mi=(m[1]<m[0])

Подумайте, какой тип данных возвращает rvalue и какой тип вы объявляете для lvalue, учитывая, что речь идёт о крестах, а не о труси бородатых времен Ритчи.

Какие могут быть ответы, если в программировании результатов - миллионы?

О правильных (проверенных вручную!) ответах на определенный тестовый набор данных. Знаете, как работают юнит-тесты?

В целом, как уже отметили предыдущие ораторы, не помня точного задания бессмысленно оценивать правильность реализации, и остается только оценивать стиль, который, как уже тоже отметили, возможно, хорош для codegolf'а, но не для прочтения человеком, тем более настроенным критически и от которого зависит оценка работы.