Выбрать несколько заданных чисел таким образом, чтобы сумма выбранных чисел была кратна N

@Chesir · Регистрация: 02.01.2023

Студворк — интернет-сервис помощи студентам

Добрый день, решаю билеты к сессии первого курса, но с одним билетом я уже совсем голову сломал. Помогите, пожалуйста.

Входные данные содержат N положительных целых чисел. Эти числа не обязательно отличаются друг от друга (может получиться так, что два или более из них будут равны). Ваша задача – выбрать несколько заданных чисел (1 ≤ несколько ≤ N) таким образом, чтобы сумма выбранных чисел была кратна N, т.е. равнялась N · k для некоторого целого k.
Исходные данные
Первая строка входа содержит целое число N (1 ≤ N ≤ 10000). Каждая из следующих N строк содержит по одному целому числу из заданного набора. Каждое из этих чисел положительное и не превышает 15000.
Результат
Если целевой набор чисел не может быть найден, выведите единственное число 0. В противном случае, выведите количество выбранных чисел в первой строке, а далее сами выбранные числа (каждое в отдельной строке) в произвольном порядке.
Если существует более одного набора чисел с требуемыми свойствами, можно вывести любой из них.

@Chesir · 06.01.2023, 19:42 **[ТС]**

исходные данные |результат
5 |2
1 |2
2 |3
3
4
1

Байт · 07.01.2023, 20:03

Chesir, с входными данными чушь какая-то. А пример только запутывает.
Тем не менее.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char x[N] = { 0};
a[N];
x[N-1] = 1; // Этот массив моделирует длинное двоичное число
bool suss = false;
while(true) {
  int s =0;
  for(int i=0; i< N; i++)
    if (x[i]) s += a[i];
  if (s % k == 0) {
     suss = true;
     break;
  }
 int j = N-1;  // Здесь мы к этому числу прибавляет 1
 for (; j>= 0 j--)
    if (x[j] ==0) break;
 if (j <0) break;  //Конец перебора suss = false 
 x[j++]=1;
 for (; j < N; j++)
   x[j] = 0; 
}
// Если suss == true выводишь те элементе массива, для которых x[j] J= 0

Это называется "Битовая шкала", которая описывает подмножество.
Полезный метод. Для малых множеств можно использовать просто число целого типа.
В std имеется контейнер map, но думаю тебе буде полезнее увидеть такую, низкоуровневую, работу с подмножествами.

Добавлено через 6 минут
Кстати, твою задачу Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной (почему код не проходит тесты?)
тоже можно тоже решить через битовую шкалу. Правда про эффективность здесь ничего не могу сказать. Это тупой брут-форс

@DrScorp · 10.01.2023, 06:28

Пожалуйста,обьясните чуть-чуть поподробнее этот метод и почему мы к числу прибавляем 1 (в 13 строчке)

Байт · 10.01.2023, 15:03

Сообщение от DrScorp

почему мы к числу прибавляем 1 (в 13 строчке)

Просто перебираем все возможные значения. Моделируем сложение столбиком (+1) для длинного двоичного числа,

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Chesir 0 / 0 / 0 Регистрация: 02.01.2023 Сообщений: 4

	Выбрать несколько заданных чисел таким образом, чтобы сумма выбранных чисел была кратна N 06.01.2023, 11:42. Показов 1742. Ответов 4 Метки c++, c++ 1 курс (Все метки) Добрый день, решаю билеты к сессии первого курса, но с одним билетом я уже совсем голову сломал. Помогите, пожалуйста. Входные данные содержат N положительных целых чисел. Эти числа не обязательно отличаются друг от друга (может получиться так, что два или более из них будут равны). Ваша задача – выбрать несколько заданных чисел (1 ≤ несколько ≤ N) таким образом, чтобы сумма выбранных чисел была кратна N, т.е. равнялась N · k для некоторого целого k. Исходные данные Первая строка входа содержит целое число N (1 ≤ N ≤ 10000). Каждая из следующих N строк содержит по одному целому числу из заданного набора. Каждое из этих чисел положительное и не превышает 15000. Результат Если целевой набор чисел не может быть найден, выведите единственное число 0. В противном случае, выведите количество выбранных чисел в первой строке, а далее сами выбранные числа (каждое в отдельной строке) в произвольном порядке. Если существует более одного набора чисел с требуемыми свойствами, можно вывести любой из них. 0

@Chesir 0 / 0 / 0 Регистрация: 02.01.2023 Сообщений: 4
	06.01.2023, 19:42 [ТС]
	исходные данные \|результат 5 \|2 1 \|2 2 \|3 3 4 1 0

@DrScorp 0 / 0 / 0 Регистрация: 10.01.2023 Сообщений: 1
	10.01.2023, 06:28
	Пожалуйста,обьясните чуть-чуть поподробнее этот метод и почему мы к числу прибавляем 1 (в 13 строчке) 0