Pagini recente » Cod sursa (job #1712688) | Cod sursa (job #2545303) | Cod sursa (job #1114082) | Cod sursa (job #1408000) | Cod sursa (job #586215)
Cod sursa(job #586215)
#include <cstdio>
using namespace std;
FILE *f=fopen("fabrica.in", "r");
FILE *g=fopen("fabrica.out", "w");
int n, nra, nrb;
int va[50001], vb[50001];
int sola, solb;
double inta, intb;
inline void swape(int &a, int &b)
{
int h=a; a=b; b=h;
}
void read()
{
fscanf(f, "%d%d%d", &n, &nra, &nrb);
for (int i=1; i<=nra; ++i)
{
fscanf(f, "%d", &va[i]);
inta+=1.0/static_cast<double>(va[i]);
}
for (int j=1; j<=nrb; ++j)
{
fscanf(f, "%d", &vb[j]);
intb+=1.0/static_cast<double>(vb[j]);
}
}
void quicksort(int lo, int hi, int a[])
{
int x=a[(lo+hi)/2];
int i=lo, j=hi;
do
{
while (a[i]<x) ++i;
while (a[j]>x) --j;
if (i<=j)
{
swape(a[i], a[j]);
++i; --j;
};
}while (i<=j);
if (i<hi) quicksort(i, hi, a);
if (j>lo) quicksort(lo, j, a);
}
int numar(int x)
{
int nr=0;
for (int i=1; i<=nra && x/va[i];++i)
{
nr+=x/va[i];
}
return nr;
}
int numarb(int x)
{
int nr=0;
for (int i=1; i<=nrb && x/vb[i];++i)
{
nr+=x/vb[i];
}
return nr;
}
void cautbin(unsigned int lo, unsigned int hi)
{
unsigned int x=(lo+hi)/2;
int cv1=numar(x);
if (cv1<n)
{
int cv2=numar(x+1);
if (cv2>=n)
sola=x+1;
else cautbin(x+1, hi);
}
else cautbin(lo, x);
}
void cautbinb(unsigned int lo, unsigned int hi)
{
unsigned int x=(lo+hi)/2;
int cv1=numarb(x);
if (cv1<n)
{
int cv2=numarb(x+1);
if (cv2>=n)
solb=x+1+va[1];
else cautbinb(x+1, hi);
}
else cautbinb(lo, x);
}
int main()
{
read();
quicksort(1, nra, va);
quicksort(1, nrb, vb);
cautbin(1, va[1]*n);
if (inta-intb>=0.000001)
cautbinb(1, vb[1]*n);
else
{
solb=sola+vb[1];
}
fprintf(g, "%d %d", sola, solb);
fclose(f);
fclose(g);
return 0;
}