Question

На вход программы поступает последовательность из N натуральных чисел. Нужно выбрать из них произвольное количество чисел так, чтобы их сумма была максимальной и не делилась на 4. В результате программа должна вывести количество выбранных чисел и их сумму. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Входные данные: На вход программе подаётся натуральное число N (N  1000), а затем N натуральных чисел, каждое из которых не превышает 10000. Пример входных данных: 3 1 2 1 Выходные данные: Программа должна вывести два числа: сначала количество выбранных чисел, а затем их сумму. Пример выходных данных для приведённого примера входных данных: 2 3 паскаль

Answer 1

Var
  a, n, i, sum, c, min: integer;
 
begin
  sum := 0;
  c := 0;
  min := 10001;
  read(n);
  for i := 1 to n do begin
    read(a);
    sum := sum + a;
    c := c + 1;
    if(a < min) and (a mod 4 <> 0) then min := a;
  end;
  if(sum mod 4 = 0) and (min <> 10001) then begin sum := sum - min; c := c - 1; end;
  if(sum mod 4 = 0) then begin write(0); exit; end;
  writeln(c, ' ', sum);
 end.

Answer 2

Задача

Вам необходимо выбрать произвольное количество чисел из заданной последовательности натуральных чисел таким образом, чтобы их сумма была максимальной и не делилась на 4. В результате программы нужно вывести количество выбранных чисел и их сумму. Если невозможно получить требуемую сумму, ответом должно быть 0.

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

На вход программе подается натуральное число N (N ≤ 1000), а затем N натуральных чисел, каждое из которых не превышает 10000.

Пример входных данных: ``` 3 1 2 1 ```

Решение

Для решения данной задачи можно использовать жадный алгоритм. Начнем с суммы, равной 0, и будем последовательно добавлять числа из последовательности, начиная с самого большого. При этом будем проверять, чтобы сумма не делилась на 4. Если сумма делилась на 4, будем пропускать текущее число и переходить к следующему. Если сумма не делилась на 4, будем добавлять текущее число к сумме.

Пример решения на языке Python: ```python def max_sum(numbers): numbers.sort(reverse=True) # Сортируем числа в убывающем порядке total_sum = 0 count = 0

for num in numbers: if (total_sum + num) % 4 != 0: # Проверяем, чтобы сумма не делилась на 4 total_sum += num count += 1

return count, total_sum

# Чтение входных данных n = int(input()) numbers = list(map(int, input().split()))

# Вызов функции и вывод результатов result = max_sum(numbers) print(result[0], result[1]) ```

Пример вывода для приведенного примера входных данных: ``` 2 3 ```

Объяснение решения

В данном примере входных данных у нас есть 3 числа: 1, 2 и 1. Мы сортируем их в убывающем порядке, получая последовательность [2, 1, 1]. Затем мы последовательно добавляем числа к сумме, начиная с самого большого. Первое число 2 добавляется к сумме, так как она не делится на 4. Затем мы добавляем следующее число 1, так как сумма 3 также не делится на 4. Последнее число 1 мы пропускаем, так как сумма 4 делится на 4. В итоге, мы выбираем два числа (2 и 1) и их сумма равна 3.