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


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

Ви не зайшли.

#1 2020-11-08 12:08:13

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

Розв`язок задачі Railroad

Щоб не чекати пів року, пропоную ділитись розв'язками тут.

Код:

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main()
{
     double  L, a1, a2, v, t;
    cin >> L >> a1 >> a2 >> v >> t;
    
    double T, t1,t2,t3,tx,vx;
    tx = (L - v*v/2/a1 - v*t - v*v/2/a2) / v;
    if (tx < 0) 
    {
        t3 = t;
        double a,b,c;
         a=a1/2*(1.0 + a1/a2);
        b=a1*t;
        c=-L;
         double x1,x2;
     x1=(-b+sqrt(pow(b,2.0)-4*a*c))/(2*a);
     x2=(-b-sqrt(pow(b,2.0)-4*a*c))/(2*a);
         if (x1<0)
        {
            t1 = x2;
            t2 = a1*x2/a2;
        }
    
        else if (x2<0)
        {
            t1 = x1;
            t2 = a1*x1/a2;
        }
        else
        {
            if (x1<x2)
            {
                t1 = x1;
                t2 = a1*x1/a2;
            }
            else
            {
                t1 = x2;
                t2 = a1*x2/a2;
            }
        }
    }
    else
    {
    t2 = t + tx;
    t1 = sqrt((L - v*(t2)   -  v*v/2/a2) * 2 / a1);
    t3 = sqrt((L - v*(t2)   -  v*v/2/a1) * 2 / a2);
    }
 
    T = t1 + t2 + t3;
    cout << fixed << setprecision(8) << T;
 return 0;
}

Вибачте, що не використовував pow(v,2.0)    У записі v*v менше букоффф smile

Алгоритм розв'язку у коментарях до програмного коду нижче:

Код:

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main()
{
     double  L, a1, a2, v, t;
    cin >> L >> a1 >> a2 >> v >> t;
    
    double T, t1,t2,t3,tx,vx;
//T-загальний час
//t1,t2,t3 - тривалість руху на трьох ділянках
//tx-час розгону до максимально можливої швидкості за умовою
//vx-до якої максимальної швидкості можна розігнатись реально 
    
     //Щоб проїхати найшвидше потрібно розігнатись до максимальної швидкості v
    //s1 = a1*t1*t1/2   s1 = v*v/2/a1
    //s2 = v*(t+tx)  
    //s3 = a2*t3*t3/2   s3 = v*v/2/a2
    //L= v*v/2/a1 + v*(t+tx)   + v*v/2/a2
    //L= v*v/2/a1 + v*t + v*tx + v*v/2/a2
 
    //звідки: 
    tx = (L - v*v/2/a1 - v*t - v*v/2/a2) / v;
    //cout << tx << endl;
    
    //Якщо не можна розігнатись до максимальної швидкості
    if (tx < 0) 
    {
        //тоді час рівномірного руху t3 повинен бути мінімальним
        t3 = t;
 
        //s1= vx*vx/2/a1 = a1*t1*t1/2
        //s2 = vx*t
        //s3 = vx*vx/2/a2 = a2*t3*t3/2
        //vx = a1*t1 = a2*t3 => t3 = a1*t1/a2
 
        //L = s1 + s2 + s3
 
        //знаходимо t1
        //L = a1*t1*t1/2 + a1*t1*t + a2*(a1*t1/a2)*(a1*t1/a2)/2
        //L = (a1/2)*t1*t1 + a1*t*t1 + (a1*a1/a2/2)*t1*t1
        //L = (a1/2)*t1*t1 + a1*t*t1 + (a1*a1/a2/2)*t1*t1
        //a1/2(1 + a1/a2)*t1*t1 + a1*t*t1 - L = 0
        double a,b,c;
 
        a=a1/2*(1.0 + a1/a2);
        b=a1*t;
        c=-L;
 
    
    //находим t1
        double x1,x2;
 
    x1=(-b+sqrt(pow(b,2.0)-4*a*c))/(2*a);
 
    x2=(-b-sqrt(pow(b,2.0)-4*a*c))/(2*a);
 
     
        if (x1<0)
        {
            t1 = x2;
            //находим t2
            t2 = a1*x2/a2;
        }
    
        else if (x2<0)
        {
            t1 = x1;
            //находим t2
            t2 = a1*x1/a2;
        }
        else
        {
            if (x1<x2)
            {
                t1 = x1;
                //находим t2
                t2 = a1*x1/a2;
            }
            else
            {
                t1 = x2;
                //находим t2
                t2 = a1*x2/a2;
            }
        }
    }
    //Якщо можна розігнатись до максимальної швидкості
    else
    {
    //Знаходимо t2
    t2 = t + tx;
 
    //s1 + s2 + s3 – L = 0
    
    //знаходимо t1
    //a1*t1*t1/2 + v*(t2)  + v*v/2/a2 - L = 0
    t1 = sqrt((L - v*(t2)   -  v*v/2/a2) * 2 / a1);
 
    //знаходимо t3
    //v*v/2/a1+ v*(t2)  + a2*t3*t3/2  - L = 0
    t3 = sqrt((L - v*(t2)   -  v*v/2/a1) * 2 / a2);
    }
 
 
    //знаходимо загальний час:
    T = t1 + t2 + t3;
 
    cout << fixed << setprecision(8) << T;
    
 
 
     return 0;
}

Відредаговано LVV (2020-11-08 12:45:16)


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

Поза форумом

 

#2 2020-11-08 17:30:42

GeniusDP
Олімпієць
Зареєстрований: 2020-10-15
Повідомлень: 18

Re: Розв`язок задачі Railroad

Код:

#include <bits/stdc++.h>

using namespace std;

double L, a1, a2, v, t;


//функция, определяющая, можем ли мы при такой скорости
//отсановится ровно на финише или до него(главное - не перескочить).
bool can(double speed){
    return speed*speed/(2*a1) + speed*t + speed*speed/(2*a2)-0.000000001 < L;
}


int main()
{
    cin >> L >> a1 >> a2 >> v >> t;

    double left=0, speed, right=v;

    //подбираем максимально возможную скорость
    //двоичный поиск по ответу
    //и да: мне жутко обидно, что я набрал только 8/20 по
    //этой задаче ТОЛЬКО из-за того, что написал маловато нулей
    //в точности (0.00001 вроде). Сейчас - АС.
    while(right-left>0.000000001){
        speed=(left+right)/2;
        if( can(speed) )left=speed;
            else right=speed;
    }

    /*
        тут дальше плохо написано, но суть
        в том, что из двух вариантов скорости right и left отбираем тот,
        который подходит.
    */
    if( !can(right) )swap(left, right);
    //будем выводить только right



    double sp=right;//результирующая скорость
    double time=sp/a1+sp/a2;//время разгона и торможения
    L-=sp*sp/(2*a1)+sp*sp/(2*a2);//оставим только то расстояние, которое проедем равномерно
    printf("%.10f", L/sp+time);
    return 0;
}

Відредаговано GeniusDP (2020-11-08 17:31:32)

Поза форумом

 

#3 2020-11-08 23:32:05

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 30

Re: Розв`язок задачі Railroad

Код:

#include <cstdio>
#include <cmath>

using std::scanf;
using std::printf;

int main()
{
    long double L,a1,a2,v,t;
    scanf("%Lg%Lg%Lg%Lg%Lg",&L,&a1,&a2,&v,&t);
    long double Q=1.0L/a1+1.0L/a2;
    if(L/v-0.5L*v*Q<t) v=2.0L*L/(t+std::sqrt(t*t+2.0L*L*Q));
    printf("%.21Lg\n",L/v+0.5L*v*Q);
    return 0;
}

Используется https://en.wikipedia.org/wiki/Quadratic … r's_method , которая бывает полезна как численно, так и аналитически (свободной обработкой случая A->0). Впрочем, в коде LVV catastrophic cancellation, вроде бы, не приводит к потере точности.

LVV написав:

Вибачте, що не використовував pow(v,2.0)

А в чём вообще может быть преимущество?

Поза форумом

 

#4 2020-11-10 17:26:11

GeniusDP
Олімпієць
Зареєстрований: 2020-10-15
Повідомлень: 18

Re: Розв`язок задачі Railroad

FordPerfect написав:

А в чём вообще может быть преимущество?

Ну на сколько я знаю pow просто приятней читать.

Відредаговано GeniusDP (2020-11-10 17:26:36)

Поза форумом

 

#5 2020-11-11 17:59:54

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

Re: Розв`язок задачі Railroad

python 2.7

Код:

L, a1, a2, v, t = map(float, raw_input().split())
a_h = 1.0/(1/a1+1/a2)
L_cr = v*t + v**2/(2*a_h)
if L > L_cr:
    print L/v+v/2.0/a_h
else:
    print (2*L/a_h+t**2)**0.5

Відредаговано andervish (2020-11-11 19:21:48)

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt