@ru_python
Andrey25.01.2018
18:46:40
18:46:40
Я думал, нужно только 1 выбрать, чтоб сумма была ≥ х
Sergey25.01.2018
18:46:51
18:46:51
Но чтобы оно было минимальным из возможных.
GoogleSergey25.01.2018
18:46:56
18:46:56
Или = x.
Andrey25.01.2018
18:49:03
18:49:03
А откуда эта задача? У нее точно есть решение не перебором?
Мне кажется, тут можно динамическое программирование применить, но нет идей как конкретно
Sergey25.01.2018
18:50:12
18:50:12
Обновил вопрос. Если понятнее, то вот:
"Как из данного количества чисел найти минимально возможную сумму этих чисел (можно с повторяющимися числами), которая >= x?"
А откуда эта задача? У нее точно есть решение не перебором?
Региональный этап всероссийской олимпиады школьниковА откуда эта задача? У нее точно есть решение не перебором?
http://informatics.mccme.ru/mod/statements/view.php?id=24703Там ограничение по времени исполнения 1 секунда стоит.
Andrey25.01.2018
18:55:03
18:55:03
А перебором пробовал? Точно не проходит?
Sergey25.01.2018
18:57:48
18:57:48
Ну, лол. Я подразумеваю перебор всех возможных комбинаций этих чисел.
Если и ты тоже, то, во-первых, составление всех комбинаций точно займет >1 секунды, а во-вторых, я не думаю, что на таких олимпиадах будут давать задачи, где нужен будет перебор (ну, или как-то может пригодиться).
Vitaliy Nameless25.01.2018
18:58:02
18:58:02
это практически задача о рюкзаке в иной форме
Sergey25.01.2018
18:58:42
18:58:42
?
Vitaliy Nameless25.01.2018
18:58:59
18:58:59
гугл по «динамическое программирование», «задача о рюкзаке»
GoogleVitaliy Nameless25.01.2018
18:59:38
18:59:38
смысл в том, что ты последовательно решаешь эту задачу исключая одно из чисел
а потом суммируешь все варианты. ну типа
короче - погугли) должно зайти
Vitaliy Nameless25.01.2018
19:01:12
19:01:12
Не совсем а немного
Aragaer25.01.2018
19:01:21
19:01:21
не-не, это существенно
набор чисел, из которых можно состыковывать - от x до x+k-1 - любое целое из этого интервала
Vitaliy Nameless25.01.2018
19:03:14
19:03:14
Разве? Там вроде дискретные входные данные
Aragaer25.01.2018
19:03:40
19:03:40
сначала на вход идут числа - от 1 до k
impl25.01.2018
19:03:44
19:03:44
А если сначала убирать большие числа?
Aragaer25.01.2018
19:03:52
19:03:52
как только в сумме наберется x или больше, оно идет на второй этап
impl25.01.2018
19:03:52
19:03:52
Потом суммировать
Aragaer25.01.2018
19:04:00
19:04:00
ноль нет
Aragaer25.01.2018
19:04:40
19:04:40
то есть число, которое прилетает с первого этапа на второй может быть от x (если все посылки по 1 кг) до x+k-1 (x-1 посылка по 1 кг, последняя k кг)
impl25.01.2018
19:04:43
19:04:43
Прямо как программисты
GoogleVitaliy Nameless25.01.2018
19:05:09
19:05:09
А
Мира25.01.2018
19:06:10
19:06:10
Пойду писать говнокод
Aragaer25.01.2018
19:06:18
19:06:18
дальше такой момент - можно считать, что в результате все посылки имеют одинаковый вес (плюс-минус 1)
Aragaer25.01.2018
19:07:11
19:07:11
в смысле мешки
impl25.01.2018
19:07:18
19:07:18
Придумал стартап и забросил
Aragaer25.01.2018
19:07:47
19:07:47
пусть они все по x, значит мы пытаемся y делить на x. Если остаток получается меньше, чем k*частное, то можно набрать ровно вес y
impl25.01.2018
19:07:56
19:07:56
Соц. сеть
Aragaer25.01.2018
19:09:00
19:09:00
дизайн надо в последнюю очередь делать
GoogleAragaer25.01.2018
19:09:09
19:09:09
а зачем нужны эти соцсети-то?
Мира25.01.2018
19:09:17
19:09:17
Там вроде мистер фримен собирался делать соц сеть в виде интернет государства со своим президентом и прочей шелухой мол даже зарплата будет
impl25.01.2018
19:09:41
19:09:41
Лоол
impl25.01.2018
19:09:57
19:09:57
Мистера фримена давно нет
Мира25.01.2018
19:10:19
19:10:19
относительно недавно новый ролик вышел ты шо?
impl25.01.2018
19:10:20
19:10:20
ФСБ завербовала
Мира25.01.2018
19:11:25
19:11:25
Не параной
Andrey25.01.2018
19:13:37
19:13:37
Ну, лол. Я подразумеваю перебор всех возможных комбинаций этих чисел.
Если и ты тоже, то, во-первых, составление всех комбинаций точно займет >1 секунды, а во-вторых, я не думаю, что на таких олимпиадах будут давать задачи, где нужен будет перебор (ну, или как-то может пригодиться).
С помощью itertools легко сделать перебор всех вариантов, которые могут подойтиМира25.01.2018
19:14:42
19:14:42
уютненько
Andrey25.01.2018
19:14:49
19:14:49
Да, мне тоже кажется, что эта задача красиво с помощью динамического программирования решается
Aragaer25.01.2018
19:22:35
19:22:35
то есть мое решение вам не нравится, потому что слишком простое?
смотри, пусть есть некоторое решение с числами x1, x2, x3, x4. Можно перераспределить числа так, чтобы сначала шли только числа N, а потом только N+1
это относится к любому набору валидных контейнеров
я как увидел mccme в урле, сразу понял, что задача не про перебор, а про математику
GoogleAragaer25.01.2018
19:24:57
19:24:57
мцнмо это не такое место, где надо тупо фигачить алгоритмы
крч
вес одного пакета может быть от x до x+k-1
вес двух пакетов может быть от 2x до 2x+2k-2
и так далее
мы получаем интервалы внутри которых можно из пакетов набрать любой вес и интервалы, в которых вес не набрать
и вопрос в том, попадает y внутрь такого интервала или нет. Если не попадает, то минимум это первая запись в следующем интервале, а если попадает, то мы можем это набрать ровно
например, если x = 7, k = 2, y = 20, то один пакет может весить 7 или 8, два пакета могут весить 14, 15 или 16, а вес трех пакетов минимум 21. Значит ответ 7 7 7 = 21
если бы k=4, то тогда 1 пакет весит 7, 8, 9 или 10 и можно получить ответ 10 10 = 20
Sergey25.01.2018
19:35:20
19:35:20
ооо. То, что мне нужно. Не додумался, что можно эту формулу использовать и дальше (2x, 3x и т.д.).
вес двух пакетов может быть от 2x до 2x+2k-2
мы получаем интервалы внутри которых можно из пакетов набрать любой вес и интервалы, в которых вес не набрать
Спасибо!
Aragaer25.01.2018
19:36:59
19:36:59
итого мы считаем так:
i = y / x
if y - i * x > i * k:
return [x] * (i + 1)
m = y / i
result = [m] * (y % i)
result.extend([m+1] * (i - y % i))
return result
... вроде чот такое
Открыть в Telegram