Задача
Измерение веса предмета осуществляется с помощью лабораторных весов. С помощью набора из $7$ гирь весом $1$ г, $3$ г, $9$ г, $27$ г, $81$ г, $243$ г и $729$ г можно измерить вес любого предмета с целым весом от $1$ до $1093$ г единственным способом. Например, для измерения предмета весом $4$ г необходимо на одну чашу положить гири в $1$ и $3$ г, а на другую сам предмет, а, скажем, для предмета весом $68$ г на чашку с ним добавляются гири в $1$, $3$ и $9$ г, а на другую — гиря в $81$ г.
Определите, сколько гирь из данного набора необходимо использовать для взвешивания предмета заданного веса.
Входные данные
Одно натуральное число $x \ (1 \leqslant x \leqslant 1000)$ — вес предмета.
Выходные данные
Вывести количество гирь, необходимых для взвешивания данного предмета.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 4 | 2 |
| 2 | 68 | 4 |
| 3 | 27 | 1 |
| 4 | 555 | 5 |
| 5 | 1000 | 4 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> #define NUM 3 #define POW 729 using namespace std; int nearest(int weight) { for (int i = 1; i < POW; i*=NUM){ if (abs(i - weight) < abs(i*NUM - weight)) { return i; } } } int main() { int right_bowl, left_bowl = 0, count = 0; cin >> right_bowl; while (right_bowl != left_bowl) { if (right_bowl > left_bowl) { left_bowl += nearest(abs(right_bowl - left_bowl)); } else right_bowl += nearest(abs(right_bowl - left_bowl)); count++; } cout << count; } |
Решение
Пусть предмет располагается на правой чаше весов. Тогда на левой чаше первым делом мы должны расположить ближайшую по весу гирю. Если этой гири оказывается недостаточно для уравновешивания весов, тогда мы добавляем на левую чашу еще одну гирю, вес которой будет ближе всех к разности весов на чашах. Повторяем операцию, пока чаши не уравняются. Если же вес левой чаши будет больше правой, то по такому же принципу добавляем гири на правую чашу. И с каждым добавлением гири увеличиваем счетчик, значение которого выводится при уравновешивании весов. И хоть такой ход решения не полностью удовлетворяет условию задачи, так как в некоторых случаях одни и те же гири используются дважды, тем не менее ответ всегда будет совпадать с ответом решения исходной задачи. Это было проверено с помощью сайта, который сравнил результаты работы двух программ, которые выдают все ответы моего решения и правильного.
Ссылки
- Код на ideone
- Задача на e-olymp
- Засчитанное решение на e-olymp
— Каждая гиря может либо использоваться, либо нет. Для вас это означает, что можно построить решение с линейной сложностью от количества гирь. Сейчас сложность квадратичная.
— Текущее решение тесты проходит, но находит что-то не то. Например, если мы хотим получить 5, то 5 = 9-3-1. Ваше решение находит 5 = 3+1+1. Количество совпадает, но найден не тот набор. Можно попробовать доказать, что исходная задача и та, которую вы решили всегда имеют одинаковые ответы.
— Для чисел в условии можно использовать laTeX, но не жирній шрифт.
— Стоит избавиться от magic numbers в коде.
— Зачем массив weights[]? Это же степени тройки.
— Кстати, я решал так