Форум Всеукраїнської інтернет-олімпіади NetOI

LeonID написав:

потрібно знайти чисельник і знаменник нескоротного дробу х/y, які задовольняють умову (n/m)*(x/y)=p/q, тоді відповідь буде х+у-2.

Дякую, а де ж сам код 20 - бального рішення.

В предпредпоследней строке можно писать
cout << (n*q+m*p-2);

LVV написав:

Stas_Tomash написав:

Код:

#include <iostream>


#define ll long long

using namespace std;

ll gcd(ll a, ll b)
{
    while (a>0 && b>0)
    if (a>b) a%=b; else b%=a;
    return (a+b);
}

int main()
{
    ll n,m,p,q;
    cin >> m >> n >> p >> q;
    ll x=gcd(m,n), y=gcd(p,q);
    m/=x; n/=x; p/=y; q/=y;
    x=gcd(m,q); y=gcd(n,p);
    m/=x; q/=x; p/=y; n/=y;
    cout << (n*q/gcd(n*q, p*m)-1)+(m*p/gcd(n*q, p*m)-1);
    return 0;
}

Дійсно, це рішення проходить усі тести.
Але як таке може бути, коли, скажімо, для значень:
10000000001
10000000000
1000000001
1000000000
які відповідають умові задачі: "Кожне з чисел не перевищує 10^18"
в результаті отримуємо -12.

Тут цікава ситуація, я пропонував журі навести хоч один тест де є відповідь -1. Як мені відповіли відомо.

LeonID написав:

Тут цікава ситуація, я пропонував журі навести хоч один тест де є відповідь -1. Як мені відповіли відомо.

Оце начеб-то і є ситуація, коли мали б отримати -1.
Тоді в рішенні потрібно було додати розрахункові обмеження.

double PM,QN;
    PM=double(p)*double(m);
    QN=double(q)*double(n);
            if (PM>1e18 || QN> 1e18)
            {
                cout << -1; // коли не можна вирахувати
                return 0;
            }

https://yadi.sk/i/Bl05OoPbkRC5X

Але, враховуючи "гарантію" умови стосовно значення відповіді:

Stas_Tomash написав:

Журі в умові задачі гарантувало що якщо відповідь існує, то вона не перевищує 10^18. Достатньо очевидним є доведення, що відповідь існує завжди, тому за гарантією журі всі тести мають бути такі, що відповідь не перевищує 10^18

це питання знімається

Відредаговано LVV (2015-11-13 05:33:21)

Мені здається, що для пітона оці штуки зайві:

x = nod(n, m)
n /= x
m /= x
y = nod(p, q)
p /= y
q /= y

Це виключно для паскаля/С++, щоб в тип даних влізти
А по факту, рішення задачі зводиться до:

LeonID написав:

потрібно знайти чисельник і знаменник нескоротного дробу х/y, які задовольняють умову (n/m)*(x/y)=p/q, тоді відповідь буде х+у-2.

Звідси маємо: x/y = (n*q)/(m*p)
Задача: скоротити дріб у правій частині, отримаємо х та у
Так як пітон фактично не має обмежень на розмір змінних, достатньо написати:

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

m, n, p, q = map(long, raw_input().split())
x = gcd(m*p, n*q)
print m*p/x + n*q/x - 2

Я ні в якому разі не придираюся, чисто з естетичних міркувань.

Вважається, що в момент удару куля не може впасти в лузу в точці (0,0).

Мається на увазі, що в момент удару кут a може змінюватися від 0 до 90 градусів, чи від 0 до 360 градусів? І якщо кут може бути більше чим 90 градусів, то вважати, що при ударі, який направлений в лузу тангенс змінюється просто на протилежний?

Дайте хтось відповідь будь ласка!

Відредаговано Lisunsin (2015-12-27 14:31:31)