Question

Степан має 12 монет, кожна з яких важить різне ціле число грамів, та терези які показують три стани: вага зліва дорівнює вазі справа вага однієї шальки більше ніж другої, але не більше ніж у два рази 3 вага однієї шальки більше ніж другої в два або більше разів якщо він покладе на обидві шальки терезів по дві монети, то завжди переважає та шалька, на якій лежить найважча з Цих монет, причому терези показують, що вага більше в два або більше разів. Потрібно знайти мінімальну можливу вагу найважчої монети.

Answer 1

Ответ:

Пошаговое объяснение:

Запишемо всі можливі ваги монет в порядку зростання:

a1 < a2 < a3 < ... < a12

Далі, помітимо, що якщо вага однієї монети більше в два або більше разів від ваги іншої монети, то цю пару монет можна одразу відкинути, бо щоб перевірити, яка з них є найважчою, потрібно порівняти обидві монети із іншим набором монет, що неможливо.

Таким чином, в результаті відкидаємо можливі пари монет з різницею в дві та більше разів:

a1 < a2 < a3 < ... < a6 < 2*a1

a6*2 < a7 < a8 < ... < a12

Тепер додатково відкинемо комбінації монет, які не задовольняють умови, що вага однієї шальки більше ніж другої, але не більше ніж у два рази. Для цього покладемо на одну шальку терезів дві найлегші монети (a1 та a2), а на другу шальку покладемо такі монети, щоб вага однієї шальки була не менше у два рази від ваги іншої. Таким чином, терези мають показувати, що на одній шальці знаходяться монети a1 та a2, а на іншій - пара монет зі списку a3 ... a12.

Отримуємо такі комбінації монет:

a3 < a4 < a5 < 2*a2

a6*2 < a7 < a8 < ... < a12

Тепер додатково відкинемо комбінації монет, які не задовольняють умови, що вага однієї шальки більше ніж другої в два або більше разів. Для цього покладемо на одну шальку терезів дві найлегші монети з другого списку (a7 та a8), а на іншу шальку покладемо такі монети, щоб вага однієї шальки була не менше у два рази від ваги іншої. Таким чином, терези мають показувати, що на одній шальці знаходяться монети a7 та a8, а на іншій - пара монет зі списку a9 ... a12.

Отримуємо такі комбінації монет:

a3 < a4 < a5 < 2*a2

2*a8 < 2*a7 < a9 < ... < a12

Тепер залишилось знайти найбільшу монету зі списку a9 ... a12. Можна покласти на одну шальку терезів найлегшу монету з цього списку (a9), а на іншу шальку покласти найбільшу монету зі списку a3 ... a5 та монету a2 (так як ці три монети не можуть бути більш важкими за будь-яку монету зі списку a9 ... a12). Якщо переважить перша шалька - найважча монета знаходиться у списку a3 ... a5. Якщо переважить друга шалька - найважча монета знаходиться у списку a9 ... a12.

Отже, мінімальна можлива вага найважчої монети дорівнює максимальній вазі зі списку a3 ... a5 або a9 ... a12.

Answer 2

To find the minimum possible weight of the heaviest coin, we can use a binary search algorithm. We start by assuming that the weight of the heaviest coin is between 1 and the sum of all the coins' weights. We then repeatedly divide this range in half and check if it is possible to distribute the coins in a way that satisfies the given conditions. Here's how the binary search algorithm can be implemented: #### Algorithm: 1. Initialize the lower bound `left` as 1 and the upper bound `right` as the sum of all the coins' weights. 2. While `left` is less than `right`, do the following: - Calculate the mid-point `mid` as the average of `left` and `right`. - Check if it is possible to distribute the coins in a way that satisfies the given conditions with the heaviest coin having a weight of `mid`. - If it is possible, update `right` to `mid`. - If it is not possible, update `left` to `mid + 1`. 3. Return the value of `left` as the minimum possible weight of the heaviest coin. Let's apply this algorithm to the given problem: #### Example: Stepan has 12 coins, each with a different integer weight in grams. The balance scale shows three states: 1. The weight on the left side is equal to the weight on the right side. 2. The weight on one side is greater than the weight on the other side, but not more than twice as much. 3. If Stepan puts two coins on each side of the scale, the side with the heaviest coin always outweighs the other side by at least twice as much. We need to find the minimum possible weight of the heaviest coin. #### Solution: 1. Initialize `left` as 1 and `right` as the sum of all the coins' weights. - `left = 1` - `right = sum of all coin weights` 2. While `left` is less than `right`, do the following: - Calculate `mid` as the average of `left` and `right`. - Check if it is possible to distribute the coins in a way that satisfies the given conditions with the heaviest coin having a weight of `mid`. - If it is possible, update `right` to `mid`. - If it is not possible, update `left` to `mid + 1`. 3. Return the value of `left` as the minimum possible weight of the heaviest coin. Let's go through the steps of the algorithm: 1. Initial values: - `left = 1` - `right = sum of all coin weights` 2. Iteration 1: - `mid = (left + right) / 2` - Check if it is possible to distribute the coins in a way that satisfies the given conditions with the heaviest coin having a weight of `mid`. - If it is possible, update `right` to `mid`. - If it is not possible, update `left` to `mid + 1`. 3. Repeat iteration 2 until `left` is no longer less than `right`. By applying this algorithm, we can find the minimum possible weight of the heaviest coin.