Минимальное количество яблок, которое нужно собрать с деревьев, чтобы гарантировать M красных яблок.

Существуют разные виды яблонь в четырех направлениях (восток, запад, север, юг), на которых могут расти как красные, так и зеленые яблоки, так что на каждом дереве растет ровно K яблок, следующим образом:

• N – количество деревьев к северу, на которых нет красных яблок.
• S – количество деревьев южнее, на которых не растут зеленые яблоки.
• W – количество деревьев на западе с красными яблоками.
• E – количество деревьев на востоке с зелеными яблоками.

Однако цвета яблок невозможно различить вне дома. Итак, задача состоит в том, чтобы найти минимальное количество яблок, которое нужно собрать с деревьев, чтобы гарантировать M красных яблок. Если это невозможно, выведите -1.

Примеры:

Input: M = 10, K = 15, N = 0, S = 1, W = 0, E = 0
Output: 10
Explanation: It simply gets 10 apples from the 1st south tree

Input: M = 10, K = 15, N = 3, S = 0, W = 1, E = 0
Output: -1
Explanation: There are no red apples in the South, North and East. But in the West there are atleast 1 red apple and total tree is 1, So, total no. of guaranteed red apple is 1 * 1 = 1 which is less than M.

Подход: Каждое яблоко на юге гарантирует, что оно красное. Итак, сначала возьмите яблоко с юга. На Востоке и на Западе на каждом дереве есть как минимум 1 красное яблоко. Поэтому гарантированно считается, что на каждом дереве на востоке и западе висит только по 1 красному яблоку. Для севера нет красного яблока, так что пренебрегайте этим. Выполните следующие шаги, чтобы решить проблему:

• Если M меньше S*K , то выведите M.
• В противном случае, если M меньше, чем равно S*K+E+W , тогда выведите S*K + (MS*K) * K
• В противном случае напечатайте -1.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)