Это олимпиада по икт.
Студент Кеша устроился на летнюю стажировку. Кеша охотно бы ходил на работу
пешком,
но, к его сожалению, офис компании расположен довольно далеко от дома Кеши. А поскольку в
городе проводится спортивный праздник, общественный транспорт ходит крайне редко, и желающих
ехать на нём очень много. Впрочем, Кеша уже давно присматривается к электросамокату, и хочет
выяснить, много ли усилий ему придётся приложить, чтобы добраться на нём до места работы.
Кеша уже провёл некоторые расчёты и выяснил, что его маршрут содержит в себе ровные участ-
ки суммарной длиной p единиц, а также участки, на которых ему придётся подниматься в гору,
суммарной длиной m единиц. Участки, на которых Кеша будет двигаться под гору, он решил не
учитывать, поскольку электросамокат будет катиться на таких участках по инерции.
При движении по ровному участку аккумулятор самоката будет расходовать 1 единицу ёмкости,
а при движении в гору — 2 единицы ёмкости на единицу длины. Если же Кеша не будет включать
электродвигатель, то для перемещения на каждой единице длины ровного участка ему потребу-
ется приложить усилие величины a, а на каждой единице длины участка, ведущего в гору, ему
потребуется приложить усилие величины b (b > a).
Ёмкость аккумулятора составляет q единиц. Кеша полагает, что в разные дни он может включать
электродвигатель на разных участках. И пока хочет узнать, какое максимальное и какое минималь-
ное количество усилий ему придётся приложить, чтобы добраться до работы, если по дороге он
полностью израсходует энергию, запасённую в аккумуляторе.
Это олимпиада по икт.
Студент Кеша устроился на летнюю стажировку. Кеша охотно бы ходил на работу
пешком,
но, к его сожалению, офис компании расположен довольно далеко от дома Кеши. А поскольку в
городе проводится спортивный праздник, общественный транспорт ходит крайне редко, и желающих
ехать на нём очень много. Впрочем, Кеша уже давно присматривается к электросамокату, и хочет
выяснить, много ли усилий ему придётся приложить, чтобы добраться на нём до места работы.
Кеша уже провёл некоторые расчёты и выяснил, что его маршрут содержит в себе ровные участ-
ки суммарной длиной p единиц, а также участки, на которых ему придётся подниматься в гору,
суммарной длиной m единиц. Участки, на которых Кеша будет двигаться под гору, он решил не
учитывать, поскольку электросамокат будет катиться на таких участках по инерции.
При движении по ровному участку аккумулятор самоката будет расходовать 1 единицу ёмкости,
а при движении в гору — 2 единицы ёмкости на единицу длины. Если же Кеша не будет включать
электродвигатель, то для перемещения на каждой единице длины ровного участка ему потребу-
ется приложить усилие величины a, а на каждой единице длины участка, ведущего в гору, ему
потребуется приложить усилие величины b (b > a).
Ёмкость аккумулятора составляет q единиц. Кеша полагает, что в разные дни он может включать
электродвигатель на разных участках. И пока хочет узнать, какое максимальное и какое минималь-
ное количество усилий ему придётся приложить, чтобы добраться до работы, если по дороге он
полностью израсходует энергию, запасённую в аккумуляторе.
Студент Кеша устроился на летнюю стажировку. Кеша охотно бы ходил на работу
пешком,
но, к его сожалению, офис компании расположен довольно далеко от дома Кеши. А поскольку в
городе проводится спортивный праздник, общественный транспорт ходит крайне редко, и желающих
ехать на нём очень много. Впрочем, Кеша уже давно присматривается к электросамокату, и хочет
выяснить, много ли усилий ему придётся приложить, чтобы добраться на нём до места работы.
Кеша уже провёл некоторые расчёты и выяснил, что его маршрут содержит в себе ровные участ-
ки суммарной длиной p единиц, а также участки, на которых ему придётся подниматься в гору,
суммарной длиной m единиц. Участки, на которых Кеша будет двигаться под гору, он решил не
учитывать, поскольку электросамокат будет катиться на таких участках по инерции.
При движении по ровному участку аккумулятор самоката будет расходовать 1 единицу ёмкости,
а при движении в гору — 2 единицы ёмкости на единицу длины. Если же Кеша не будет включать
электродвигатель, то для перемещения на каждой единице длины ровного участка ему потребу-
ется приложить усилие величины a, а на каждой единице длины участка, ведущего в гору, ему
потребуется приложить усилие величины b (b > a).
Ёмкость аккумулятора составляет q единиц. Кеша полагает, что в разные дни он может включать
электродвигатель на разных участках. И пока хочет узнать, какое максимальное и какое минималь-
ное количество усилий ему придётся приложить, чтобы добраться до работы, если по дороге он
полностью израсходует энергию, запасённую в аккумуляторе.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения данной задачи можно воспользоваться жадным алгоритмом.
Для начала рассмотрим случай, когда Кеша всегда использует электродвигатель. На каждой единице длины ровного участка он будет тратить 1 единицу ёмкости, а на каждой единице длины участка в гору - 2 единицы ёмкости. Таким образом, если сумма всех участков в гору равна m, то ему придется потратить еще m единиц ёмкости. Следовательно, минимальное количество усилий, которое ему придется приложить, равно ma.
Теперь рассмотрим случай, когда Кеша не использует электродвигатель ни на одном участке. В этом случае ему придется приложить усилие на каждой единице длины участка, ведущего в гору, равное b. Таким образом, максимальное количество усилий, которое ему придется приложить, равно mb.
Итак, минимальное количество усилий - ma, максимальное количество усилий - mb.