Кто может объяснить суть задачи Три попарных максимума?

Question

[Максим Яковенко]

Дана такая задача:

Вам даны три положительных (то есть строго больших, чем 0) целых числа x, y и z.
Ваша задача — найти такие положительные целые числа a, b и c, что x=max(a,b), y=max(a,c) и z=max(b,c), или определить, что невозможно найти такие значения a, b и c.

Не смог решить сам. Поэтому пошел читать разбор. Не логика рассуждений, совсем для меня не очевидна. Возможно кто-то сможет помочь в ее разъяснении.

Comments

[dmshar]

Есть-ли условие на взаимоотношения x,y,z? Допускается ли попарные равенства между a,b,с ?

[Максим Яковенко]

dmshar, четкого условия нет. Можно только предположить, что x ≤ y ≤ z . Ограничений по равенствам нет.

Answer 1

[dmshar]

Если действительно
четкого условия нет. Можно только предположить, что x ≤ y ≤ z . Ограничений по равенствам нет.

то рассуждаем следующим образом:
X максимум из a и b, Для определенности, возьмем либо a < b либо a=b (раз равенства допускаются).
Т.е. уже имеем b=Х. Для a должно выполняться условие a<=b.
Из условий Y=max(a,c), Z=max(b,c) и условия a<=b следует, что с>=b. Тогда с=Y, с=Z.

Следовательно, условию удовлетворяют только такие пары, у которых либо все три заданных числа X,Y,Z равны между собой, либо X < Y=Z и тогда b=Х, с=Y=Z, a - произвольное число, меньшее либо равное b.

Алгоритм свелся к тому, что вы проверяете, выполняются-ли указанные условия и если одно из них выполняется, непосредственно получаете свои а,b и с без всякого подбора.

Comments

[Максим Яковенко]

Я так понимаю, что b=X, следует из допущенного равенства a=b?

Answer 2

[hint000]

Решение существует, когда
max(x, y) = max(y, z) = max(x, z),
И
{если min (x, y, z) < max(x, y, z), то должно быть min (x, y, z) > 1}.
Доказательство оставим в качестве домашнего упражнения. ;)

P.S. моё условие почти соответствует тому, что вывел dmshar, только записано в чуть более общей форме. Я не пользовался ограничением x ≤ y ≤ z.

Comments

[Максим Яковенко]

Нет, только то, что я описал выше.

[Максим Яковенко]

C доказательством у меня явные проблемы. Нужно теорию чисел подтянуть.

[hint000]

Максим Яковенко, max(x, y) = max(y, z) = max(x, z) эквивалентно условию, что два наибольших числа равны, либо все три равны. Подумайте минуту и поймёте, что это так.
Но dmshar, говоря

a - произвольное число, меньшее либо равное b

, упустил условие, что а>0, значит нужно добавить условие, что b>1. Это соответствует той части условия, которая у меня в фигурных скобках.

[Максим Яковенко]

hint000, вот тут не совсем понял логику рассуждений. Если b должен быть > 1, то мы же сломаем равенство max(x, y) = max(y, z) = max(x, z), или нет?

[hint000]

Максим Яковенко, вот не зря сказано: "утро вечера мудренее". На свежую голову понял, что условие в фигурных скобках лишнее. :) Потому что нигде не требуется, чтобы все три числа a, b, c были разными. В случае min (x, y, z) < max(x, y, z) будет решение:
с=max(x, y, z),
b=min (x, y, z),
a≤min (x, y, z), а значит можно выбрать частный случай a=b=min (x, y, z).

В случае min (x, y, z) = max(x, y, z) будет единственное решение:
a=b=с=x=y=z.

Answer 3

[Saboteur]

Вообще не понимаю проблемы. Тут нкиаких условий к xyz не указано.
Просто вычисляем abc, либо идем к преподу и уточняем условия

Comments

[dmshar]

Да нет, тут нечего уточнять.
Вопрос в том, как именно вычислить abc. Если ничего не придумать, то только полным перебором. Что грустно.
А логические рассуждения позволяют явно решить задачу, проверив несколько условий над xyz. И либо сразу принять решение о невозможности, либо сразу и однозначно получить искомые abc.
Кстати, в отличии от большинства "олимпиадных" задач, этой скорее всего можно придумать "случай из жизни".

[Saboteur]

то есть?

функция Max работает очень просто.
a=3
b=4
c=5

x=max(3,4) = 4
y=(3,5) = 5
z=(4,5) = 5

я не вижу никаких зависимостей для xyz между собой. Может у вас неполный текст задачи?

[dmshar]

Saboteur, Вопрос же в другом. (На оборот относительно вашего примера).
Задано
х=100, y=200, z=300.
Найти a, b, c, если известно, что x=max(a,b), y=max(a,c) и z=max(b,c)

[Saboteur]

А. ну тогда проще.
Ответ - невозможно гарантировано найти такие значения.

Из трех чисел всегда одно самое маленькое. И по вашим функциям, узнать значение самого маленького невозможно, поскольку x,y,z получаются из фунции max.
Можно попытаться вычислить какое именно значение самое маленькое, но учитывая, что в условиях не указано, что три числа не могут совпадать, это будет негарантировано.

Например:
а) a=1, b=2, c=3
у нас x=2, y=3, z=3
то есть значения А в списке нет в принципе.

б) a=2, b=2, c=3
Выходит x=2, y=3, z=3
снова неудача, вычислить какие два значения одинаковы - сложно.

в) a=3, b=3, c=3
выходит x=3, y=3, z=3
Тоже не можем определить было ли какое-то из a,b,c меньше, или все три одинаковые.

[hint000]

Saboteur,

Ответ - невозможно гарантировано найти такие значения.

Там всё чётко, при одних значениях x, y, z решение гарантированно есть и легко находится, при других значениях решения нет и это легко доказывается.

Из трех чисел всегда одно самое маленькое. И по вашим функциям, узнать значение самого маленького невозможно

В условиях не требуется однозначное соответствие, достаточно найти любые подходящие значения.

[Saboteur]

hint000,
Приведите пример x,y,z где гарантировано легко находится решение.

[dmshar]

10,10,10
1,10,10
1,1,10

[Saboteur]

ок.
1) 10,10,10
у вас a,b,c могут быть 10,10,1 или 10,10,2 или 10,10,10. Так где же истина?
то есть гарантировано вы ничего легко не находите.
Тоже самое и в других случаях.

[hint000]

Saboteur, ещё раз: в условиях задачи не требуется однозначное соответствие, достаточно найти любые подходящие значения. А любые подходящие находятся легко.
dmshar, вот 1,1,10 как раз неудачный пример, для него решения нет. Вы же в своём ответе правильно сформулировали: X < Y=Z, а случай 1,1,10 не соответствует.

[dmshar]

hint000, Да, ошибся, признаю.