Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
#1

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

16.08.2012, 06:27. Просмотров 820. Ответов 11
Метки нет (Все метки)

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

Исходные данные
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//структура дроби
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++
1
2
3
4
5
6
7
8
9
//объявление переменной-знака
    char _sign;
 
    //Считываем первую дробь
    _oneFract = ReadFractional();
    //Считываем знак
    scanf("%c", &_sign);
    //Считываем вторую дробь
    _twoFract = ReadFractional();
Код, отвечающий за вывод результата

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.08.2012, 06:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Олимпиадная задача. Не могу найти ошибку (C++):

Задача из Златопольского: "Найти числа с известным количеством делителей". Не могу найти ошибку - C++
Здравствуйте. Задача следующая: Найти все целые числа из промежутка от a до b, у которых количество делителей равно k. К примеру я взял...

Не могу понять ошибку "C2043: недопустимый break". Задача: найти подстроку в строке - C++
#include <iostream> #include <fstream> #include <string> #include <stdio.h> #include <conio.h> using namespace std; int...

Никак не могу исправить ошибку, задача на функции - C++
Суть задачи. С помощью рекурсивной функции, не возвращающей значение, замените в данной строке все слова, начинающиеся с заглавной буквы,...

Олимпиадная задача - C++
Вот наткнулся сегодня на такую задачу: Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда...

Олимпиадная задача - C++
Был в прошлом году на олимпиаде по программированию и там была такая задача: После запуска программы пользователь должен начать...

Олимпиадная задача - C++
#include <cstdio> #include <cstdlib> #include <iostream> using namespace std; int main() { unsigned int N; cout<<"N=";...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
cmath
Модератор
2433 / 1657 / 133
Регистрация: 11.08.2012
Сообщений: 3,299
Завершенные тесты: 5
16.08.2012, 07:30 #2
А полный код можно?
0
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
16.08.2012, 07:36  [ТС] #3
Да, без проблем
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#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;
}
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.08.2012, 09:03 #4
Цитата Сообщение от Roukff Посмотреть сообщение
но сервер, на котором идет проверка, говорит, мол ответ неправильный на первом же тесте.
убирайте или закоментируйте перед отправкой строку:
Цитата Сообщение от Roukff Посмотреть сообщение
#include "stdafx.h"
, если отправляете не сам код, а файл (сервер просит указать путь и имя отправляемого на проверку файла), то после того, как убрали данную строку (или закоментировали) не забудьте в компиляторе нажать значек "сохранить".

И на всякий случай (есть и такие проверочные системы), в конце вывода результата сделайте перевод на новую строку:
C
1
printf("\n");
0
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.08.2012, 09:14 #5
Roukff, а может и правда стоит считать построчно. valeriikozlov, как раз тому свидетель, на одном автоматизированном сайте никак не мог понять почему в самой простейшей программе выдаёт ошибки, оказалось у них в тестах на некоторых линиях есть какие-то данные, не относящиеся к задаче
0
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
16.08.2012, 09:32  [ТС] #6
stdafx.h я убираю. Попробовал в конце вывода поставить \n. - безрезультатно
А насчет построчного ввода. Подскажите мне, как считать тогда правильно, т.к. у меня не получается.
при считывании дроби может отсутствовать какая-либо часть: либо дробная либо целая...
Обычной строкой
C++
1
scanf("%lld%lld/%lld",one,two,three)
не получается, т.к. ожидает, когда я введу остальные переменные.
Если считывать в строку, то как ее потом грамотно разобрать?
RegExp'ом наврядли получится, птмчт, чтобы его подключить, надо скачивать доп.файлы или я неправ?
Вобщем, подскажите, как тогда грамотно считать эту дробь?
0
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.08.2012, 09:39 #7
Можно попробовать функцией fgets() или C++ функцией std::getline()
Либо тупо считывать по одному символу пока не попадется нужный нам '\n' и после него считывать следующую строку
0
cmath
Модератор
2433 / 1657 / 133
Регистрация: 11.08.2012
Сообщений: 3,299
Завершенные тесты: 5
16.08.2012, 10:16 #8
Несколько придирок к коду:
1.Почему программа не выдает ошибку для нулевого знаменателя, а приравнивает его к нулю?
2.Почему в программе нет кода, выводящего информацию о вводе дробей и знака операции (формат ввода)? Пользователь не должен эту информацию угадывать.
3.Функция ввода неправильно работает в случае разделяющего знака ' '.
4.Нет кода обрабатывающего ошибки ввода (интересные результаты получаются, особенно в сумме с п.2)
5.Присутствует лишний код (на самом деле находить НОК не нужно, НОД'а вполне хватает)
6.Переносить целую часть в числитель нет смысла (гораздо проще и быстрее представить дробь как целая часть + дробная).
7.Функция нахождения модуля также не нужна (кроме того есть места в коде где для нахождения модуля вы ей не пользуетесь)
8.Не важно: функция main() слишком большая. Попробуйте вынести все вычисления, за исключением элементарных (2+2), в отдельные функции, иначе код тяжело воспринимать, что не есть хорошо. Если будете писать что-то крупнее, сами в своем же коде запутаетесь.

p.s. попробую накидать свой вариант (с учетом выше изложенного) может пригодиться.
0
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
16.08.2012, 10:40  [ТС] #9
1. Это я уже просто для уверенности сделал, затем это уберется. Просто в задаче говорится, что ввод корректен и знаменатель нулю не может быть равен.
2. Этот код проверяется автоматом, поэтому там лучше вообще ничего лишнего не выводить
3. А почему не корректно? Объясните пожалуйста
4. он и не нужен, иначе проверящая система выдаст ошибку
5. Это да, лишний код присутствует =) Но вначале надо сделать, чтобы работало, а уже потом оптимизировать
6. а умножать дробь на дробь как будете? мб я забыл что-то о дробях, но вроде целую часть надо в числитель
7. Нет, она как раз таки нужна, т.к. неизвестно, с каким знаком нам подается целая часть и она должна быть положительной
8. Да, это тоже верно, но как я сказал выше, вначале надо сделать, чтоб работало
0
cmath
Модератор
2433 / 1657 / 133
Регистрация: 11.08.2012
Сообщений: 3,299
Завершенные тесты: 5
16.08.2012, 16:08 #10
На счет ошибки:
Виноват, извиняюсь. Ошибки на самом деле нет. Лишний символ случайно поставил когда занимался отладкой вашего кода. Убрал. Ошибка пропала.
На счет дробей:
Можно перемножать как (ц часть + дробная)*(ц часть + дробная). Надо просто скобки раскрыть.
Что я и сделал. (см. проект).
На счет автомата: Наверное в нем самом ошибка. Сегодня частенько такое встречается.
Если я правильно понял, то он должен
а) либо ввести свои данные в вашу программу и считать результат, затем его проверить (если посылал файл)
б) либо скомпилировать ваш код и все равно проделать пред. пункт
Непонимаю только: как в автомате могут быть какие-то сторонние данные? Он несколько разнотипных задач проверяет??? Какой нормальный человек будет добавлять в программу данные, которые никак не относятся к поставленной для неё цели????
На счет 4 пункта не согласен:
если ваша программа работает без ошибок, то автомат этот не заметит действие кода, обрабатывающего ошибки, в противном случае автомат вас все равно пошлет куда по-дальше, а вы, по крайней мере, будете знать "где собака зарыта".
На счет 7 пункта:
см мою прогу она работает нормально, я ее уже раз 50 протестил (где-то 30 пока отладкой занимался)
я обошелся без всяких модулей.

P. S. Там ввод немного не доработан, но в сообщении, появляющемся после старта программы указано как дроби вводить(от КЭПа ) в остальном все нормально.
0
Вложения
Тип файла: rar Дроби.rar (2.80 Мб, 3 просмотров)
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
16.08.2012, 22:39 #11
C++
1
fflush(stdin);
Это по стандарту undefined behaviour. И даже если оно будет пропускать всё - зачем?! Если stdin - это файл, то получается, что всё после первой дроби - игнорируется?
0
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
16.08.2012, 23:58  [ТС] #12
Ура! В соседней ветке мне подсказали, как можно считать ввод: я пропарсил строку и все.
делал я это так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
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;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.08.2012, 23:58
Привет! Вот еще темы с ответами:

Олимпиадная задача - C++
Дошел до этой олимпиадной задачи и впал в ступор. Нагуглил, что можно решить с помощью матриц, либо с помощью графов, но какого-то...

Задача на дп (олимпиадная) - C++
Здравствуйте, имеется данная задача, основная проблема состоит в том, что мое решение никак не проходит по времени. Пробовал писать через...

C++. Олимпиадная задача - C++
Здравствуйте! Код не проходит какой-то тест, может алгоритм не правильный. И если не правильный, то как исправить? Помогите найти ошибку....

Олимпиадная задача - C++
Есть такая задачка: В ряд выписаны числа, состоящие только из цифр 1, 3, 7: 1, 3, 7, 11, 13, 17, ... Необходимо по номеру N определить...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
16.08.2012, 23:58
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru