Есть N приборов, пронумерованных от 1 до N, для каждого известно время подготовки к работе (Ai) и работы до отключения (Bi). И есть техник, который может подготовить любой прибор к работе и включить, после чего тот отработает свое время и отключится. Готовить к работе техник может в каждый момент времени только один прибор, но если какой-то прибор не работает в данный момент, техник не имеет права отдыхать.
Когда все приборы работают, он может, наконец, отдохнуть, пока какой-то прибор не отключился.
Требуется, зная Ai и Bi (целые количества минут), сказать, в каком порядке следует включать приборы, чтобы иметь возможность хоть немного отдохнуть, либо сказать, что это невозможно.
Скорее всего, что-то очень простое, но в голову ничего разумного пока не пришло...
Отсортировать по убыванию Bi — не годится. Например: (Ai, Bi) = (1, 5), (4, 3), (1, 1). В таком порядке отдохнуть не получится, но если сначала подготовить и включить второй, а потом первый и третий, то останется 1 минута на отдых.
Здравствуйте, kfmn, Вы писали:
K>Всем привет!
K>Нужна подсказка в такой задаче:
K>Есть N приборов, пронумерованных от 1 до N, для каждого известно время подготовки к работе (Ai) и работы до отключения (Bi). И есть техник, который может подготовить любой прибор к работе и включить, после чего тот отработает свое время и отключится. Готовить к работе техник может в каждый момент времени только один прибор, но если какой-то прибор не работает в данный момент, техник не имеет права отдыхать. K>Когда все приборы работают, он может, наконец, отдохнуть, пока какой-то прибор не отключился.
K>Требуется, зная Ai и Bi (целые количества минут), сказать, в каком порядке следует включать приборы, чтобы иметь возможность хоть немного отдохнуть, либо сказать, что это невозможно.
K>Скорее всего, что-то очень простое, но в голову ничего разумного пока не пришло... K>Отсортировать по убыванию Bi — не годится. Например: (Ai, Bi) = (1, 5), (4, 3), (1, 1). В таком порядке отдохнуть не получится, но если сначала подготовить и включить второй, а потом первый и третий, то останется 1 минута на отдых.
Предположим техник начал готовить один прибор, но тут закончил работу другой. Может ли он "временно" переключиться на подготовку второго?
Здравствуйте, kfmn, Вы писали:
K>Всем привет!
K>Нужна подсказка в такой задаче:
K>Есть N приборов, пронумерованных от 1 до N, для каждого известно время подготовки к работе (Ai) и работы до отключения (Bi). И есть техник, который может подготовить любой прибор к работе и включить, после чего тот отработает свое время и отключится. Готовить к работе техник может в каждый момент времени только один прибор, но если какой-то прибор не работает в данный момент, техник не имеет права отдыхать. K>Когда все приборы работают, он может, наконец, отдохнуть, пока какой-то прибор не отключился.
K>Требуется, зная Ai и Bi (целые количества минут), сказать, в каком порядке следует включать приборы, чтобы иметь возможность хоть немного отдохнуть, либо сказать, что это невозможно.
Если не требуется находить оптимального решения, то задача довольна проста.
Решение ищем рекурсивно. Изначально у нас N приборов.
Пусть B это сумма всех Bi. Тогда, если не найдется такого i, что Ai > B — Bi, то решения нет. Т.е в этом случае технику отдохнуть не удастся.
Если же найдется несколько таких i, то надо выбрать из них коэффициент с максимальным Bi. Техник должен первым ремонтировать данный прибор.
Теперь останется (N-1) прибор и продолжаем рекурсию далее. Процесс остановится. Если удастся дойти до конца, то решение будет найдено.
Здравствуйте, Chorkov, Вы писали:
C>Предположим техник начал готовить один прибор, но тут закончил работу другой. Может ли он "временно" переключиться на подготовку второго?
В условии про это ничего не сказано. Так что пусть будет "может".
Здравствуйте, baily, Вы писали:
B>Если не требуется находить оптимального решения, то задача довольна проста. B>Решение ищем рекурсивно. Изначально у нас N приборов. B>Пусть B это сумма всех Bi. Тогда, если не найдется такого i, что Ai > B — Bi, то решения нет. Т.е в этом случае технику отдохнуть не удастся. B>Если же найдется несколько таких i, то надо выбрать из них коэффициент с максимальным Bi. Техник должен первым ремонтировать данный прибор. B>Теперь останется (N-1) прибор и продолжаем рекурсию далее. Процесс остановится. Если удастся дойти до конца, то решение будет найдено.
Спасибо за идеи. Можешь немного пояснить:
1. Почему решения нет, если для всех i: Ai+Bi <= B ?
2. Почему надо выбирать максимальный Bi? Это эвристика или она чем-то подкреплена? При рекурсии надо уменьшать B на значение выбранного Bi, так?
3. Приборов в тестах может быть до 50000, не возникнет ли stack overflow при такой рекурсии?
Здравствуйте, kfmn, Вы писали:
K>Здравствуйте, Chorkov, Вы писали:
C>>Предположим техник начал готовить один прибор, но тут закончил работу другой. Может ли он "временно" переключиться на подготовку второго?
K>В условии про это ничего не сказано. Так что пусть будет "может".
Тогда решение есть всегда, если все B ненулевые:
Готовим все приборы до состояния "осталось работать 1 секунду". (Или пикосекунду, если приборов много...)
Потом все запускам. отдыхаем min_{i}(B_i)
Здравствуйте, Chorkov, Вы писали:
C>Здравствуйте, kfmn, Вы писали:
K>>Здравствуйте, Chorkov, Вы писали:
C>>>Предположим техник начал готовить один прибор, но тут закончил работу другой. Может ли он "временно" переключиться на подготовку второго?
K>>В условии про это ничего не сказано. Так что пусть будет "может".
C>Тогда решение есть всегда, если все B ненулевые: C>Готовим все приборы до состояния "осталось работать 1 секунду". (Или пикосекунду, если приборов много...) C>Потом все запускам. отдыхаем min_{i}(B_i) C>
А, теперь я понял, что ты имел в виду... Нет, видимо все-таки надо считать, что подготовка это непрерывный процесс, который заканчивается запуском.
K>Требуется, зная Ai и Bi (целые количества минут), сказать, в каком порядке следует включать приборы, чтобы иметь возможность хоть немного отдохнуть, либо сказать, что это невозможно.
K>Скорее всего, что-то очень простое, но в голову ничего разумного пока не пришло...
Начиная с самого длинного Ai+Bi, далее по убыванию.
Если Сумма Ai больше, чем максимальный Ai+Bi, то отдыхать не будешь.
Здравствуйте, kfmn, Вы писали:
K>Здравствуйте, baily, Вы писали:
B>>Если не требуется находить оптимального решения, то задача довольна проста. B>>Решение ищем рекурсивно. Изначально у нас N приборов. B>>Пусть B это сумма всех Bi. Тогда, если не найдется такого i, что Ai > B — Bi, то решения нет. Т.е в этом случае технику отдохнуть не удастся. B>>Если же найдется несколько таких i, то надо выбрать из них коэффициент с максимальным Bi. Техник должен первым ремонтировать данный прибор. B>>Теперь останется (N-1) прибор и продолжаем рекурсию далее. Процесс остановится. Если удастся дойти до конца, то решение будет найдено.
K>Спасибо за идеи. Можешь немного пояснить:
Вообще то это не идеи а уже готовое решение
K>1. Почему решения нет, если для всех i: Ai+Bi <= B ?
Предположим, что решение есть. Это означает, что технику удастся отдохнуть в некоторый момент времени. Т.е в этот момент времени все приборы работают.
Т.е все они были ранее запущены. Рассмотрим тот прибор, который был запущен первым. После того как он был запущен также были запущены все прочие приборы.
Т.е прошло (B — Bi) секунд. Но т.к (B — Bi) > Ai, то это прибор уже должен был остановиться. Противоречие.
K>2. Почему надо выбирать максимальный Bi? Это эвристика или она чем-то подкреплена?
Предположим, что решение задачи есть.
Это означает, что существует перестановка из N элементов i1, ..., iN, что когда техник последовательно запускает приборы в этом порядке,
то после того как будет запущен последний прибор все они еще продолжают работать. Без ограничения общности можно считать, что это просто последовательность 1, 2, ..., N.
Рассмотрим два первых элемента. Пусть у нас (A1 + B1 > B) и (A2 + B2 > B). Но при этом B1 < B2.
Переставим их местами. Т.е будем включать приборы в порядке 2, 1, 3, 4, ..., N.
Этот порядок также будет решением.
В самом деле, — для приборов 3, 4, ..., N вообще ничего не изменилось.
Для прибора 1 ситуация даже улучшилась, т.к в новой последовательности с момента его запуска пройдет еще меньше времени, чем при старой последовательности.
Ну а прибор 2 также будет работать, т.к (A2 + B2 > B).
Таким образом, если у нас есть решение, то мы можем получить еще одно решение, в котором Bi будут максимальными на каждом шаге.
( заметим, что максимум каждый раз берется не по всем Bi, а по тем из них, что (Ai + Bi > B) )
K>3. Приборов в тестах может быть до 50000, не возникнет ли stack overflow при такой рекурсии?
С какой радости? Рекурсию я использовал для математического доказательства.
Ну а для написания программы ее использовать не нужно. Делаем просто цикл в N итераций.
На каждой итерации находим один прибор. Так что в памяти ничего не хранится. И никакого overflow случиться не может
Здравствуйте, baily, Вы писали:
B>Здравствуйте, kfmn, Вы писали:
K>>Здравствуйте, baily, Вы писали:
B>>>Если не требуется находить оптимального решения, то задача довольна проста. B>>>Решение ищем рекурсивно. Изначально у нас N приборов. B>>>Пусть B это сумма всех Bi. Тогда, если не найдется такого i, что Ai > B — Bi, то решения нет. Т.е в этом случае технику отдохнуть не удастся. B>>>Если же найдется несколько таких i, то надо выбрать из них коэффициент с максимальным Bi. Техник должен первым ремонтировать данный прибор. B>>>Теперь останется (N-1) прибор и продолжаем рекурсию далее. Процесс остановится. Если удастся дойти до конца, то решение будет найдено.
K>>Спасибо за идеи. Можешь немного пояснить:
B>Вообще то это не идеи а уже готовое решение
K>>1. Почему решения нет, если для всех i: Ai+Bi <= B ?
B>Предположим, что решение есть. Это означает, что технику удастся отдохнуть в некоторый момент времени. Т.е в этот момент времени все приборы работают. B>Т.е все они были ранее запущены. Рассмотрим тот прибор, который был запущен первым. После того как он был запущен также были запущены все прочие приборы. B>Т.е прошло (B — Bi) секунд. Но т.к (B — Bi) > Ai, то это прибор уже должен был остановиться. Противоречие.
Долго тупил над этим объяснением... Потом понял, что ты поменял местами Ai и Bi — у тебя Bi — время подготовки, Ai — время работы, а в условии наоборот!
Я потому и не понял первоначальную идею!
K>>2. Почему надо выбирать максимальный Bi? Это эвристика или она чем-то подкреплена?
B>Предположим, что решение задачи есть. B>Это означает, что существует перестановка из N элементов i1, ..., iN, что когда техник последовательно запускает приборы в этом порядке, B>то после того как будет запущен последний прибор все они еще продолжают работать. Без ограничения общности можно считать, что это просто последовательность 1, 2, ..., N. B>Рассмотрим два первых элемента. Пусть у нас (A1 + B1 > B) и (A2 + B2 > B). Но при этом B1 < B2. B>Переставим их местами. Т.е будем включать приборы в порядке 2, 1, 3, 4, ..., N. B>Этот порядок также будет решением. B>В самом деле, — для приборов 3, 4, ..., N вообще ничего не изменилось. B>Для прибора 1 ситуация даже улучшилась, т.к в новой последовательности с момента его запуска пройдет еще меньше времени, чем при старой последовательности. B>Ну а прибор 2 также будет работать, т.к (A2 + B2 > B).
B>Таким образом, если у нас есть решение, то мы можем получить еще одно решение, в котором Bi будут максимальными на каждом шаге. B>( заметим, что максимум каждый раз берется не по всем Bi, а по тем из них, что (Ai + Bi > B) )
С перестановкой A и B все встало на места! Круто!
K>>3. Приборов в тестах может быть до 50000, не возникнет ли stack overflow при такой рекурсии?
B>С какой радости? Рекурсию я использовал для математического доказательства. B>Ну а для написания программы ее использовать не нужно. Делаем просто цикл в N итераций. B>На каждой итерации находим один прибор. Так что в памяти ничего не хранится. И никакого overflow случиться не может
Да, это я уже понял после того, как написал про SO
Здравствуйте, alpha21264, Вы писали:
A>Здравствуйте, kfmn, Вы писали:
K>>Требуется, зная Ai и Bi (целые количества минут), сказать, в каком порядке следует включать приборы, чтобы иметь возможность хоть немного отдохнуть, либо сказать, что это невозможно.
K>>Скорее всего, что-то очень простое, но в голову ничего разумного пока не пришло...
A>Начиная с самого длинного Ai+Bi, далее по убыванию. A>Если Сумма Ai больше, чем максимальный Ai+Bi, то отдыхать не будешь.
Боюсь, есть контрпример...
(10, 5) (2, 1) (1, 1)
Сумма Ai = 13, максимальный Ai + Bi = 15. Порядок подготовки именно такой, как ты описал. Но все трое одновременно работать не смогут...
Видимо, надо на каждом шаге уменьшать сумму оставшихся Ai и заново сравнивать с максимальным из оставшихся Ai+Bi...
Здравствуйте, baily, Вы писали:
B>Предположим, что решение задачи есть. B>Это означает, что существует перестановка из N элементов i1, ..., iN, что когда техник последовательно запускает приборы в этом порядке, B>то после того как будет запущен последний прибор все они еще продолжают работать. Без ограничения общности можно считать, что это просто последовательность 1, 2, ..., N. B>Рассмотрим два первых элемента. Пусть у нас (A1 + B1 > B) и (A2 + B2 > B). Но при этом B1 < B2. B>Переставим их местами. Т.е будем включать приборы в порядке 2, 1, 3, 4, ..., N. B>Этот порядок также будет решением. B>В самом деле, — для приборов 3, 4, ..., N вообще ничего не изменилось. B>Для прибора 1 ситуация даже улучшилась, т.к в новой последовательности с момента его запуска пройдет еще меньше времени, чем при старой последовательности. B>Ну а прибор 2 также будет работать, т.к (A2 + B2 > B).
B>Таким образом, если у нас есть решение, то мы можем получить еще одно решение, в котором Bi будут максимальными на каждом шаге. B>( заметим, что максимум каждый раз берется не по всем Bi, а по тем из них, что (Ai + Bi > B) )
Почему для приборов 3, 4,.... ничего не изменилось?
Если первый прибор готовят 10 минут, а работает он час, а второй готовят 20 минут, а работает он полчаса, то на все остальные будет 30 минут, пока работают оба. А если наоборот, то только 20 минут.
Здравствуйте, kfmn, Вы писали:
A>>Начиная с самого длинного Ai+Bi, далее по убыванию. A>>Если Сумма Ai больше, чем максимальный Ai+Bi, то отдыхать не будешь.
K>Боюсь, есть контрпример... K>(10, 5) (2, 1) (1, 1) K>Сумма Ai = 13, максимальный Ai + Bi = 15. Порядок подготовки именно такой, как ты описал. Но все трое одновременно работать не смогут...
K>Видимо, надо на каждом шаге уменьшать сумму оставшихся Ai и заново сравнивать с максимальным из оставшихся Ai+Bi...
Здравствуйте, kfmn, Вы писали:
K>Здравствуйте, baily, Вы писали:
B>>Предположим, что решение задачи есть. B>>Это означает, что существует перестановка из N элементов i1, ..., iN, что когда техник последовательно запускает приборы в этом порядке, B>>то после того как будет запущен последний прибор все они еще продолжают работать. Без ограничения общности можно считать, что это просто последовательность 1, 2, ..., N. B>>Рассмотрим два первых элемента. Пусть у нас (A1 + B1 > B) и (A2 + B2 > B). Но при этом B1 < B2. B>>Переставим их местами. Т.е будем включать приборы в порядке 2, 1, 3, 4, ..., N. B>>Этот порядок также будет решением. B>>В самом деле, — для приборов 3, 4, ..., N вообще ничего не изменилось. B>>Для прибора 1 ситуация даже улучшилась, т.к в новой последовательности с момента его запуска пройдет еще меньше времени, чем при старой последовательности. B>>Ну а прибор 2 также будет работать, т.к (A2 + B2 > B).
B>>Таким образом, если у нас есть решение, то мы можем получить еще одно решение, в котором Bi будут максимальными на каждом шаге. B>>( заметим, что максимум каждый раз берется не по всем Bi, а по тем из них, что (Ai + Bi > B) )
K>Почему для приборов 3, 4,.... ничего не изменилось?
Потому что для любого такого прибора что при первом, что при втором способе его запуск случился через одинаковое время. А именно, для i-го прибора его запуск будет через B1 + ... + Bi.
Ну а время окончания запуска всех приборов также одинаково для обоих способов и равно B.
K>Если первый прибор готовят 10 минут, а работает он час, а второй готовят 20 минут, а работает он полчаса, то на все остальные будет 30 минут, пока работают оба. А если наоборот, то только 20 минут.
А это неважно. Я же писал, что мой алгоритм находит не самое оптимальное решение, а просто какое то решение. В вашей формулировке условия спрашивалось можно ли технику так включать приборы, чтобы иметь возможность отдыхать.
Если бы спрашивалось найти способ отдыхать как можно дольше, то задача станет значительно сложнее.
Здравствуйте, baily, Вы писали:
B>Здравствуйте, kfmn, Вы писали:
K>>Здравствуйте, baily, Вы писали:
B>>>Предположим, что решение задачи есть. B>>>Это означает, что существует перестановка из N элементов i1, ..., iN, что когда техник последовательно запускает приборы в этом порядке, B>>>то после того как будет запущен последний прибор все они еще продолжают работать. Без ограничения общности можно считать, что это просто последовательность 1, 2, ..., N. B>>>Рассмотрим два первых элемента. Пусть у нас (A1 + B1 > B) и (A2 + B2 > B). Но при этом B1 < B2. B>>>Переставим их местами. Т.е будем включать приборы в порядке 2, 1, 3, 4, ..., N. B>>>Этот порядок также будет решением. B>>>В самом деле, — для приборов 3, 4, ..., N вообще ничего не изменилось. B>>>Для прибора 1 ситуация даже улучшилась, т.к в новой последовательности с момента его запуска пройдет еще меньше времени, чем при старой последовательности. B>>>Ну а прибор 2 также будет работать, т.к (A2 + B2 > B).
B>>>Таким образом, если у нас есть решение, то мы можем получить еще одно решение, в котором Bi будут максимальными на каждом шаге. B>>>( заметим, что максимум каждый раз берется не по всем Bi, а по тем из них, что (Ai + Bi > B) )
K>>Почему для приборов 3, 4,.... ничего не изменилось?
B>Потому что для любого такого прибора что при первом, что при втором способе его запуск случился через одинаковое время. А именно, для i-го прибора его запуск будет через B1 + ... + Bi. B>Ну а время окончания запуска всех приборов также одинаково для обоих способов и равно B.
K>>Если первый прибор готовят 10 минут, а работает он час, а второй готовят 20 минут, а работает он полчаса, то на все остальные будет 30 минут, пока работают оба. А если наоборот, то только 20 минут.
B>А это неважно. Я же писал, что мой алгоритм находит не самое оптимальное решение, а просто какое то решение. В вашей формулировке условия спрашивалось можно ли технику так включать приборы, чтобы иметь возможность отдыхать. B>Если бы спрашивалось найти способ отдыхать как можно дольше, то задача станет значительно сложнее.
alpha21264 предложил более простой критерий выбора — просто по убыванию Ai + Bi (с проверкой на каждом шаге, что максимальная сумма больше оставшегося суммарного времени подготовки), и я не могу понять, оба ли подхода работают... Как-то они выглядят не вполне равносильными.
