Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
0 / 0 / 0
Регистрация: 12.05.2018
Сообщений: 54
1

Программа не проходит все тесты на тестовой системе

04.10.2019, 21:10. Показов 709. Ответов 9
Метки нет (Все метки)

Дано число K. Дальше следуют K блоков. В каждом блоке есть 4 числа a,b и c,d . Числа натуральные и не превосходят 10^18. Для каждого блока входных данных нужно вывести "YES" , если в процессе применения алгоритма Евклида к паре (a,b) в какой-то момент получится пара (c,d). Иначе вывести NO

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
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
bool checker_evk(long a,long b,long c,long d) {
if ( a== c && b==d) return true;
while(a!=b) {
    if (a>b) a-=b; else b-=a;
 if (a==c && b==d ) return true;
}
return false;
}
int main(){
    ifstream cin("input.txt");
    ofstream cout("output.txt");
long  k,c,d;
cin>>k;
vector < long> a;
for(int i = 0;i < k*2 ;i++) {
    cin >>c >> d;
  a.push_back(c);
 a.push_back(d);
}
int i=0;
while(i<a.size()-1) {
    if  (checker_evk(a[i],a[i+1],a[i+2],a[i+3])) cout<<"YES"<<endl; else cout<<"NO"<<endl;
    i+=4;
}
return 0;
}
Например
INPUT::
2
20 10
10 10
10 7
2 4
OUTPUT::
YES
NO
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.10.2019, 21:10
Ответы с готовыми решениями:

Программа не проходит тесты
Здравствуйте, решаю задачу: Имеется список людей с указанием их фамилии, имени и даты рождения....

Программа с процедурами не проходит тесты
Добрый день Пишу сюда, так как не могу найти ошибку самостоятельно. Код программы с...

Программа не проходит определённые тесты
Вот такой вот вышел код для данной задачи но он почему-то не проходит выше второй группы хотя если...

Программа не проходит некоторые тесты
Доброго времени суток, друзья! Решаю задачу: вывод стандартный вывод Дана строка, состоящая...

9
Мозгоправ
1729 / 1023 / 468
Регистрация: 01.10.2018
Сообщений: 2,136
Записей в блоге: 2
05.10.2019, 02:10 2
Попробуйте так:
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
#include <iostream>
#include <fstream>
 
using namespace std;
 
bool checker_evk(long a, long b, long c, long d) {
    if ((a == c && b == d) || ((a == d && b == c))) return true;
    while (a != b) {
        if (a > b) a -= b; else b -= a;
        if ((a == c && b == d) || ((a == d && b == c))) return true;
    }
    return false;
}
 
int main() {
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    long  k, a, b, c, d;
    cin >> k;
    for (long i = 0; i < k; ++i) {
        cin >> a >> b >> c >> d;
        if (checker_evk(a, b, c, d)) 
            cout << "YES" << endl; 
        else
            cout << "NO" << endl;
    }
    return 0;
}
0
0 / 0 / 0
Регистрация: 12.05.2018
Сообщений: 54
05.10.2019, 09:48  [ТС] 3
большинство тестов не проходят по времени- time limited
0
Мозгоправ
1729 / 1023 / 468
Регистрация: 01.10.2018
Сообщений: 2,136
Записей в блоге: 2
05.10.2019, 14:50 4
Цитата Сообщение от borisboris1 Посмотреть сообщение
большинство тестов не проходят по времени- time limited
А чего ж вы это сразу не сказали?

По условию входные числа не превосходят 10^18. Измените тип данных с long на long long - у вас видимо Евклид циклится из-за переполнения.

Попробуйте переделать с потоков STL на cstdio: scanf, puts.

Обычно тестовые системы подают входные данные на stdin и принимают результат из stdout тестируемой программы. Почитайте описание вашей тестовой системы. Если это так, то уберите файловый ввод-вывод вообще.
0
0 / 0 / 0
Регистрация: 12.05.2018
Сообщений: 54
05.10.2019, 16:16  [ТС] 5
поменял на long long - ни какой разницы.
вот правила системы https://qbit.dots.org.ua/documents/instruction.pdf. как я понял - неправильный алгоритм
0
6971 / 4727 / 2714
Регистрация: 18.12.2017
Сообщений: 14,783
05.10.2019, 17:29 6
L0M, разве вывод должен находиться в теле цикла ?

borisboris1, переделал вывод, алгоритм не проверял. протестируйте так:
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
#include <iostream>
#include <fstream>
 
using namespace std;
 
bool checker_evk(long a, long b, long c, long d) {
    if ((a == c && b == d) || ((a == d && b == c))) return true;
    while (a != b) {
        if (a > b) a -= b; else b -= a;
        if ((a == c && b == d) || ((a == d && b == c))) return true;
    }
    return false;
}
 
int main() {
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    int p=0;
    long  k, a, b, c, d;
    cin >> k;
    for (long i = 0; i < k; ++i) {
        cin >> a >> b >> c >> d;
        if (checker_evk(a, b, c, d)) p=1;
    }
    
    if(p) cout << "YES\n"; 
    else cout << "NO\n";
    
system("pause");
return 0;
}
Добавлено через 2 минуты
алгоритм Евклида это вроде НОД ? как НОД может быть парой ? объясните если кто разобрался в условии
0
Мозгоправ
1729 / 1023 / 468
Регистрация: 01.10.2018
Сообщений: 2,136
Записей в блоге: 2
05.10.2019, 18:03 7
Цитата Сообщение от Yetty Посмотреть сообщение
L0M, разве вывод должен находиться в теле цикла ?
В моём варианте - да. Цикл идёт по блокам. Считываются сразу 4 числа, анализируются в функции и выводится ответ.

В вашем варианте ответ будет только один: по последней четвёрке чисел.

Цитата Сообщение от Yetty Посмотреть сообщение
алгоритм Евклида это вроде НОД ? как НОД может быть парой ? объясните если кто разобрался в условии
Верно, НОД. Для пары чисел. При работе алгоритма Евклида, когда оба числа становятся равными, это значение (одно) и будет НОД. Подробности см. в Википедии.
0
0 / 0 / 0
Регистрация: 12.05.2018
Сообщений: 54
05.10.2019, 18:19  [ТС] 8
Этот вариант алгоритма прошел 23 теста из 100 ( больше всех) ,но при этом перестал проходить тесты, которые прошлые варианты проходили. Вместо Time Limited пишет WA ( Wrong Answer) , а некоторые бывшие TL проходит на OK (правильно)
0
Мозгоправ
1729 / 1023 / 468
Регистрация: 01.10.2018
Сообщений: 2,136
Записей в блоге: 2
05.10.2019, 19:12 9
Цитата Сообщение от borisboris1 Посмотреть сообщение
Этот вариант алгоритма
Какой из?
0
813 / 500 / 211
Регистрация: 19.01.2019
Сообщений: 1,196
06.10.2019, 11:38 10
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool checker_evk(uint64_t a, uint64_t b, uint64_t c, uint64_t d) {
    if (a == c && b == d) {
        return true;
    }
    while (b) {
        if (a < b) {
            std::swap(a, b);
        }
        if (b > d) {
            a %= b;
            continue;
        }
        if (b < d || a <= c) {
            return false;
        }
        if ((a - c) % d == 0) {
            return true;
        }
    }
    return false;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.10.2019, 11:38

Не проходит все тесты
#include &lt;iostream&gt; #include &lt;cmath&gt; int main() { long long m, n; std::cin &gt;&gt; m &gt;&gt; n; ...

Числа Смита (Не проходит все тесты)
Число Смита — такое составное число, сумма цифр которого равняется сумме цифр всех его простых...

Программа не проходит тесты по времени, посоветуйте как исправить
Добрый день, не могли бы вы подсказать по задаче. Имеется круг с целыми числами от 1 до n. Числа...

Задача «Форматирование кода» не проходит все тесты
Задача не проходит все тесты. Пример, указанный в условии работает, а потом тестировщик пробует еще...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

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