Входные данные

В первой строке задано количество тестов $n \ (1 < n < 100)$. Каждый тест состоит из одной строки и содержит количество входных чисел $m \ (1 < m < 100)$, за которым следуют $m$ натуральных чисел. Все входные числа натуральные, не превышающие $10^6.$

Код

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main() {
    int n, m, sum;
    cin >> n;
    while(n-- > 0) {
        cin >> m; 
        int ns[m];
        for(int i = 0; i < m; i++) cin >> ns[i];
        sum = 0;
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);
        }
        cout << sum << endl;
    }
}

#include <iostream>

using namespace std;

int gcd(int a, int b) {

return b == 0 ? a : gcd(b, a%b);

}

int main() {

int n, m, sum;

cin >> n;

while(n-- > 0) {

cin >> m;

int ns[m];

for(int i = 0; i < m; i++) cin >> ns[i];

sum = 0;

for(int i = 0; i < m; i++) {

for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);

}

cout << sum << endl;

}

Решение

Алгоритм решения этой задачи очень простой: чтобы найти сумму НОД всех пар чисел в строке нужно сначала найти все сочетания по два числа из строки, потом посчитать НОД для каждой пары и сложить все НОД.

Задача

Измерение веса предмета осуществляется с помощью лабораторных весов. С помощью набора из $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

Код

#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;
}

#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

№	Входные данные	Выходные данные
1	3 4 10 20 30 40 3 7 5 12 3 125 15 25	70 3 35
2	2 3 12 7 8 4 5 14 25 11	6 10
3	4 4 5 6 7 8 4 8 6 2 9 3 2 15 6 5 12 25 29 19 11	7 11 6 10

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Натан Чачко

e-olymp 6941. Сумма НОД

Задача

Входные данные

Выходные данные

Тесты

Код

Решение

Ссылки

Related Images:

e-olymp 7110. Весы

Задача

Входные данные

Выходные данные

Тесты

Код

Решение

Ссылки

Related Images: