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

@Andreer · Регистрация: 04.01.2020

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

Недавно Алексей устроился на работу в крупную IT-компанию. Ему предложили поработать над
групповым проектом. До этого у него уже было много успешных проектов, но в этот раз всё шло
не по плану.
Алексей долго пытался найти причину всех неудач. В итоге он пришел к выводу, что его группа
несбалансированна. Он считает, что i-й человек в компании характеризуется числом ai
. Тогда в его
понимании, группа сбалансирована, если для любого целого m > 1 и любой пары разных людей
(i, j) в группе верно, что остатки от деления чисел ai и aj на m различаются.
Алексей обратился со своими соображениями к руководству. Они были бы рады согласиться на
реформы, но для начала хотели бы оценить все риски. Помогите Алексею убедить руководство, для
этого требуется найти минимальное количество сбалансированных групп, на которое можно разбить
всех работников компании.
Формат входных данных
В первой строке задано одно целое число n (2 6 n 6 200 000) — количество работников в компании.
Во второй строке заданы n целых чисел a1, a2, . . . , an (1 6 ai 6 109
) — числа, характеризующие
работников.
Формат выходных данных
Выведите одно число — минимальное количество сбалансированных групп, на которое можно
разбить всех работников компании.
Примеры
стандартный ввод стандартный вывод
4
1 2 3 1
3
5
6 1 2 5 3
3
6
1 1 2 2 1 1
4
Замечание
В первом примере работников можно разбить на группы 4 способами: {(1),(2),(3),(4)}, {(1, 2),
(3),(4)}, {(1),(2, 4),(3)}, {(1),(2, 3),(4)}. Первый и третий работник не могут быть в одной группе
так как остатки от деления a1 и a3 на 2 совпадают. Первый и четвёртый работник не могут быть
в одной группе так как остатки от деления a1 и a4 на 7 совпадают. Третий и четвёртый работник
не могут быть в одной группе так как остатки от деления a3 и a4 на 2 совпадают. Таким образом,
ответ на данный тест равен 3

@pythonbeginner · 08.01.2020, 12:58

Andreer, какая задача?

@eaa · 08.01.2020, 14:14

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

В первом примере работников можно разбить на группы 4 способами

Почему на 4?

@Andreer · 08.01.2020, 16:00 **[ТС]**

вот эта задача,pythonbeginner

Добавлено через 13 секунд
eaa, там все написано

@eaa · 08.01.2020, 17:09

Так чтоли?

Python
1
2
n = input()
print(sum([int(x) % 2 for x in input().split()]))

@Andreer · 09.01.2020, 10:36 **[ТС]**

eaa, проходит 9 тестов, если считать количество нечетных и чётных и выбирать большее, то 15

@eaa · 09.01.2020, 11:44

Python
1
2
3
n = int(input())
s = sum([int(x) % 2 for x in input().split()])
print(max(n-s, s))

@Andreer · 09.01.2020, 14:37 **[ТС]**

eaa, 15 тестов, как я и говорил)

@eaa · 10.01.2020, 14:35

рассмотрите такие примеры:

2
5 8

2
9 14

@Andreer · 10.01.2020, 16:24 **[ТС]**

все, я сдал на 100, отбой

Новые блоги и статьи Все статьи Все блоги /
Вывод данных через динамический список в справочнике Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .

@Andreer 1 / 1 / 0 Регистрация: 04.01.2020 Сообщений: 25

	Вычислить минимальное количество сбалансированных групп, на которое можно разбить всех работников компании 08.01.2020, 12:16. Показов 3204. Ответов 9 Метки нет (Все метки) Недавно Алексей устроился на работу в крупную IT-компанию. Ему предложили поработать над групповым проектом. До этого у него уже было много успешных проектов, но в этот раз всё шло не по плану. Алексей долго пытался найти причину всех неудач. В итоге он пришел к выводу, что его группа несбалансированна. Он считает, что i-й человек в компании характеризуется числом ai . Тогда в его понимании, группа сбалансирована, если для любого целого m > 1 и любой пары разных людей (i, j) в группе верно, что остатки от деления чисел ai и aj на m различаются. Алексей обратился со своими соображениями к руководству. Они были бы рады согласиться на реформы, но для начала хотели бы оценить все риски. Помогите Алексею убедить руководство, для этого требуется найти минимальное количество сбалансированных групп, на которое можно разбить всех работников компании. Формат входных данных В первой строке задано одно целое число n (2 6 n 6 200 000) — количество работников в компании. Во второй строке заданы n целых чисел a1, a2, . . . , an (1 6 ai 6 109 ) — числа, характеризующие работников. Формат выходных данных Выведите одно число — минимальное количество сбалансированных групп, на которое можно разбить всех работников компании. Примеры стандартный ввод стандартный вывод 4 1 2 3 1 3 5 6 1 2 5 3 3 6 1 1 2 2 1 1 4 Замечание В первом примере работников можно разбить на группы 4 способами: {(1),(2),(3),(4)}, {(1, 2), (3),(4)}, {(1),(2, 4),(3)}, {(1),(2, 3),(4)}. Первый и третий работник не могут быть в одной группе так как остатки от деления a1 и a3 на 2 совпадают. Первый и четвёртый работник не могут быть в одной группе так как остатки от деления a1 и a4 на 7 совпадают. Третий и четвёртый работник не могут быть в одной группе так как остатки от деления a3 и a4 на 2 совпадают. Таким образом, ответ на данный тест равен 3 0

@pythonbeginner 26 / 25 / 6 Регистрация: 20.12.2019 Сообщений: 135
	08.01.2020, 12:58
	Andreer, какая задача? 0

@Andreer 1 / 1 / 0 Регистрация: 04.01.2020 Сообщений: 25
	08.01.2020, 16:00 [ТС]
	вот эта задача,pythonbeginner Добавлено через 13 секунд eaa, там все написано 0

@Andreer 1 / 1 / 0 Регистрация: 04.01.2020 Сообщений: 25
	09.01.2020, 10:36 [ТС]
	eaa, проходит 9 тестов, если считать количество нечетных и чётных и выбирать большее, то 15 0

@Andreer 1 / 1 / 0 Регистрация: 04.01.2020 Сообщений: 25
	09.01.2020, 14:37 [ТС]
	eaa, 15 тестов, как я и говорил) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	10.01.2020, 14:35
	рассмотрите такие примеры: 2 5 8 2 9 14 0

@Andreer 1 / 1 / 0 Регистрация: 04.01.2020 Сообщений: 25
	10.01.2020, 16:24 [ТС]
	все, я сдал на 100, отбой 0