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 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
3 4 5
Output