TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

burici.cpp    1,966 b      izvorni kod rešenja
burici.tests.rar    1,146,234 b      test primeri

zadatak: Burići

Dato je n burića. U svakom buretu se nalazi određena količina vode. Perica može da probuši ukupno m rupa na dnima burića (m > n). Kroz svaku probušenu rupu izlazi 1 litar vode u sekundi. Perica sve rupe buši istovremeno i želi da ih probuši tako da što pre ni u jednom buretu ne ostane ni malo vode (tj. da sva voda isteče što pre). Odrediti koliko je minimalno vreme posle bušenje nakon koga ni u jedmom buretu neće više biti vode.

Ulaz:

(Ulazni podaci se nalaze u datoteci burici.in) U prvom redu tekstualne datoteke nalaze se redom prirodni brojevi n (broj burića, n ≤ 50.000) i m (broj rupa, m ≤ 400.000). U drugom redu nalazi se n prirodnih brojeva (svaki je manji ili jednak 2.000.000.000) tako da i-ti (1 ≤ in) broj označava broj litara u i-tom buretu.

Izlaz:

(Izlazne podatke upisati u datoteku burici.out) U prvom redu tekstualne datoteke ispisati jedan realan broj a to je minimalno vreme koje se traži zaokruženo na dve decimale (priznaje se svako rešenje koje se od zvaničnog rešenja razlikuje po apsolutnoj vrednosti za ne više od 0:01).

Primer:

burici.in      burici.out
3 9
6 10 2
        
2.00
fajl: burici.cpp
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int n,m;
double *L;
double broj;

//prvo resenje ---------------------------------------
//za 100 poena
struct cvor
{
  double lit;  
  int br;
};

void zam(cvor *a,cvor *b)
{
  cvor pom=*a;
  *a=*b;
  *b=pom;
}

void f1()
{
  cvor *A=(cvor *)malloc(n*sizeof(cvor));
  int i;
  for (i=0;i<n;i++)
  {
    A[i].lit=L[i];
    A[i].br=1;
    int j=i;
    while (j>0 && A[(j-1)/2].lit<A[j].lit)
    {
      zam(A+(j-1)/2,A+j);
      j=(j-1)/2;
    }
  }
  for (i=0;i<m-n;i++)
  {
    A[0].br++;
    int j=0,da=1;
    while (da)
    {
      if (j*2+1>=n)
        da=0;
      else
        if (j*2+2==n)
          if (A[j].lit/A[j].br<A[j*2+1].lit/A[j*2+1].br)
          {
            zam(A+j,A+j*2+1);
            j=j*2+1;
          }
          else
            da=0;
        else
          if (A[j*2+1].lit/A[j*2+1].br>A[j*2+2].lit/A[j*2+2].br)
            if (A[j].lit/A[j].br<A[j*2+1].lit/A[j*2+1].br)
            {
              zam(A+j,A+j*2+1);
              j=j*2+1;
            }
            else
              da=0;
          else
            if (A[j].lit/A[j].br<A[j*2+2].lit/A[j*2+2].br)
            {
              zam(A+j,A+j*2+2);
              j=j*2+2;  
            }
            else
              da=0;
    }
  }
  broj=A[0].lit/A[0].br;
  free(A);
}
//--------------------------------------------------------

//drugo resenje ------------------------------------------
//za sto poena
void f2()
{
  double g=L[0],d=0;
  int i;
  for (i=1;i<n;i++)
    if (g<L[i])
      g=L[i];
  while (g-d>0.0001)
  {
    double br1=(g+d)/2;
    int br2=0;
    for (i=0;i<n;i++)
      br2+=ceil(L[i]/br1);
    if (br2<=m)
      g=br1;
    else
      d=br1;
  }
  broj=g;
}

//-------------------------------------------------------

void main()
{
  
  FILE *dat=fopen("Bure.in","r");
  fscanf(dat,"%d%d",&n,&m);
  L=(double *)malloc(n*sizeof(double));
  int i;
  for (i=0;i<n;i++)
    fscanf(dat,"%lf",L+i);
  fclose(dat);

  //f1();
  f2();

  
  


  dat=fopen("Bure.out","w");
  fprintf(dat,"%.2lf",broj);
  fclose(dat);

  
}