Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2445

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2445

Polígono

 

Por OBI - Olimpíada Brasileira de Informática 2013 BR Brazil

Timelimit: 1

Renato gosta muito de geometria e acaba de achar alguns palitos em seu quarto. Ele está tentando utilizar esses palitos de forma a fazer um polígono com o maior número de lados possíveis.

Para montar o polígono, Renato não quer cruzar os palitos; ou seja, os palitos devem se tocar apenas nas pontas. Ele também não quer quebrar nenhum palito, de forma que todos os palitos que forem usados devem manter sua medida original.

Se, por exemplo, os palitos têm medidas 3, 4 e 5, é possível utilizar todos os três palitos para formar um triângulo. Mas se as medidas são 1, 1, 1 e 5, é possível formar um triângulo com três lados iguais a 1 mas não é possivel formar um polígono com todos os 4 palitos.

Você consegue ajudar Renato a descobrir qual é o maior número de palitos que ele consegue usar?

 

Entrada

 

A primeira linha contém apenas um inteiro N (3 ≤ N ≤ 100000) que indica o número de palitos. A segunda linha possui N inteiros indicando as medidas dos palitos, ( as medidas dos palitos são inteiros positivos menores ou iguais a 10000).

 

Saída

 

Se programa deve imprimir uma única linha, contendo um único inteiro, o maior número de lados que o polígono pode ter seguindo as restrições do enunciado. Se não for possível formar nenhum polígono usando os palitos, imprima 0.

 

 

 

Exemplos de Entrada Exemplos de Saída

3

3 4 5

3

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int main() {
    int resp = 0, soma = 0, n;
    scanf("%d", &n);
    vector<int> vetor;
    for (int i = 0; i  <  n; i++) {
        int davez;
        scanf("%d", &davez);
        vetor.push_back(davez);
    }
    sort(vetor.begin(), vetor.end());
    for (int i = 0; i  <  n; i++) {
        if (vetor[i] < soma) resp = i + 1;
        soma += vetor[i];
    }
    printf("%d\n", resp);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
3 4 5

Output

x
+
cmd
3
Advertisements

Demonstration


Previous
#2444 Beecrowd Online Judge Solution 2444 Volume da TV Solution in C, C++, Java, Js and Python
Next
#2448 Beecrowd Online Judge Solution 2448 Postman Solution in C, C++, Java, Js and Python