Сакурако — молода програмістка, яка працює над проєктом у сфері робототехніки.
Вона побудувала три розумні контейнери, кожен з яких спочатку має , та м'ячів відповідно. Контейнери призначені для передачі м'ячів один одному, і її завдання — написати програму, яка зробить кількість м'ячів у всіх трьох контейнерах однаковою.
Сакурако може наказати непорожньому контейнеру витягти один м'яч і передати його іншому. Однак їй цікаво дізнатися, чи можливо взагалі збалансувати контейнери, і якщо так, то скільки рухів це займе. Чи можете ви допомогти їй розробити ефективне рішення?
Припустимо, у неї є три контейнери; перший контейнер має м'яч, другий контейнер має м'ячі, а третій контейнер має м'яч. Нижче ви можете знайти ілюстрацію для такого прикладу.
Жовті стрілки показують м'яч, який ми беремо, і куди ми його кладемо. У цьому випадку ми виконуємо дві операції.
Єдиний рядок містить три цілі числа , та (0\le a, b, c\le 10^8).
Якщо неможливо зробити кількість м'ячів у всіх трьох контейнерах однаковою, виведіть "-1".
В іншому випадку виведіть мінімальну кількість рухів, необхідних для балансування м'ячів між контейнерами.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
У другому прикладі можна показати, що неможливо розподілити кулі між контейнерами, як описано в умові.
У третьому прикладі всі контейнери порожні, що означає, що у всіх них однакова кількість куль; отже, вихідні дані дорівнюють нулю.
У четвертому прикладі ми можемо дотримуватися стратегії, описаної нижче:
(\textcolor{red}{12}, 0, 0) | (11, \textcolor{red}{1}, 0) | |
(\textcolor{red}{11}, 1, 0) | (10, 1, \textcolor{red}1) | |
(\textcolor{red}{10}, 1, 1) | (9, \textcolor{red}2, 1) | |
(\textcolor{red}{9}, 2, 1) | (8, 2, \textcolor{red}2) | |
(\textcolor{red}{8}, 2, 2) | (7, \textcolor{red}3, 2) | |
(\textcolor{red}{7}, 3, 2) | (6, \textcolor{red}4, 2) | |
(\textcolor{red}{6}, 4, 2) | (5, 4, \textcolor{red}3) | |
(\textcolor{red}{5}, 4, 3) | (4, 4, \textcolor{red}4) |
що займає у нас рівно операцій. Ми можемо довести, що неможливо збалансувати контейнери менш ніж за операцій.
Ви отримаєте щонайменше балів, якщо ваше рішення працює правильно для b=0 та c=0; тобто, другий і третій контейнери порожні.
Ви отримаєте щонайменше балів, якщо ваше рішення працює правильно для b= 2 \cdot a та c = 3 \cdot a.