Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MACACOMG - Macaco rural

Você foi contratado como programador para um novo website de compras coletivas chamado Macaco Rural. Para se diferenciar dos seus vários concorrentes, esse site planeja oferecer ofertas para pares de produtos. Por exemplo, “compre uma bola de futebol e uma camisa oficial da seleção brasileira com 75% de desconto”.

O site quer planejar as ofertas do dia para os próximos n dias. Para tanto, há uma lista de 2n produtos, com seus respectivos preços (já com os descontos aplicados). Como ofertas muito caras vendem menos, seu chefe quer minimizar o preço da oferta mais cara. Cabe a você agrupar os 2n produtos em n pares de forma tal que o custo do par mais caro seja minimizado. O custo de um par é a soma dos custos dos produtos que o compõem.

Entrada

Há vários casos de teste.

Cada caso de teste começa com uma linha que contém um único inteiro N, o número de produtos que serão usados para criar as ofertas (1 ≤ N ≤ 2.000.000, e N é sempre um número par). Em seguida, há uma linha contendo N inteiros P1, P2, ..., PN, que representam os preços dos N produtos que serão pareados em N/2 ofertas (0 ≤ Pi ≤ 1.000.000.000, para todo i).

A entrada termina com N = 0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma linha contendo um único inteiro, que é o maior preço de uma oferta, quando os N produtos são pareados de forma tal a minimizar esse maior preço.

Exemplos

Entrada:
4
1 19 26 17
8
3 9 6 18 14 1 7 8
0

Saída:
36
19

No primeiro caso de teste, há 3 possibilidades:

  • (1, 19), (17, 26), com custos 1+19=20 e 17+26=43. O maior custo é 43.
  • (1, 26), (17, 19), com custos 1+26=27 e 17+19=36. O maior custo é 36.
  • (1, 17), (19, 26), com custos 1+17=18 e 19+26=45. O maior custo é 45.

Dessas três opções, a que minimiza o maior custo é a segunda, que leva a um custo máximo de 36.


Adicionado por:Wanderley Guimarăes
Data:2012-06-21
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Maratona Mineira 2012

hide comments
2017-05-20 21:08:57
alguém me ajuda
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.