6 ответов в теме

[Лэн]

Коллега поделилась задачей, которую её сыну 11-класснику на олимпиаде дали. Условие - во вложении, требования к результату - тоже.
Я думал-думал, так и не придумал, как её решить. Сводил к задаче о рюкзаке - в нужные требования вписаться не смог.
Может,у кого есть какие-то мысли?

Прикрепленные миниатюры

• 
• 
• 

[koraalex]

Я не понял, что хотят от одиннадцатиклассника. Я бы с такой задачей направил назад с требованием переделать ТЗ, прежде всего, чтобы по-русски было написано.

 

Додумываю:

1. В шапке задачи прописаны конкретные числа a,b,c и h.

2. Кнопки лифта можно жать сколько угодно раз.

3. "Если лифту понадобится вылететь..." - фактически "Если лифту дадут команду переместиться на несуществующий этаж..."

 

Далее, вся задача сводится к определению тройки чисел k, m, и n которые являются кратными множителями a, b и c, при которых достигается наибольшее число k*a+m*b+n*c<=h. Примечание в отношении возможного равенства чисел (двух или трёх) намекает на упрощение задачи (кстати, иной раз такое примечание может намекать на то, что задача в общем случае не имеет решения, но не тут). Подумаю...

Изменено: koraalex, 20 Декабрь 2023 - 15:47

[Лэн]

Я не понял, что хотят от одиннадцатиклассника. Я бы с такой задачей направил назад с требованием переделать ТЗ, прежде всего, чтобы по-русски было написано.

По-моему, все вполне очевидно:
Ты вводишь 3 числа в диапазоне 1-10^5. Программа на основании этого должна найти комбинацию для суммы из трех этих чисел (каждое число можно использовать сколько угодно раз), чтобы получилось максимально близко к 10^64.

[koraalex]

По-моему, все вполне очевидно:
Ты вводишь 3 числа в диапазоне 1-10^5. Программа на основании этого должна найти комбинацию для суммы из трех этих чисел (каждое число можно использовать сколько угодно раз), чтобы получилось максимально близко к 10^64.

Только не к 10^64, а к четвёртому, которое меньше 2^64.

[Лэн]

Только не к 10^64, а к четвёртому, которое меньше 2^64.

Да, всё так. Я просто изначально пытался решить её для h=2^64 как наибольшего числа.
И сверху ты все верно додумал - жать можно сколько угодно, это ж лифт

[KiberGus]

Вопрос все-таки до скольких этажей можно добраться, а не самый высокий, до которого можно добраться. Например при a=3, b=3, c=3, h=7 жобраться можно до 1, 3, 6 и 7. Ответ 4.

[GrGr]

Я бы попробовал в цикле посчитать целочисленные деления, предварительно проверив, что среди входных чисел нет взаимно кратных.

Типа, если a > b > c, то наш ответ будет h div a + (h - ia) div b + (h - ia - jb) div c +1 для каждого i  от 0 до h div a и j от 0 до h - ia div b. Правда, у меня ощущение, что для слишком больших чисел это все может считаться слишком долго.