JBIRDS - Jeremías y sus loros

no tags 

El pirata Jeremías planea ofrecer un espectáculo a su tripulación. Para ello, Jeremías dispone de N loros, que planea equilibrar sobre sus hombros. Cada uno de los N loros tiene un peso, en gramos, que Jeremías conoce de antemano.

 

Jeremías tiene solamente dos hombros, y por lo tanto debe separar los loros en dos grupos. El desbalance del Jeremías sera igual a la diferencia (positiva) de peso entre el grupo que lleva en el hombro izquierdo y el que lleva en el hombro derecho.

 

¿Cuál es el menor valor que puede tomar el desbalance del pirata?

Input

La entrada comienza con una línea que contiene un único entero, N (0 <= N <= 10000)

Las siguientes N líneas describen los pesos de los loros. Cada línea contiene un único entero wi (0 <= wi <= 1000)

Output

Una línea con un único entero, el mínimo desbalance (en valor absoluto).

Example

Input:
4
2 1 5 3
Output:
1

hide comments
y17prashant: 2018-12-02 10:33:43

With simple array implementation you can do it in 0(n)...

Vadim: 2018-10-06 23:08:33

Is there a solution better than O(n^2)? Given limits(N <= 10000 and wi <= 1000) look too large

anirudnits: 2018-07-02 17:40:02

simple recursion works.

Muhammad Faishol Amirul Mukminin: 2018-07-02 09:55:44

The same problem
https://uva.onlinejudge.org/external/5/562.pdf

but with different constraint.

Last edit: 2018-07-02 09:56:33
mehmetin: 2018-06-29 01:43:29

It turns out that n <= 10 and sum <= 100

prakash1108: 2018-06-27 11:17:57

DP nailed it :)

prakash1108: 2018-06-26 15:03:57

The pirate Jeremiah plans to offer a show to his crew. For this, Jeremiah has N parrots, which he plans to balance on his shoulders. Each of the N parrots has a weight, in grams, which Jeremiah knows beforehand.



Jeremiah has only two shoulders, and therefore he must separate the parrots into two groups. The imbalance of Jeremiah will be equal to the (positive) difference in weight between the group that leads on the left shoulder and the one on the right shoulder.



What is the lowest value that the pirate's imbalance can take?

Input
The entry begins with a line containing a single integer, N (0 <= N <= 10000)

The following N lines describe the weights of the parrots. Each line contains a single integer wi (0 <= wi <= 1000)

Output
A line with a single integer, the minimum imbalance (in absolute value).

Last edit: 2018-06-26 20:36:22
prateek_imkp1: 2018-06-26 09:39:32

Last edit: 2018-06-26 11:54:44

Added by:BerSub
Date:2018-06-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All