06/04/2025 12:00:30

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

41. Копилка

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Задан вес

$E$ пустой копилки и вес

$F$ копилки с монетами. В копилке могут находиться монеты

$N$ видов, для каждого вида известна ценность

$P_i$ и вес

$W_i$ одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Ограничения:

$1\ ≤\ E\ ≤\ F\ ≤\ 10\ 000$ ,

$1\ ≤\ N\ ≤\ 500$ ,

$1\ ≤\ P_i\ ≤\ 50\ 000$ ,

$1\ ≤\ "Wi"\ ≤\ 10\ 000$ , все числа целые.

Ввод

В первой строке находятся числа

$E$ и

$F$ , во второй – число

$N$ , в следующих

$N$ строках – по два числа,

$P_i$ и

$W_i$ .

Вывод

Выводятся два числа через пробел – минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, – вывести "This is impossible.".

Пример ввода 1

Пример вывода 1

100 250

Пример ввода 2

Пример вывода 2

10 16

Пример ввода 3

1000 2000
1        
10 3

Пример вывода 3

This is impossible.

Источник: CERC, 1999, Меньшиков

03/07/2006	Лето 2006 дорешивание ( 3H)
07/07/2006	Лето 2006 - 3 (H)
19/11/2010	Занятие 10 (A)
10/10/2013	Занятие 6 для продолжающих (A)
08/07/2019	Лето 2019 - 4 (E)
02/03/2023	Базовый уровень: динамическое программирование 2 (проводит BOGAT) (D)
12/07/2023	Лето 2023-8 простые (B)
05/03/2024	Динамическое программирование 2 (проводит BOGAT) (D)
10/07/2024	Лето 2024-8 простые (B)
19/03/2025	ЦОП1: динамическое программирование (проводит BOGAT) (D)