😱 Типа простые задачки...

На тренировках столкнулся, как может показаться, с простой задачей.
Все вещи и имена изменены. 😎

И так школьная задачка по информатике. 😱

У меня в шкафу в двух ящиках в одном лежат футболки и другом шорты.
Футболки и шорты двух разных цветов. Для простоты - красные и синие.
Известно количество по каждому цвету A и B - футболки, С и D - шорты.
Вопрос: Если вытаскивать "неглядя", сколько минимум нужно вытащить футболок и шорт, что бы гарантированно получить пару одного цвета.
(Выдать надо пару [N, M] - кол-во футболок и шорт). 🩳👕

И так что бы гарантированно получить футболки разных цветов надо вытащить max(A, B)+1, а шорт - max(C, D)+1.
Т.о. что бы создать пару надо вытащить только одни шорты и одну футболку ответственно:

[max(A, B)+1, 1] и [1, max(C, D)+1]

И ответом будет вариант где общее кол-во вещей меньше.

Вроде все очевидно, но этот вариант решения у меня не прошел. 😫
Я задумался почему? Скорее всего что это гарантированный, но не минимальный вариант. 🤦🏻‍♂️

Как можно еще гарантированно получить пару одного цвета?
Т.к. мы знаем кол-во вещей каждого цвета то можно взять на одну вещь больше - что гарантирует нам два цвета.
Если у нас A красных футболок мы берем A + 1 футболок, а шорт берем С + 1.
Т.о. получаем еще варианты

[A + 1, C + 1] и [B + 1, D + 1]

Теперь надо выбирать из этих четырех вариантов.

Кстати еще надо не забыть про крайний случай, т.к. нигде не сказано что кол-во больше 0;
Т.о. варианты актуальны если:

[max(A, B) + 1, 1] - A > 0 и B > 0
[1, max(C, D) + 1] - C > 0 и D > 0
[A + 1, C + 1] - В > 0 и D > 0
[B + 1, D + 1] - A > 0 и C > 0

т.е. в первых двух случаях есть из чего выбирать, а во вторых - точно присутствует второй цвет. 🤯

Ну и выбираем вариант где N + M будет минимальной.

Как вам задачка? Хочется обратно в школу ⁉️

#algorithm_training

Баста карапузики, кончилися танцы!

Сегодня пытался сделать задачи по тренировкам.
Сейчас понимаю что это была не очень хорошая идея. Сил хватило только на половину.
Больше делать не буду, тех что есть должно хватить на сертификат.
На этом мое участие в тренировках подошла к концу.

Такое ощущение что выходные даже не начались 👿

#algorithm_training