Тема: Олімпіада , математичної індукції

Напевно я найшов помилку у відповідях до олімпіади ось сайт http://osvita-tomakivka.dp.ua/zavdannja … amuvannja/
Завдання
Для ілюстрації метода математичної індукції у підручниках часів СРСР завжди наводилася наступна задача: «Довести, що будь-яку цілу суму грошей, починаючі з 8 крб., можна без здачі розміняти купюрами по 3 та 5 крб.». Вам не потрібно нічого доводити, а необхідно просто написати програму, яка б для двох типів купюр по Х та Y грошових одиниць визначала б, яку найбільшу суму грошей неможливо розміняти цими купюрами, якщо Х та Y – взаємно прості натуральні числа.

Тести до задачі “CHANGE”
№ тесту    Вхідні дані    Результат    Оцінка
1    3 5    7    2 бали
2    1 73    0    7 балів
3    24 17    367    7 балів
4    999 1001    994999    7 балів
5    46342 46341    2147441939    7 балів

В четвертому в мене виходить 997999 , я склав дві програми (дві показують однаковий результат) допоможіть підтвердити чи спростувати помилку напишіть в кого помилка (якщо в мене то поясніть чому)

Програма 1

#include <iostream>
#include <conio.h>
using namespace std;
 
const double MAX = 9999999999;
long int x, y;
double mas;
 
inline bool oneone(double k)
{
    double X;
    X = x;
    for (double i = 0; i < MAX; i++)
    {
        if (X == k)
        {
            return 1;
        }
        if (X > k)
            break;
        X += x;
    }
    return 0;
}
 
inline bool twotwo(double k)
{
    double Y;
    Y = y;
    for (double i = 0; i < MAX; i++)
    {
        if (Y == k)
        {
            return 1;
        }
        if (Y > k)
            break;
        Y += y;
    }
    return 0;
}
 
inline bool onetwo(double k)
{
    double X, XX, i;
    X = x;
    XX = x;
    Pochtok :
    for (i = 0; i < MAX; i++)
    {
        if (X == k)
        {
            return 1;
        }
        if (X > k)
            break;
        X += y;
    }
    if (XX >= MAX || XX > k)
    return 0;
    XX += x;
    X = XX;
    goto Pochtok;
}
 
inline bool twoone(double k)
{
    double Y, YY, i = 0;;
    Y = y;
    YY = y;
    Pochtok :
    for (i = 0; i < MAX; i++)
    {
        if (Y == k)
        {
            return 1;
        }
        if (Y > k)
            break;
        Y += x;
    }
    if (Y >= MAX || YY > k)
    return 0;
    YY += y;
    Y = YY;
    goto Pochtok;
}
 
int main()
{
    double m = 0;
    bool k;
    cout << "Enter X ->";
    cin >> x;
    cout << "Enter Y ->";
    cin >> y;   
    long int i;
    if (x > y)
        i = x;
    else
        i = y;
    if (x <= 0 || x > 46342 || y <= 0 || y > 46342)
    {
        cout << "Erorr (1 do 46342)";
        getch();
        return 0;
    }
    for (; i < MAX; i++)
    {
        if (x % 2 == 0 && i % 2 == 0)
        {
            k = oneone(i);
            if (k == 1)
                continue;
        }
        if (y % 2 == 0 && i % 2 == 0)
        {
            k = twotwo(i);
            if (k == 1)
                continue;
        }
        k = onetwo(i);
        if (k == 1)
            continue;
        k = twoone(i);
        if (k == 1)
            continue;
        mas=i;
    }
    cout <<"Max number = "<< mas;
    getch();
    return 0;
}

програма 2

#include <iostream>
#include <conio.h>
using namespace std;
 
int main()
{
    long int x, y, Suma;
    cout << "Enter X ->";
    cin >> x;
    cout << "Enter Y ->";
    cin >> y;
    if (x <= 0 || x > 46342 || y <= 0 || y > 46342)
    {
        cout << "Erorr (1 do 46342)";
        getch();
        return 0;
    }
    Suma = (x*y) - (x + y);
    if (Suma>0)
    cout <<"Mix sum = "<< Suma;
    else
        cout <<"Mix sum = 0";
    getch();
}

2

Re: Олімпіада , математичної індукції

В тестових даних помилка:
994999=1001*497+999*498, тобто розміняти можна.

Подякували: koala, Betterthanyou2

3

Re: Олімпіада , математичної індукції

yooll написав:

В тестових даних помилка:
994999=1001*497+999*498, тобто розміняти можна.

Щось я не можу зрозуміти ди Ви взяли 497 і 498

4

Re: Олімпіада , математичної індукції

1001*a+999*b = 994999
Якби було a=0, мали б
999*995 = 994005, не вистачає 994. Але кожна заміна 999 на 1001 збільшує суму на 1001-999=2, отже, якщо a=994/2=497, а b = 995-a = 498, то виходить що треба.

Подякували: Betterthanyou, yooll2