23

Я писал ЕГЭ по информатике, сегодня стали известны результаты. Почему-то в 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;
}
10
  • 2
    На первый взгляд, если вход нормальный и N > 1, то правильно. Может быть следовало рассмотреть варианты с N < 2 ?
    – avp
    7 июн 2012 в 11:34
  • Проверяет вероятней всего какаето тетя Таня, которая в программировании вообще нечего не шарит, у нее есть листочек с ответом, там через while написано, буквы не совпадают, бабла для нее в конверте нету, отсюда вместо 4х - 1
    – Gorets
    7 июн 2012 в 11:36
  • Видимо не совпало с ответами :) По-моему всё правильно, если не учитывать лишнего присваивания m[mi] самому себе в случае, если пришло не большее число.
    – sercxjo
    7 июн 2012 в 11:38
  • 2
    Отличный код, создатели ЕГЭ на такое не расчитывали видимо.
    – margosh
    7 июн 2012 в 12:12
  • 2
    @sercxjo, если Вы по поводу конкретного кода m[mi]=(m[mi]<v)? v: m[mi]; вместо if (m[mi]<v) m[mi] = v; то Вы правы, а я погорячился. Вариант с if лучше.
    – avp
    7 июн 2012 в 12:24

8 ответов 8

11

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

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

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

8
  • 2
    >Здесь пошла нездоровая дискуссия о том, что, мол, школьные учителя ничего не понимают в программировании Вообще-то, в школе у меня в школе такой учитель и был. В диагностических работах только части A и B с ответами сверял, а C даже не смотрел. Дал спецификацию и сказал проверять самостоятельно. Правда на то, чтобы стать экспертом он и не претендовал.
    – devoln
    7 июн 2012 в 19:12
  • Это правда, так бывает. Экспертная комиссия ЕГЭ формируется 50 на 50 из школьных учителей и преподавателей ВУЗов. Интересно, как ваш учитель поступил с последней тренировочной статградовской работы, где правильные ответы были перемешаны между вариантами. На вопрос @avp (там кончился лимит комментариев): зависит от контекста, решая задачку на олимпиадном сервере, я бы как-то так и сам написал, в серьезном проекте избегал бы подобного и другим членам команды не рекомендовал бы.
    – northerner
    8 июн 2012 в 6:39
  • 1
    М... А разьве произведение двух наибольших скоростей не равно максимальному произведению их всех пар скоростей? 8 июн 2012 в 7:11
  • @oleg_ismaylov -10000 * -10000 8 июн 2012 в 7:32
  • 1
    @oleg_ismaylov - Проекции векторов еще никто не отменял. - Если вы действительно хотите продолжить этот разговор, то скорость как векторная величина не может быть и положительной, поскольку в данном контексте имеет смысл только положительность / отрицательность какой-либо R1 метрики, введенной для векторов. - И да, если уж говорить о скорости как о векторной величине, то как в контексте данной задачи вы представляете себе произведение скоростей? 8 июн 2012 в 7:46
11
  • Мне кажется, что если бы вы написали бы программу, аналогичную вашей, но не занимаясь 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 >> n;
    assert(n >= 2);

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

        if (velocity > firstMaximum)
        {
            secondMaximum = firstMaximum;
            firstMaximum = velocity;
        }
        else if (velocity > secondMaximum)
        {
            secondMaximum = velocity;
        }
    }

    std::cout << firstMaximum * secondMaximum;
    return 0;
}
7
  • >но не занимаясь Code golf'ом Для меня та конструкция привычна, я ей пользуюсь давно, и не вижу в ней ничего сложного. На то, чтобы её придумать и написать у меня уходит меньше времени, чем написание этих больших if'ов.
    – devoln
    7 июн 2012 в 13:08
  • 7
    @GLmonster Только вы забываете, что пишете код не для себя, а для других людей :) 7 июн 2012 в 13:10
  • Ну что тут сказать. Грамотная, понятная, эффективная, легко модифицируемая ... Просто образец для разных экзаменов.
    – avp
    7 июн 2012 в 13:17
  • @Котик люто бешено плюсую на счет кода для других. В идеале было чтобы весь код был понятен тому кому его могут передать. Иногда бывает слишком много времени уходит на понимание, и уже что-то добавить свое страшно становится
    – misha_m
    7 июн 2012 в 13:51
  • 1
    @GLMonster никто её тут сложной не считает. Только тут у вас 3 строки. А представляете когда такого кода хотя бы 1000 строк. А тех кто проверяет ЕГЭ, мы увы знать не можем (проверял бы кто-то из нас, скорее всего 4/4 получили бы :) )
    – misha_m
    7 июн 2012 в 13:55
11

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

11
  • ну так, это все проясняет:)
    – KoVadim
    7 июн 2012 в 14:10
  • Жаль, столько обсуждали, а программа решает не ту задачку...
    – avp
    7 июн 2012 в 14:16
  • 1
    Но не один же балл! В критериях к задаче C4 (правда другой) написано: "Три балла также выставляется, если в эффективной программе, удовлетворяющей критериям выставления 4 баллов, есть одна ошибка, в результате которой программа работает неверно на некоторых наборах нетипичных входных данных". >Жаль, столько обсуждали, а программа решает не ту задачку... А мне-то как жаль... Даже не знаю, идти ли на апелляцию теперь. Ладно, пойду всё равно, наверное.
    – devoln
    7 июн 2012 в 14:21
  • 2
    по-моему это стоит указать в тексте вопроса
    – Spectre
    7 июн 2012 в 14:31
  • 2
    Нет, здесь очевидно один балл. Один в один по критериям. Я на самом деле сочувствую автору, потому что в этом году каждый первичный балл C4 стоит трёх баллов в стобалльной шкале, следовательно, теряя 3 первичных балла теряешь сразу 9 - и это как-то слишком жестко, но, увы, ничего не попишешь.
    – northerner
    7 июн 2012 в 15:24
10

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

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

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

1
  • 6
    Не думаю, что кому-то нужно знаменитое "хакерство", KR-like способ закодировать что-то и т.д. на ЕГЭ. А вот написать код, который поймет тетя Таня и дядя Вася - это тоже искусство. Разумеется, на правах IMHO. 7 июн 2012 в 12:18
8

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

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

2
  • >вполне вероятно, что во время написания ЕГЭ, вы упустили какую-то важную деталь, которую сочли незначительной Я допускаю, что я мог неправильно понять условие, но его у меня нет. Поэтому я пытаюсь исключить по крайней мере всё остальное. Но исходный код точно такой же, я его переписал со скана листа работы. >любые рассмотрения кода не имеют смысла пока не будет представлено точное ТЗ К сожалению, не будет. Ладно, на апелляции узнаю.
    – devoln
    7 июн 2012 в 13:00
  • 2
    @GLmonster, попробуйте поискать в нете схожие задания - говорят, некоторые варианты задач можно найти, может и Ваша среди них встретится
    – margosh
    7 июн 2012 в 13:09
7

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

Update

@Northener писал:

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

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

13
  • 3
    >Надо идти на апелляцию. Завтра пойду писать заявление.
    – devoln
    7 июн 2012 в 12:46
  • 4
    > Алгоритм оч. хороший. Реально хороший. Алгоритм очень плохой. Реальной плохой. Как раз на 1 балл. И да, я эксперт ЕГЭ.
    – northerner
    7 июн 2012 в 15:18
  • @northerner, объясните подробно. А то Вы оцениваете учеников, а мы им работу потом даем. Интересно несовпадение критериев.
    – avp
    7 июн 2012 в 15:27
  • 2
    @northerner А как при выставлении общего балла относятся к вещам типа mi=(m[1]<m[0])? 7 июн 2012 в 15:37
  • 1
    @Котик_хочет_кушать, используемые конструкции и стиль не играют роли. Хорошо это или плохо - другой вопрос, факт, что критерии явным образом определяют правила игры так. Другое дело - человеческий фактор. Эксперт может ошибиться. Правда для этого каждую работу и проверяют двое отдельно, при разнице в один балл ставится большая оценка, при большей разнице включается третий эксперт, и предусмотрена апелляция. Но все же рекомендую писать по-человечески - ниже вероятность срезать верное решение.
    – northerner
    7 июн 2012 в 15:49
5

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

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

16
  • 1
    а я не утверждаю, что оно возвратит только 0 или 1. В стандарте я такого утверждения не нашел. Поэтому на ЕГЭ и не стоит так делать. А вот на собеседовании, когда можем выбирать компилятор, можно и использовать, там объяснять проще будет.
    – KoVadim
    7 июн 2012 в 12:31
  • 3
    Классическая проблема - либо сразу пишем три строки и получаем хороший бал, либо пишем одну, потом ходим, доказываем. Как по мне - первое значительно эффективно. Так что топикстартер решил задачу не оптимально. выражение (m[1]<[m[0])? 1: 0 - более красивое. Но в целом, задача написана на с, а не на с++.
    – KoVadim
    7 июн 2012 в 12:36
  • 2
    @GLmonster - принципиального отличия между if и mi = (m[1]<[m[0]) нету, и там и там скорее всего сгенерируется код который вычтет одно число из другого и проверит флаги, только второй вариант сильно зависит от аппаратной части и версии и настроек компилятора, не предвнося понимания кода, тогда как вариант с if даст более простой для понимания код, без потери качества генерируемого выполняемого кода.
    – Чад
    7 июн 2012 в 12:46
  • 2
    @KoVadim, я нашел такие входные данные, когда код не решает поставленную задачу Проверил на Вашем примере, а также, когда все числа равны - нет все работает (программа правильная).
    – avp
    7 июн 2012 в 13:06
  • 3
    @KoVadim Нулевая скорость больше, чем отрицательная. Если, конечно, в задаче не фигурировал модуль. 7 июн 2012 в 13:24
5

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

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

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

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

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

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

12
  • 2
    >Подумайте, какой тип данных возвращает rvalue и какой тип вы объявляете для lvalue Судя по всему, bool, который конвертируется в int. >Далее, кстати, у вас потенциальный выход за пределы массива. true - 1, false - 0. Разве может быть по-другому? >речь идёт о крестах, а не о труси бородатых времен Ритчи. А как же обратная совместимость? Разве даже в таких мелочах не сохраняется обратная совместимость?
    – devoln
    7 июн 2012 в 15:09
  • 1
    @karmadro4, в g++ код работает. Самое главное, автор продемонстрировал нетривиальный подход к поиску 2-х максимальных элементов, т.е. творческое мышление, а также способность писать компактный код в условиях дефицита времени (экзамен). @GLmonster, очень интересно, а сколько программок надо было написать и за какое время ? -- В данных условиях - это 5+. Другой вопрос, если код решает не ту задачу. Тогда из автоматизированных тестов пройдет только компиляция и исполнение с кодом возврата 0.
    – avp
    7 июн 2012 в 15:10
  • 2
    @GLmonster Программировать на C++, исходя из обратной совместимости с C - это самое страшное, что только можно предпринять. Отсюда и рождаются грабли с миллионами new / delete в коде, вещи типа operator bool, отсюда растут ноги у использования int для хранения значения булевского выражения и C-style касты, ломающие использование vfptr и vcbl. Если уж взялись писать на C++, то используйте bool для хранения булевского значения. 7 июн 2012 в 15:23
  • 1
    @GLmonster - Утверждение про implementation-specific bool, судя по всему, некорректно, либо я неправильно интерпретирую пункт [4.7 - Integral Conversions][1] стандарта C++. > If the source type is bool, the value false is converted to zero and the value true is converted to one. [1]: open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf#page=98 7 июн 2012 в 18:14
  • 1
    @karmadro4 Я вообще недавно был шокирован тем, что у меня вот [эта вот страница][1] попала в топ16 вкладок хрома :) [1]: hashcode.ru/users/6679/karmadro4/recent 7 июн 2012 в 20:19

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.