Олимпиадная задача. Не могу найти ошибку

@Roukff · Регистрация: 05.06.2011

Author24 — интернет-сервис помощи студентам

Привет всем! Решил порешать олимпиадные задачи и столкнулся с проблемой: Написанный мной код правильно решает поставленную задачу, но сервер, на котором идет проверка, говорит, мол ответ неправильный на первом же тесте. Это вызвало большие подозрения. Все перепроверил, вроде все правильно. Начал подозревать, что возможно вывод неправильный. Но, вроде бы, тоже все верно. Не могу никак найти ошибку. Цитирую, как надо вводить информацию.

Исходные данные
The first line – a fraction (the first operand);
The second line – the sign of an operation;
The third line – a fraction (the second operand).
Both fractions may be reducible. The numerator is always less than the denominator.

Результат
A single line that contains an irreducible proper fraction (result) in the format described above.

Пример

исходные данные
-3 1/6
+
2/4
результат
-2 2/3

Примеры дробей
Samples of fractional number representation: “-7 3/4”, “8 1/2”, “-7/11”, “0”, “11”.

Код, отвечающий за ввод:

C++

//структура дроби
struct Fractional
{
    //объявление целой части, числителя и знаменателя
    long long intPart, numerator, denomerator;
} _oneFract, _twoFract, _result;
 
//функция считывания дроби
Fractional ReadFractional()
{
    Fractional _fract;
    //переменная _razdel определяет, что ввели: только целую часть, только дробную часть или целую и дробную часть
    char _razdel;
    //считываем первое число
    scanf("%lld",&_fract.intPart);
    //считываем разделитель после первой цифры: если нажат Enter, то число без дробной части, 
    //если слеш, то только дробная часть, если пробел то и целая и дробная части присутствуют
    scanf("%c", &_razdel);
    if (_razdel == '\n')
    {
        _fract.numerator = 0;
        _fract.denomerator = 1;
    }
    else if (_razdel == ' ')
    {
        //Считываем дробную часть
        scanf("%lld/%lld%*c", &_fract.numerator, &_fract.denomerator);
        if (_fract.denomerator == 0)
            _fract.denomerator = 1;
    }
    else if (_razdel == '/')
    {
        //Считываем знаменатель
        scanf("%lld%*c", &_fract.denomerator);
        if (_fract.denomerator == 0)
            _fract.denomerator = 1;
        _fract.numerator = _fract.intPart;
        _fract.intPart = 0;
    }
    //Сбрасываем входной поток
    fflush(stdin);
    return _fract;
}

Вызов этой функции:

C++

//объявление переменной-знака
    char _sign;
 
    //Считываем первую дробь
    _oneFract = ReadFractional();
    //Считываем знак
    scanf("%c", &_sign);
    //Считываем вторую дробь
    _twoFract = ReadFractional();

Код, отвечающий за вывод результата

C++

if (_result.intPart == 0)
    {
        if (_result.numerator == 0)
        {
            printf("0");
        }
        else
        {
            printf("%lld/%lld", _result.numerator, _result.denomerator);
        }
    }
    else if (_result.numerator == 0)
    {
        printf("%lld",_result.intPart);
    }
    else
    {
        printf("%lld %lld/%lld",_result.intPart, _result.numerator, _result.denomerator);
    }

Также нашел на форуме еще одного человека с похожей проблемой, только он ввод делал через getline(). Вот что он пишет, мб это пригодится для выяснения причины
Strange...I had taken input through getline and removed last character if it was null or end of line. And I was getting wrong answer. But when I changed it to the condition, that remove last character if it is not from 0 to 9, it got AC.
Can anybody explain why?

@cmath · 16.08.2012, 07:30

А полный код можно?

@Roukff · 16.08.2012, 07:36 **[ТС]**

Да, без проблем

C++

#include "stdafx.h"
#include <stdio.h>
 
int ABS(int a)
{
    if (a < 0)
        return -a;
    else
        return a;
}
 
//структура дроби
struct Fractional
{
    //объявление целой части, числителя и знаменателя
    long long intPart, numerator, denomerator;
} _oneFract, _twoFract, _result;
 
//функция считывания дроби
Fractional ReadFractional()
{
    Fractional _fract;
    //переменная _razdel определяет, что ввели: только целую часть, только дробную часть или целую и дробную часть
    char _razdel;
    //считываем первое число
    scanf("%lld",&_fract.intPart);
    //считываем разделитель после первой цифры: если нажат Enter, то число без дробной части, 
    //если слеш, то только дробная часть, если пробел то и целая и дробная части присутствуют
    scanf("%c", &_razdel);
    if (_razdel == '\n')
    {
        _fract.numerator = 0;
        _fract.denomerator = 1;
    }
    else if (_razdel == ' ')
    {
        //Считываем дробную часть
        scanf("%lld/%lld%*c", &_fract.numerator, &_fract.denomerator);
        if (_fract.denomerator == 0)
            _fract.denomerator = 1;
    }
    else if (_razdel == '/')
    {
        //Считываем знаменатель
        scanf("%lld%*c", &_fract.denomerator);
        if (_fract.denomerator == 0)
            _fract.denomerator = 1;
        _fract.numerator = _fract.intPart;
        _fract.intPart = 0;
    }
    //Сбрасываем входной поток
    fflush(stdin);
    return _fract;
}
 
//Функция нахождение наименьшего общего делителя (НОД)
int NOD(int a, int b)
{
    while ((a != 0) && (b != 0))
    {
        (a >= b) ? (a %= b) : (b %= a);
    }
    if (a != 0)
        return a;
    else
        return b;
    //(a != 0) ? (return a) : (return b);
}
 
int main()
{
    //объявление переменной-знака
    char _sign;
 
    //Считываем первую дробь
    _oneFract = ReadFractional();
    //Считываем знак
    scanf("%c", &_sign);
    //Считываем вторую дробь
    _twoFract = ReadFractional();
    
    //НОК
    int _nok = 1;
    if ((_sign == '+') || (_sign == '-'))
    {
        //находим наименьшее общее кратное
        _nok = _oneFract.denomerator * _twoFract.denomerator / NOD(_oneFract.denomerator, _twoFract.denomerator);
        //Умножаем числитель одной дроби на знаменатель другой
        _oneFract.numerator *= _nok / _oneFract.denomerator;
        _twoFract.numerator *= _nok / _twoFract.denomerator;
        //переносим целую часть в числитель
        _oneFract.numerator += _nok * ABS(_oneFract.intPart);
        if (_oneFract.intPart < 0)
        {
            _oneFract.numerator = -_oneFract.numerator;
        }
        _twoFract.numerator += _nok * ABS(_twoFract.intPart);
        if (_twoFract.intPart < 0)
        {
            _twoFract.numerator = -_twoFract.numerator;
        }
    }
    else
    {
        //переносим целую часть в числитель
        _oneFract.numerator += _oneFract.denomerator * ABS(_oneFract.intPart);
        if (_oneFract.intPart < 0)
        {
            _oneFract.numerator = -_oneFract.numerator;
        }
        _twoFract.numerator += _twoFract.denomerator * ABS(_twoFract.intPart);
        if (_twoFract.intPart < 0)
        {
            _twoFract.numerator = -_twoFract.numerator;
        }
    }
        switch (_sign)
        {
            case '+': 
                _result.numerator = _oneFract.numerator + _twoFract.numerator;
                _result.denomerator = _nok;
                break;
            case '-': 
                _result.numerator = _oneFract.numerator - _twoFract.numerator;
                _result.denomerator = _nok; 
                break;
            case '*': 
                _result.numerator = _oneFract.numerator * _twoFract.numerator;
                _result.denomerator = _oneFract.denomerator * _twoFract.denomerator; 
                break;
            case '/': 
                _result.numerator = _oneFract.numerator * _twoFract.denomerator;
                _result.denomerator = _oneFract.denomerator * _twoFract.numerator;
                if (_result.denomerator < 0)
                {
                    _result.numerator = -_result.numerator;
                    _result.denomerator = -_result.denomerator;
                }
                break;
        }
        if (_result.denomerator == 0)
        {
            _result.denomerator = 1;
        }
        //Находим целую часть
        _result.intPart = _result.numerator / _result.denomerator;
        //находим числитель
        _result.numerator %= _result.denomerator;
        if (_result.intPart < 0)
        {
            _result.numerator = ABS(_result.numerator);
            _result.denomerator = ABS(_result.denomerator);
        }
        //Сокращаем дробь
        _nok = _result.denomerator;
        _result.denomerator /= NOD(ABS(_result.numerator), _nok);
        _result.numerator /= NOD(ABS(_result.numerator), _nok);
    //}
 
    if (_result.intPart == 0)
    {
        if (_result.numerator == 0)
        {
            printf("0");
        }
        else
        {
            printf("%lld/%lld", _result.numerator, _result.denomerator);
        }
    }
    else if (_result.numerator == 0)
    {
        printf("%lld",_result.intPart);
    }
    else
    {
        printf("%lld %lld/%lld",_result.intPart, _result.numerator, _result.denomerator);
    }
    return 0;
}

valeriikozlov · 16.08.2012, 09:03

Сообщение от Roukff

но сервер, на котором идет проверка, говорит, мол ответ неправильный на первом же тесте.

убирайте или закоментируйте перед отправкой строку:

Сообщение от Roukff

#include "stdafx.h"

, если отправляете не сам код, а файл (сервер просит указать путь и имя отправляемого на проверку файла), то после того, как убрали данную строку (или закоментировали) не забудьте в компиляторе нажать значек "сохранить".

И на всякий случай (есть и такие проверочные системы), в конце вывода результата сделайте перевод на новую строку:

C

1	printf("\n");

@Buckstabue · 16.08.2012, 09:14

Roukff, а может и правда стоит считать построчно. valeriikozlov, как раз тому свидетель, на одном автоматизированном сайте никак не мог понять почему в самой простейшей программе выдаёт ошибки, оказалось у них в тестах на некоторых линиях есть какие-то данные, не относящиеся к задаче

@Roukff · 16.08.2012, 09:32 **[ТС]**

stdafx.h я убираю. Попробовал в конце вывода поставить \n. - безрезультатно
А насчет построчного ввода. Подскажите мне, как считать тогда правильно, т.к. у меня не получается.
при считывании дроби может отсутствовать какая-либо часть: либо дробная либо целая...
Обычной строкой

C++

1	scanf("%lld%lld/%lld",one,two,three)

не получается, т.к. ожидает, когда я введу остальные переменные.
Если считывать в строку, то как ее потом грамотно разобрать?
RegExp'ом наврядли получится, птмчт, чтобы его подключить, надо скачивать доп.файлы или я неправ?
Вобщем, подскажите, как тогда грамотно считать эту дробь?

@Buckstabue · 16.08.2012, 09:39

Можно попробовать функцией fgets() или C++ функцией std::getline()
Либо тупо считывать по одному символу пока не попадется нужный нам '\n' и после него считывать следующую строку

@cmath · 16.08.2012, 10:16

Несколько придирок к коду

:
1.Почему программа не выдает ошибку для нулевого знаменателя, а приравнивает его к нулю?
2.Почему в программе нет кода, выводящего информацию о вводе дробей и знака операции (формат ввода)? Пользователь не должен эту информацию угадывать.
3.Функция ввода неправильно работает в случае разделяющего знака ' '.
4.Нет кода обрабатывающего ошибки ввода (интересные результаты получаются, особенно в сумме с п.2)
5.Присутствует лишний код (на самом деле находить НОК не нужно, НОД'а вполне хватает)
6.Переносить целую часть в числитель нет смысла (гораздо проще и быстрее представить дробь как целая часть + дробная).
7.Функция нахождения модуля также не нужна (кроме того есть места в коде где для нахождения модуля вы ей не пользуетесь)
8.Не важно: функция main() слишком большая. Попробуйте вынести все вычисления, за исключением элементарных (2+2), в отдельные функции, иначе код тяжело воспринимать, что не есть хорошо. Если будете писать что-то крупнее, сами в своем же коде запутаетесь.

p.s. попробую накидать свой вариант (с учетом выше изложенного) может пригодиться.

@Roukff · 16.08.2012, 10:40 **[ТС]**

1. Это я уже просто для уверенности сделал, затем это уберется. Просто в задаче говорится, что ввод корректен и знаменатель нулю не может быть равен.
2. Этот код проверяется автоматом, поэтому там лучше вообще ничего лишнего не выводить
3. А почему не корректно? Объясните пожалуйста
4. он и не нужен, иначе проверящая система выдаст ошибку
5. Это да, лишний код присутствует =) Но вначале надо сделать, чтобы работало, а уже потом оптимизировать
6. а умножать дробь на дробь как будете? мб я забыл что-то о дробях, но вроде целую часть надо в числитель
7. Нет, она как раз таки нужна, т.к. неизвестно, с каким знаком нам подается целая часть и она должна быть положительной
8. Да, это тоже верно, но как я сказал выше, вначале надо сделать, чтоб работало

@cmath · 16.08.2012, 16:08

На счет ошибки:
Виноват, извиняюсь. Ошибки на самом деле нет. Лишний символ случайно поставил когда занимался отладкой вашего кода. Убрал. Ошибка пропала

.
На счет дробей:
Можно перемножать как (ц часть + дробная)*(ц часть + дробная). Надо просто скобки раскрыть.
Что я и сделал. (см. проект).
На счет автомата: Наверное в нем самом ошибка. Сегодня частенько такое встречается

.
Если я правильно понял, то он должен
а) либо ввести свои данные в вашу программу и считать результат, затем его проверить (если посылал файл)
б) либо скомпилировать ваш код и все равно проделать пред. пункт
Непонимаю только: как в автомате могут быть какие-то сторонние данные? Он несколько разнотипных задач проверяет??? Какой нормальный человек будет добавлять в программу данные, которые никак не относятся к поставленной для неё цели????

На счет 4 пункта не согласен:
если ваша программа работает без ошибок, то автомат этот не заметит действие кода, обрабатывающего ошибки, в противном случае автомат вас все равно пошлет куда по-дальше, а вы, по крайней мере, будете знать "где собака зарыта".
На счет 7 пункта:
см мою прогу она работает нормально, я ее уже раз 50 протестил (где-то 30 пока отладкой занимался

)
я обошелся без всяких модулей.

P. S. Там ввод немного не доработан, но в сообщении, появляющемся после старта программы указано как дроби вводить(от КЭПа

) в остальном все нормально.

@Somebody · 16.08.2012, 22:39

C++

1	fflush(stdin);

Это по стандарту undefined behaviour. И даже если оно будет пропускать всё - зачем?! Если stdin - это файл, то получается, что всё после первой дроби - игнорируется?

@Roukff · 16.08.2012, 23:58 **[ТС]**

Ура! В соседней ветке мне подсказали, как можно считать ввод: я пропарсил строку и все.
делал я это так:

C++

Fractional ReadFractional()
{
    Fractional _fract;
    char sInput[20];
    gets(sInput);
    switch (sscanf(sInput, "%lld%*c%lld/%lld", &_fract.intPart,&_fract.numerator, &_fract.denomerator))
    {
        case 1: _fract.numerator = 0; _fract.denomerator = 1; break;
        case 2: _fract.denomerator = _fract.numerator; _fract.numerator = _fract.intPart; _fract.intPart = 0; break;
    }
    return _fract;
}

@cmath 2525 / 1751 / 152 Регистрация: 11.08.2012 Сообщений: 3,349
	16.08.2012, 07:30	2
	А полный код можно? 0

@Buckstabue 179 / 127 / 25 Регистрация: 12.01.2012 Сообщений: 623
	16.08.2012, 09:14	5
	Roukff, а может и правда стоит считать построчно. valeriikozlov, как раз тому свидетель, на одном автоматизированном сайте никак не мог понять почему в самой простейшей программе выдаёт ошибки, оказалось у них в тестах на некоторых линиях есть какие-то данные, не относящиеся к задаче 0

@Buckstabue 179 / 127 / 25 Регистрация: 12.01.2012 Сообщений: 623
	16.08.2012, 09:39	7
	Можно попробовать функцией fgets() или C++ функцией std::getline() Либо тупо считывать по одному символу пока не попадется нужный нам '\n' и после него считывать следующую строку 0

@cmath 2525 / 1751 / 152 Регистрация: 11.08.2012 Сообщений: 3,349
	16.08.2012, 10:16	8
	Несколько придирок к коду: 1.Почему программа не выдает ошибку для нулевого знаменателя, а приравнивает его к нулю? 2.Почему в программе нет кода, выводящего информацию о вводе дробей и знака операции (формат ввода)? Пользователь не должен эту информацию угадывать. 3.Функция ввода неправильно работает в случае разделяющего знака ' '. 4.Нет кода обрабатывающего ошибки ввода (интересные результаты получаются, особенно в сумме с п.2) 5.Присутствует лишний код (на самом деле находить НОК не нужно, НОД'а вполне хватает) 6.Переносить целую часть в числитель нет смысла (гораздо проще и быстрее представить дробь как целая часть + дробная). 7.Функция нахождения модуля также не нужна (кроме того есть места в коде где для нахождения модуля вы ей не пользуетесь) 8.Не важно: функция main() слишком большая. Попробуйте вынести все вычисления, за исключением элементарных (2+2), в отдельные функции, иначе код тяжело воспринимать, что не есть хорошо. Если будете писать что-то крупнее, сами в своем же коде запутаетесь. p.s. попробую накидать свой вариант (с учетом выше изложенного) может пригодиться. 0

@Roukff 1 / 1 / 1 Регистрация: 05.06.2011 Сообщений: 35
	16.08.2012, 10:40 [ТС]	9
	1. Это я уже просто для уверенности сделал, затем это уберется. Просто в задаче говорится, что ввод корректен и знаменатель нулю не может быть равен. 2. Этот код проверяется автоматом, поэтому там лучше вообще ничего лишнего не выводить 3. А почему не корректно? Объясните пожалуйста 4. он и не нужен, иначе проверящая система выдаст ошибку 5. Это да, лишний код присутствует =) Но вначале надо сделать, чтобы работало, а уже потом оптимизировать 6. а умножать дробь на дробь как будете? мб я забыл что-то о дробях, но вроде целую часть надо в числитель 7. Нет, она как раз таки нужна, т.к. неизвестно, с каким знаком нам подается целая часть и она должна быть положительной 8. Да, это тоже верно, но как я сказал выше, вначале надо сделать, чтоб работало 0