Informática - Nivel Iniciante - Semana 3

Alturas

Em um parque, $N$ pessoas querem se divertir no mais novo brinquedo aquático inaugurado. Cada pessoa entrará no brinquedo em um bote, tal que cada bote pode conter no máximo duas pessoas. Para cada bote, há uma restrição quanto à altura dos participantes: A soma das alturas das pessoas em cada bote deve ser menor ou igual a $x$. Cada pessoa irá entrar em exatamente um bote, e um bote pode conter uma ou duas pessoas.

Com isso, as pessoas do parque pediram que você responda a seguinte pergunta: Qual a menor quantidade necessária de botes para que todos se divirtam?

Entrada:

A primeira linha da entrada consiste de dois inteiros, $N$ e $x$.
A segunda linha da entrada contém $N$ inteiros $h_i$ ($1 \leq i \leq N$), indicando as alturas de cada pessoa.

Saída

Imprima um único inteiro: A menor quantidade necessária de botes.

Restrições:

• $1 \leq N \leq 10^5$
• $1 \leq x \leq 10^9$
• $1 \leq h_i \leq x$

Exemplos:

4 10
7 2 3 9

3

Use esse link para submeter a sua solução.