|
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.
|
logo by Igor Antolović
|
|
|
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 ≤ i ≤ n) 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);
}
|
|
|