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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2015-11-12 16:42:05

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Розбір рішень Задача Billiards

Поділіться, хто має 20 бальне рішення smile


Вік живи - вік навчайся.

Поза форумом

 

#2 2015-11-12 17:16:23

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Розбір рішень Задача Billiards

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

Поза форумом

 

#3 2015-11-12 17:20:04

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розбір рішень Задача Billiards

LeonID написав:

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

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


Вік живи - вік навчайся.

Поза форумом

 

#4 2015-11-12 17:28:01

Stas_Tomash
Новий користувач
Зареєстрований: 2015-11-12
Повідомлень: 5

Re: Розбір рішень Задача Billiards

Код:

#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;
}

Відредаговано Stas_Tomash (2015-11-12 17:29:19)

Поза форумом

 

#5 2015-11-12 18:19:05

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 25

Re: Розбір рішень Задача Billiards

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

Поза форумом

 

#6 2015-11-12 19:28:01

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розбір рішень Задача Billiards

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.


Вік живи - вік навчайся.

Поза форумом

 

#7 2015-11-12 19:40:46

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Розбір рішень Задача Billiards

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. Як мені відповіли відомо.

Поза форумом

 

#8 2015-11-12 20:57:44

Stas_Tomash
Новий користувач
Зареєстрований: 2015-11-12
Повідомлень: 5

Re: Розбір рішень Задача Billiards

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

Поза форумом

 

#9 2015-11-12 21:01:24

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розбір рішень Задача Billiards

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)


Вік живи - вік навчайся.

Поза форумом

 

#10 2015-11-13 00:16:40

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 25

Re: Розбір рішень Задача Billiards

python 20/20

Код:

m, n, p, q = map(long, raw_input().split())

def nod(a, b):#
    while b != 0:
        a, b = b, a%b
    return a
   
x = nod(n, m)
n /= x
m /= x
y = nod(p, q)
p /= y
q /= y
z = nod(q, m)
t = nod(p, n)
print (n/t)*(q/z) + (m/z)*(p/t) - 2

Идейно мало чем отличается от решения Stas_Tomash.
Отличие - в комменте после его решения.

Відредаговано andervish (2015-11-13 00:18:25)

Поза форумом

 

#11 2015-11-13 18:21:04

Belitoron
Новий користувач
Зареєстрований: 2015-11-13
Повідомлень: 5

Re: Розбір рішень Задача Billiards

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

Код:

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

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

Поза форумом

 

#12 2015-11-14 01:35:33

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 25

Re: Розбір рішень Задача Billiards

Belitoron написав:

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

Так и есть. Причем вначале так и написал. Но потом подумал, что расчет может идти быстрее, если работать с меньшими числами (но это не проверял замерами, суеверие такое, выходит). А так как таймлимиты для всех языков одинаковы, в том числе и для тормозного по умолчанию питона, то и послал вариант с извращениями.

Поза форумом

 

#13 2015-12-27 14:30:02

Lisunsin
Новий користувач
Зареєстрований: 2015-12-14
Повідомлень: 11

Re: Розбір рішень Задача Billiards

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

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

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

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

Поза форумом

 

#14 2015-12-27 19:58:13

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розбір рішень Задача Billiards

Lisunsin написав:

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

в момент удару куля не може впасти в лузу в точці (0,0) отже кут не може бути 180<a<270 градусів.
Окрім того p та  q - за умовою натуральні числа, отже кут не може бути  90<=a<=180  а також 270<=a<=360
Залишається: 0<a<90
http://www.dpva.info/Guide/GuideMathema … nsOneStep/

Відредаговано LVV (2015-12-27 19:59:06)


Вік живи - вік навчайся.

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt