Решение задачи "Гирлянда" с Меньшиков

Без пояснения   Просмотров: 24


Гирлянда состоит из N лампочек на общем проводе. Один её конец закреплён на заданной высоте A мм (H1 = A). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (Hi = (Hi - 1 + Hi + 1) / 2 - 1 для 1 < i < N). Требуется найти минимальную высоту второго конца B (B = HN) при условии, что ни одна из лампочек не должна лежать на земле (Hi > 0 для 1 <= i <= N).

Ограничения: 3 <= N <= 1000 - целое, 10 <= A <= 1000 - вещественное.

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n;
const double eps = 1e-9;
vector<double> h;
void input()
{
    cin>>n;
    h.resize(n);
    cin>>h[0];
}
double _fabs(double a)
{
    if (a<0)
        return -a;
    return a;
}
double Equal(double a, double b)
{
    return _fabs(a-b) <= eps;
}
double Less(double a, double b)
{
    return a < b && !Equal(a,b);
}
double More(double a, double b)
{
    return a > b && !Equal(a,b);
}
void solve()
{
    double res = 1e9;
    double l = 0, r = h[0];
    while (Less(l,r))
    {
        h[1] = (l + r) / 2;
        h.back() = 0;
        bool isUp = false;
        for (int i=2;i<n;i++)
        {
            h[i] = 2*h[i-1] - h[i-2] + 2;
            if (!More(h[i],0))
            {
                isUp = true;
                break;
            }
        }
        if (More(h.back(),0.0))
            res = min(res,h.back());
        if (isUp)
            l = h[1];
        else
            r = h[1];
    }
    printf("%0.2f",res);
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться