elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Problema de reparticiones de chocolates
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Problema de reparticiones de chocolates  (Leído 1,458 veces)
KINGARZA

Desconectado Desconectado

Mensajes: 33

Facebook: Luis Garza


Ver Perfil
Problema de reparticiones de chocolates
« en: 5 Diciembre 2016, 04:56 am »

Hola a todos, pues hoy me encuentro con este problema:

https://omegaup.com/arena/problem/cuanto#problems

L-¿Cuánto nos toca?

Límite de memoria   32MB
Límite de tiempo (caso)   1s   
Límite de tiempo (total)   60s

Descripción
El fin de semana pasado Karel celebró que había obtenido puntaje perfecto en su examen, por lo que hizo una fiesta para autofestejarse. En la fiesta hubo de todo, pero lo que más llamo la atención fueron unas barras de frutas con chocolate.
Al lunes siguiente, Karel planeó darle barras a sus amigos que no fueron invitados a la fiesta. Sin embargo, sus amigos estaban un poco molestos por no haber sido invitados. Como las barras de fruta no tienen la misma cantidad de chocolate , te has metido en un pequeño embrollo para compartirlas:
Para empezar, todos tienen que recibir la misma cantidad de chocolate.
Si alguno de ellos recibe mas chocolate que los demás, entonces se enojarán para siempre contigo.
Siempre puedes partir cualquier barra para darle a uno o más amigos (una parte a cada uno) o inclusive darles una barra completa.
En tu reparto, a cada uno de tus amigos sólo le puedes dar ya sea un único trozo de barra o una barra completa, ya que si alguno de ellos recibe más de un trozo o barra completa (aunque tenga la misma cantidad de chocolate que los demás amigos), también se enojarán contigo.
Para compensar el que no los hayas invitado, quieres darles la mayor cantidad de chocolate, siguiendo las restricciones de arriba, aunque implique que te quedes con barras incompletas y/o completas.
Entrada
En la primera línea habrá dos enteros NN y AA,que indican la cantidad de barras de chocolate y la cantidad de amigos a los que quiere repartir Karel.
En las siguientes NN líneas habrá un entero CiCi que indica la cantidad de chocolate que tiene la barra ii.
Salida
Un único número entero que representa la mayor cantidad de chocolate que les puedes dar a cada uno de tus amigos respetando las restricciones. Nota que es posible darles una cantidad racional de chocolate, pero como no tienes tanta precisión al partir, solo quieres darles cantidades enteras.
Ejemplo
Entrada   Salida   Descripción
2 2
2
2
2
Le das un barra a cada uno de tus amigos.
2 3
7
4
3
Como no es posible darles un pedazo que tenga 4 "unidades" de chocolate, es necesario partir ambas barras (barra [7] -> [3] [3] [1] y barra [4] -> [3] [1]) para que haya 3 pedazos con 3 "unidades" de chocolate y le das una de estas partes a cada uno de tus amigos.
Límites
1 <= NN, AA <= 100000
1 <= CiCi <= 100000

Esta es mi respuesta, la cual me da "Tiempo limite excedido"  y 46.67%:
Código
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.  
  5.    cin.tie(0);
  6.    ios_base::sync_with_stdio(0);
  7.    int n, amigos, aux, suma = 0, cont;
  8.    cin>>n>>amigos;
  9.    int ar[n];
  10.  
  11.    for(int i = 0; i < n; i++){
  12.        cin>>ar[i];
  13.        suma += ar[i];
  14.    }
  15.  
  16.    int optimo = suma / amigos;
  17.  
  18.    while(optimo){
  19.  
  20.        cont = 0;
  21.        for(int j = 0; j < n; j++)
  22.            cont += ar[j] / optimo;
  23.  
  24.        if(cont >= amigos)
  25.            break;
  26.        else
  27.            optimo--;
  28.    }
  29.    cout<<optimo;
  30.    return 0;
  31. }
  32.  

Si tienes alguna otra idea a la mia, por favor mencionala, me ayudarias mucho...


En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines