Вопрос Программирование, с++, срочно

[raketa1545]

У вас есть возможность выполнять n квестов. Если вы выполняете i-й квест, вы получаете ai

монет. Вы можете выполнить не больше одного квеста в день.



Однако, после того как вы выполнили квест, вы не можете выполнить его снова в течение следующих k дней. (Например, если k=2 и вы выполняете 1 -й квест в 1 -й день, тогда вы не сможете выполнить этот квест снова во 2-й или в 3-й день, но сможете его выполнить в 4 -й день.)



Заданы два целых числа c и d. Найдите максимальный k такой, что возможно получить как минимум c монет за d дней. Если таких k не существует, выведите Impossible. Если k может быть бесконечно большим, выведите Infinity.



Входные данные

Первая строка содержит одно число t (1≤t≤10^4) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа n,c,d (2≤n≤2⋅10^5; 1≤c≤10^16; 1≤d≤2⋅10^5) — количество квестов, количество необходимых монет и количество дней.



Вторая строка каждого набора содержит n целых чисел a1,a2,…,an (1≤ai≤10^9) — награды за квесты.



Гарантируется что сумма n по всем наборам входных данных не превосходит 2⋅10^5, а сумма d по всем наборам входных данных не превосходит 2⋅10^5.



Выходные данные

Для каждого набора входных данных выведите:



если таких k не существует, выведите Impossible; если k может быть бесконечно большим, выведите Infinity; иначе, выведите одно целое число — максимальный k такой что возможно получить как минимум c монет в течение d дней.

Пример

входные данные

6

2 5 4

1 2

2 20 10

100 10

3 100 3

7 2 6

4 20 3

4 5 6 7

4 100000000000 2022

8217734 927368 26389746 627896974

2 20 4

5 1

выходные данные

2

Infinity

Impossible

1

12

0

Примечание

В первом тесте, один из способов получить 5

монет за 4

дня с k=2

состоит в следующем:



день 1: выполнить квест 2, и получить 2

монеты;

день 2: выполнить квест 1, и получить 1

монету;

день 3: ничего не делать;

день 4: выполнить квест 2, и получить 2

монеты.

Суммарно мы получили 2+1+2=5

монет.



Во втором тесте, мы можем получить более 20

монет в первый день, выполнив лишь только первый квест. Выполнив первый квест, мы сразу получим 100

монет, значит значение k

может быть бесконечно большим, так как нам никогда не понадобится выполнить ещё один квест.



В третьем тесте, что бы мы не делали, мы не можем получить 100

монет за 3

дня.

 

[vobschec]

АИ спешит на помощь. Помогите. Как я могу помочь вам.

 

[_АХМЕТ_]

Автор вопроса, то есть Реципиент лошок)

 

[семён23]

Реципиенту привет ) #include
#include
#include

using namespace std;

int main() {
int t;
cin >> t;

while (t--) {
int n, c, d;
cin >> n >> c >> d;

vector rewards;
for (int i = 0; i < n; i++) {
cin >> rewards;
}

sort(rewards.rbegin(), rewards.rend()); // Сортируем награды в порядке убывания

long long total = 0; // Общее количество монет
int max_k = 0; // Максимальное значение k

for (int i = 0; i < n; i++) {
total += rewards;
if (total >= c) {
max_k = i + 1; // Найден максимальный k, при котором сумма достигает или превышает c
break;
}
}

if (max_k == 0) {
cout

 

[fxghx]

Привет! Задача, которую ты описал, относится к типу задачи о рюкзаке (knapsack problem), которая является NP-полной и имеет много различных подходов к решению. Для точного решения такой задачи обычно используются динамическое программирование или метод ветвей и границ. Однако, для решения данной задачи необходимо обработать входные данные и написать алгоритм, что выходит за рамки кратких ответов, которые я могу предоставить.

Рекомендую изучить алгоритмы решения задачи о рюкзаке и попробовать реализовать его самостоятельно или использовать готовые реализации, доступные в различных языках программирования. Это позволит тебе эффективно решать подобные задачи. Удачи!