Задача о конспектах для лоботряса Лёши
В далекой-далекой галактике студент Леша узнал, что через два дня у него экзамен. Так получилось, что за весь год он ни разу не сходил на занятия. Леша не отчаялся и решил рационально распределить оставшееся время до экзамена на подготовку.
Он знает, что сегодня у него осталось a a часов свободного времени, а завтра он сможет готовиться в течение b b часов. Обратите внимание, что на планете, где живет Леша, в дне может быть гораздо больше часов, чем в земном. Качество подготовки к экзамену зависит только от количества конспектов, которые Леша успеет прочитать. У Леши есть доступ к бесконечному количеству конспектов, но он знает, что первый конспект он прочитает за час, второй конспект за два часа и так далее, то есть Леша может прочитать конспект с номером k k за k k часов. Леша может читать конспекты в произвольном порядке, но он не может начать читать конспект в первый день, а дочитать во второй день. Таким образом, Леша должен прочитать несколько конспектов целиком в первый день, затратив на это не более a a часов суммарно, и несколько конспектов целиком во второй день, затратив на это не более b b часов. Сколько максимум конспектов успеет прочитать Леша за оставшееся время до экзамена? Какие конспекты он должен читать в первый день, а какие — во второй?:jazik::lamo::bsod: |
ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff fffffffffffffffffffffffffffffffffffffffffff:sigh:
|
http://www.tehnari.ru/f8/t15561/
Создавайте темы с осмысленным названием, топики с заглавием ПОМОГИТЕ!!!!!!!!!! будут удаляться. А за Цитата:
|
Да... забавная такая задачка. Поломал малость голову. Но мне кажется, что я понял, как её решить.
1. Понятно, что если нужно набрать максимальное КОЛИЧЕСТВО конспектов, то целесообразно идти с первого и далее по восходящей. 2. Таким образом, общее время, затраченное на штудирование n конспектов (Tn), можно определить, исходя из формул арифметической прогрессии: Wn = W1 + (n-1)*Q Tn = (n/2)*(W1 +Wn). Здесь W1 — первый член прогрессии, Wn — n-й член, Q — разность. В данном случае W1=Q=1. 3. Можно поставить обратную задачу: зная суммарное время, определить число n. Это приведёт к квадратному уравнению, целая часть осмысленного корня которого и будет ответом. 4. Временно "забудем" о невозможности дробить изучение конспекта между двумя днями и определим n вышеописанным способом, исходя из Tn = a + b. 5. А теперь я попробую доказать, что, невзирая на условие "неделимости" конспектов, найденное значение n и будет ответом на задачу. Действуем так: Из двух чисел a и b выбираем наибольшее. Пусть это будет, например, b (второй день). Определяем Nb — количество конспектов, которое надлежит изучить во ВТОРОЙ день. Тут несколько сложнее: нужно рассмотреть УБЫВАЮЩУЮ арифметическую прогрессию, стартующую с Wn с разностью Q=-1. Также потребуем, чтобы сумма Tb членов не превышала b. И теперь — внимание! — во ВТОРОЙ день наш лоботряс должен проштудировать: a) конспекты с номерами от n до n-Nb. б) конспект с номером b-Tb. Таким образом, ВТОРОЙ день будет заполнен целиком. в) то, что останется из n конспектов, автоматически влезет в день a. Рассмотрим пример. Пусть a=4, b=8. Таким образом, общее время, отведённое на учёбу, составит 12 часов. Находим, что n=4, т.е. надо изучить конспекты с номерами 1, 2, 3 и 4. Общее время штудирования этих конспектов составит 10 часов. Во второй день (8 часов) находим, что лоботряс может проштудировать 2 конспекта (начиная с самого длинного и вниз ПО ОЧЕРЕДИ). Этими конспектами будут 4 и 3, так что Tb составит 7. Добавим к ним конспект с номером 8-7=1, таким образом, ВТОРОЙ день окажется заполненным целиком. А на первый останется конспект номер 2 и два часа свободного времени. Конечно, можно, например, вместо 4 взять конспект 5, но это не повлияет на общее количество конспектов, а оно-то нас и интересует. Как-то так. Вроде бы. |
Здорово! Кажется, это называется "линейное программирование" :) Никогда не мог понять методику решения, кроме тупого перебора.
|
Часовой пояс GMT +4, время: 19:52. |
Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.