Алгоритм или решение по этой задаче

@AndreShah · Регистрация: 01.08.2019

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

У Васи есть массив A длины N из неотрицательных целых чисел и число M. Необходимо выбрать ровно K элементов массива A, чтобы их произведение было в точности равно M.

Формат ввода
Первая строка входного файла содержит три числа N, M, K(1≤K≤N≤5000,0≤M≤109) – размер массива A, произведение, которое нужно построить, и количество выбираемых элементов соответственно. Вторая строка входного файла содержит N неотрицательных целых чисел Ai(0≤Ai≤109) –элементы массива A.Гарантируется, что ответ всегда существует.Формат выводаВыведите K различных натуральных чисел – индексы выбранных элементов массива A. Если решений несколько, выведите любое. Индексы можно выводить в произвольном порядке.

Пример
1Ввод
7 27 2
9 1 1 27 3 27 3
Вывод
4 2
Пример 2
Ввод
7 60 4
30 1 1 3 10 6 4
Вывод
5 6 3 2

@Catstail · 02.08.2019, 19:16

Задача сводится к перебору всех подмножеств из K элементов.

@dondublon · 02.08.2019, 19:59

Catstail, грубо, вылетит по времени.
Тут нужно что-то с сортировкой придумать.

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@AndreShah 0 / 0 / 0 Регистрация: 01.08.2019 Сообщений: 3

	Алгоритм или решение по этой задаче 01.08.2019, 14:52. Показов 3935. Ответов 2 Метки python 3, python 3.5, python 3.7, python 3.x, python для начинающих, алгоритмы (Все метки) У Васи есть массив A длины N из неотрицательных целых чисел и число M. Необходимо выбрать ровно K элементов массива A, чтобы их произведение было в точности равно M. Формат ввода Первая строка входного файла содержит три числа N, M, K(1≤K≤N≤5000,0≤M≤109) – размер массива A, произведение, которое нужно построить, и количество выбираемых элементов соответственно. Вторая строка входного файла содержит N неотрицательных целых чисел Ai(0≤Ai≤109) –элементы массива A.Гарантируется, что ответ всегда существует.Формат выводаВыведите K различных натуральных чисел – индексы выбранных элементов массива A. Если решений несколько, выведите любое. Индексы можно выводить в произвольном порядке. Пример 1Ввод 7 27 2 9 1 1 27 3 27 3 Вывод 4 2 Пример 2 Ввод 7 60 4 30 1 1 3 10 6 4 Вывод 5 6 3 2 0

@Catstail Супер-модератор 38197 / 21130 / 4309 Регистрация: 12.02.2012 Сообщений: 34,738 Записей в блоге: 14
	02.08.2019, 19:16
	Задача сводится к перебору всех подмножеств из K элементов. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	02.08.2019, 19:59
	Catstail, грубо, вылетит по времени. Тут нужно что-то с сортировкой придумать. 1