Question

Дана последовательность N целых положительных чисел. Необходимо определить количество пар элементов этой последовательности, сумма которых делится на m = 60 и при этом хотя бы один элемент из пары больше b = 40. Описание входных и выходных данных. В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Пример входных данных: 6 30 30 150 20 40 100 Пример выходных данных для приведённого выше примера входных данных: 3 Пояснение. Из данных шести чисел можно составить три пары, удовлетворяющие условию: (30, 150), (30, 150), (20, 100). У пар (30, 30) и (20, 40) сумма делится на 60, но оба элемента в этих парах не превышают 40. Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N. Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную только по времени — 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла. Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите используемый язык программирования и его версию. НУЖНО НА ЯЗЫКЕ C++

Answer 1

Ответ:

#include <iostream>

using namespace std;

signed main() {

  int n;

  cin >> n;

  int a[n];

  for(int i = 0; i < n; i++)

      cin >> a[i];

  int cnt = 0;

  for(int i = 0; i < n; i++)

      for(int j = i+1; j < n; j++)

          if((a[i] - a[j]) % 80 == 0 && max(a[i],a[j]) > 100)

              cnt++;

  cout << cnt;

}

Answer 2

Для решения данной задачи на C++ вы можете воспользоваться следующим алгоритмом:

1. Создайте две переменные: `count` для подсчета пар и `hasGreater` для отслеживания наличия элемента больше 40 в паре.

2. Создайте массив для хранения частоты чисел от 1 до 10 000. Инициализируйте его нулями.

3. Считайте N и создайте цикл для считывания N чисел в массив. Внутри цикла обновляйте частоты для каждого числа в массиве.

4. Затем, начните внутренний цикл, который будет перебирать пары чисел. Перебирайте все числа от 41 до 10 000 и для каждого числа `i`, проверяйте, есть ли в массиве частот число `60 - i` (поскольку сумма чисел в паре должна быть равна 60).

5. Если `60 - i` существует в массиве частот, проверьте, есть ли числа больше 40 в паре. Если да, увеличьте `count` и установите `hasGreater` в true.

6. После внутреннего цикла, если `hasGreater` равно true, увеличьте `count` на 1 (потому что каждая пара с числом больше 40 вносит свой вклад в результат).

7. Выведите значение `count` как ответ.

Пример кода на C++:

#include 
#include

using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector frequency(10001, 0);
    
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        frequency[num]++;
    }
    
    int count = 0;
    
    for (int i = 41; i <= 10000; ++i) {
        if (frequency[i] > 0 && frequency[60 - i] > 0) {
            if (i > 40) {
                count += frequency[i] * frequency[60 - i];
            }
            else {
                count += frequency[i] * frequency[60 - i];
                count += frequency[i] * frequency[60 - i];
            }
        }
    }
    
    cout << count << endl;
    
    return 0;
}

Этот код считывает входные данные, подсчитывает частоту чисел и затем перебирает возможные пары, учитывая условия задачи. Он эффективен как по времени, так и по памяти, и должен решить задачу.