Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2327. Сборка компьютера
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 13/11/2016 | Муниципальный этап 10-11 классы (4) |
| 02/03/2023 | Базовый уровень: динамическое программирование 2 (проводит BOGAT) (G) |
| 12/07/2023 | Лето 2023-8 простые (E) |
| 05/03/2024 | Динамическое программирование 2 (проводит BOGAT) (G) |
| 10/07/2024 | Лето 2024-8 простые (E) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для сборки компьютера необходимо `T` компонентов различного типа (видеокарта, жесткий диск, монитор и т.д.).
В магазине продаются `N` компонентов. Каждый компонент относится к определенному типу и имеет некоторую
стоимость и рейтинг по обзорам в журналах.
Напишите программу, определяющую из каких компонентов нужно собрать компьютер, чтобы его стоимость не
превышала `B`, в составе были по одному компоненту каждого типа, а суммарный рейтинг использованных компонентов
был максимальным.
Первая строка ввода содержит одно целое число – количество типов компонентов `T` (`1\ ≤\ T\ ≤\ 5`).
Вторая строка ввода содержит одно целое число – количество компонентов в магазине `N` (`1\ ≤\ N\ ≤\ 1000`).
Далее следует `N` строк, содержащих по три целых числа, разделенных пробелами – стоимость `i`-го
компонента `C_i` (`1\ ≤\ C_i\ ≤\ 3000`), его рейтинг `R_i` (`1\ ≤\ R_i\ ≤\ 3000`) и его тип `t_i` (`1\ ≤\ t_i\ ≤\ T`).
Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера `B` (`1\ ≤\ B\ ≤\ 3000`).
Вывести в первой строке одно целое число – максимальный суммарный рейтинг использованных компонент.
Во второй строке вывести `T` целых чисел – `i`-е число означает номер компонента типа `i`, выбранного для сборки.
Если существует несколько вариантов с максимальным суммарным рейтингом, то из них вывести вариант с
минимальной стоимостью, а среди таких вариантов можно вывести любой. Если не существует варианта
сборки компьютера в рамках указанного бюджета, то вывести в первой строке одно число –1
Пример ввода
2 5 10 6 1 5 7 1 6 10 2 1 5 1 11 11 2 16
Пример вывода
18 2 5
Система оценки и описание подзадач
Подзадача 1 (10 баллов)
`T=1`
В этой подзадаче 2 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (20 баллов)
`T=2`
В этой подзадаче 4 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (70 баллов)
`3\ ≤\ T\ ≤\ 5`
В этой подзадаче 10 тестов, каждый тест оценивается в 7 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
Внимание! Тест из примера не подходит под ограничения для подзадачи 1, но решение принимается
на проверку только в том случае, если оно выводит правильный ответ на тесте из примера.
Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадачи 1.
