O Caso das Malas

image imagem

Em janeiro de 2025, foi notícia um deputado ter sido constituído arguido por suspeitas de furtar bagagens em aeroportos. Dizem que, na casa de banho, escondia as malas furtadas dentro de outras de maior dimensão.

Não queremos resolver um caso de polícia, mas perceber como esconder $N$ malas pequenas em $B$ malas grandes, utilizando o menor número possível das grandes, sem analisar orientações e re-orientações para as encaixar. As malas grandes são identificadas por inteiros consecutivos, a partir de 1, assim como as pequenas. As malas grandes têm todas capacidade $C$ . A mala $i$ pequena ocupa $c_{i}$ unidades de capacidade, para $1 \leq i \leq N$ , sendo $C \geq c_{1} \geq c_{2} \geq \dots \geq c_{N} > 0$ , e todos inteiros. O número $t$ de tipos de malas é igual ao número de valores $c_{i}$ distintos.

Se desfizermos malas, isto é, se pudermos distribuir $c_{i}$ por várias malas grandes, para conseguir que as malas grandes usadas, exceto talvez uma delas, fiquem totalmente cheias, quantas malas usaria uma tal arrumação fracionária ótima? É fácil calcular! E, sem desfazer malas, quantas malas grandes requer uma arrumação ótima (não fracionária)? De certo, se $t$ e $N$ forem grandes, até o melhor programa pode demorar um tempo excessivo para responder. Para nos despacharmos, podemos tentar uma arrumação apressada em que, simplesmente, colocamos a mala $i$ pequena na primeira grande em que ainda couber, depois de termos escondido as malas numeradas de 1 a $i - 1$ . Com sorte, tal arrumação é tão boa como a ótima ou, até, como a ótima fracionária, que é sempre a que requer menos malas! Se a fracionária requerer mais do que $B$ malas, é óbvio que a apressada também falha assim como qualquer alternativa, pois $B$ malas não bastariam nunca.

Tarefa

Escreva um programa que, dados inteiros,

N

C

B

K

L

c_{i}

, com

i = 1, \dots, N

, determina a arrumação apressada, assumindo que não existem mais do que

B

malas grandes. Se a arrumação apressada falhar, por requerer mais do que

B

malas, indica a primeira mala

i

que não consegue arrumar, escrevendo "Apressada falha para mala

i

". Caso falhe ou suceda, calcula quantas malas requer uma arrumação fracionária ótima, para ver se vale a pena tentar procurar uma arrumação ótima (não fracionária) ou se, até, já a tem.

Assim, deve calcular uma arrumação ótima só se $N \leq L$ , $t \leq K$ e não for óbvio que a arrumação apressada é ótima, sendo $K$ e $L$ os dois limites dados. Para cada escolha para as malas $1$ a $i - 1$ , a mala $i$ pode ser colocada numa qualquer mala grande onde ainda caiba. Para cada alternativa, deve procurar completar a arrumação das restantes de forma ótima. Para não sucumbir por exaustão, tem de ser inteligente. Se $c_{i} = c_{i - 1}$ , isto é, se as malas $i$ e $i - 1$ são do mesmo tipo, não as permute, devendo ver se é melhor $i$ ficar na mesma mala que $i - 1$ ou numa das seguintes (até à mala $i$ grande). E deve tentar procurar arrumações (não fracionárias) que usem menos malas do que a melhor arrumação já encontrada. Não vale a pena tentar completar arrumações que não seriam melhores.

Input

A primeira linha do input tem cinco inteiros, que são

N

C

B

K

L

. Segue-se uma linha com

N

inteiros, separados por espaços, sendo

c_{i}

o valor que está na

i

-ésima posição da linha (para

i = 1, \dots, N

Restrições

$1 \leq N \leq 100$ Número de malas pequenas

$1 \leq C \leq 50$ Capacidade de cada mala grande

$1 \leq B \leq N$ Número de malas grandes disponíveis

$1 \leq c_{i} \leq C$ Capacidade ocupada pela mala pequena $i$ (para $i = 1, \dots, N$ )

$1 \leq t \leq N$ Número de tipos de malas pequenas

$1 \leq K \leq 10$ Número máximo de tipos para procurar uma arrumação ótima

$1 \leq L \leq 22$ Número máximo de malas pequenas para procurar uma arrumação ótima

Output

O output é constituído por duas linhas. Se a arrumação apressada suceder:

A primeira linha tem $N$ inteiros, separados por espaços, que indicam em que mala grande ficou cada mala pequena nessa arrumação, pela ordem em que as malas ocorrem no input;

A segunda linha tem a frase "Como fracionaria!", se a arrumação apressada usar o mesmo número de malas que a ótima fracionária; senão, se $N \leq L$ e $t \leq K$ , terá "Otima requer $M$ malas", com $M$ substituído pelo seu valor; mas, se $N > L$ ou $t > K$ , terá "Boa arrumacao?".

Se a arrumação apressada falhar:

A primeira linha tem "Apressada falha para mala $i$ ", com $i$ substituído pelo identificador da primeira mala que não pode ser escondida;

A segunda linha tem "Fracionaria requer $F$ malas", indicando $F$ . Se $F \leq B$ , $N \leq L$ e $t \leq K$ , terá ainda " e otima $M$ ", sendo $M$ o número que a arrumação ótima requer.

Exemplo 1

Input

9 12 9 9 9
7 6 4 4 4 3 3 3 2

Output

1 2 1 2 3 3 3 4 2
Otima requer 3 malas

Exemplo 2

Input

9 12 9 1 9
7 6 4 4 4 3 3 3 2

Output

1 2 1 2 3 3 3 4 2
Boa arrumacao?

Exemplo 3

Input

9 12 5 4 9
7 6 4 4 4 3 3 3 3

Output

1 2 1 2 3 3 3 4 4
Como fracionaria!

Exemplo 4

Input

9 12 3 5 9
7 6 4 4 4 3 3 3 2

Output

Apressada falha para mala 8
Fracionaria requer 3 malas e otima 3

Exemplo 5

Input

9 12 2 3 6
7 6 4 4 4 3 3 3 2

Output

Apressada falha para mala 5
Fracionaria requer 3 malas

Exemplo 6

Input

21 44 8 10 22
36 25 25 25 25 25 20 20 12 12 12 12 12 12 12 12 12 12 12 9 8

Output

Apressada falha para mala 17  
Fracionaria requer 8 malas e otima 9

Exemplo 7

Input

21 44 21 10 22 
36 25 25 25 25 25 20 20 12 12 12 12 12 12 12 12 12 12 12 9 8

Output

1 2 3 4 5 6 7 7 2 3 4 5 6 8 8 8 9 9 9 10 1
Otima requer 9 malas

ToPAS'2025