|
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: Vojnici
|
Perica igra jednu igru na svom računaru. On ima n svojih vojnika od kojih svaki ima
neku jačinu. Dato je i n protivničkih vojnika od kojih svaki takođe ima neku jačinu. Jačine
tih 2n vojnika su različite (tj. ne postoje dva vojnika sa jednakim jačinama). Perica treba
da uradi sledeću stvar: treba da sastavi n parova vojnika tako da se svaki par sastoji
od jednog njegovog i jednog protivničkog vojnika i da se svaki od 2n vojnika pojavljuje u
tačno jednom paru. I tada kreće bitka. U svakom od n dvoboja (u i-tom dvoboju (1 ≤ i ≤ n)
učestvuju vojnici i-tog para) pobeđuje vojnik koji je jači. Za svakog od n protivničkih
vojnika data su po dva broja: jedan koji govori koliko Perica dobija poena ukoliko njegov
(Peričin) vojnik pobedi tog vojnika i drugi koji govori koliko Perica gubi poena ukoliko
njegov vojnik izgubi od tog vojnika. Perica na početku ima 0 poena. Odrediti koliki je
maksimalan broj poena koji Perica može skupiti (taj broj može biti i negativan).
Ulaz.
(Ulazni podaci se nalaze u datoteci vojnici.in) U prvom redu tekstualne datoteke
nalazi se prirodan broj n (n ≤ 2.000). U drugom redu nalazi se n prirodnih brojeva: i-ti
od tih brojeva (1 ≤ i ≤ n) predstavlja jačinu i-tog Peričinog vojnika (svaki od brojeva je
manji od ili jednak 2.000.000.000). U trećem redu nalazi se n prirodnih brojeva: i-ti broj u tom
redu (1 ≤ i ≤ n) predstavlja jačinu i-tog protivničkog vojnika (svaki od brojeva je manji ili
jednak 2.000.000.000). U četvrtom redu nalazi se n prirodnih brojeva: i-ti broj (1 ≤ i ≤ n)
predstavlja broj poena koji Perica dobija ukoliko je taj protivnički vojnik poražen (svaki
od brojeva je manji od ili jednak 1.000). U petom redu nalazi se n prirodnih brojeva: i-ti broj
(1 ≤ i ≤ n) predstavlja broj poena koji Perica gubi ukoliko je taj protivnički vojnik u
dvoboju u kome je učestvovao izašao kao pobednik (svaki od brojeva je manji ili jednak
1.000).
Izlaz.
(Izlazne podatke upisati u datoteku vojnici.out) U prvom redu tekstualne datoteke
ispisati jedan ceo broj a to je maksimalan broj poena koji Perica može skupiti.
Primer 1.
vojnici.in
|
|
vojnici.out
|
3
9 12 3
4 5 6
10 2 7
5 3 1
|
|
14
|
|
|
fajl: vojnici.cpp
|
#include <stdio.h>
#include <stdlib.h>
int n;
int *A,*B,*D,*G;
int broj;
void zam(int *a,int *b)
{
int pom=*a;
*a=*b;
*b=pom;
}
//prvo resenje ------------------------------------------
void sortA(int *A,int n)
{
int br=A[n/2];
int i=0,j=n-1;
while (i<=j)
{
while (A[i]<br)
i++;
while (A[j]>br)
j--;
if (i<=j)
{
zam(A+i,A+j);
i++;
j--;
}
}
if (j>0)
sortA(A,j+1);
if (n-i>1)
sortA(A+i,n-i);
}
void sortB(int *B,int *D,int *G,int n)
{
int br=B[n/2];
int i=0,j=n-1;
while (i<=j)
{
while (B[i]<br)
i++;
while (B[j]>br)
j--;
if (i<=j)
{
zam(B+i,B+j);
zam(G+i,G+j);
zam(D+i,D+j);
i++;
j--;
}
}
if (j>0)
sortB(B,D,G,j+1);
if (n-i>1)
sortB(B+i,D+i,G+i,n-i);
}
void f1()
{
sortA(A,n);
sortB(B,D,G,n);
int *P1=(int *)malloc(n*sizeof(int));
int *P2=(int *)malloc(n*sizeof(int));
int i,j;
for (i=0;i<n;i++)
{
int *pom=P2;
P2=P1;
P1=pom;
if (A[i]>B[0])
P1[0]=D[0];
else
P1[0]=-G[0];
for (j=1;j<=i;j++)
{
P1[j]=P1[j-1]-G[j];
if (A[i]>B[j] && P2[j-1]+D[j]>P1[j])
P1[j]=P2[j-1]+D[j];
}
}
broj=P1[n-1];
}
//-------------------------------------------------------
//drugo resenje -----------------------------------------
void sortC(int *B,int *D,int *G,int n)
{
int br=D[n/2]+G[n/2];
int i=0,j=n-1;
while (i<=j)
{
while (D[i]+G[i]<br)
i++;
while (D[j]+G[j]>br)
j--;
if (i<=j)
{
zam(B+i,B+j);
zam(G+i,G+j);
zam(D+i,D+j);
i++;
j--;
}
}
if (j>0)
sortC(B,D,G,j+1);
if (n-i>1)
sortC(B+i,D+i,G+i,n-i);
}
void f2()
{
sortC(B,D,G,n);
broj=0;
int i,j,da,k,m;
m=n;
for (i=n-1;i>=0;i--)
{
da=0;
for (j=0;j<m;j++)
if (A[j]>B[i])
if (!da)
{
da=1;
k=j;
}
else
if (A[j]<A[k])
k=j;
if (da)
{
m--;
zam(A+k,A+m);
broj+=D[i];
}
else
broj-=G[i];
}
}
//-------------------------------------------------------
void main()
{
FILE *dat=fopen("Vojnici.in","r");
fscanf(dat,"%d",&n);
int i;
A=(int *)malloc(n*sizeof(int));
B=(int *)malloc(n*sizeof(int));
D=(int *)malloc(n*sizeof(int));
G=(int *)malloc(n*sizeof(int));
for (i=0;i<n;i++)
fscanf(dat,"%d",A+i);
for (i=0;i<n;i++)
fscanf(dat,"%d",B+i);
for (i=0;i<n;i++)
fscanf(dat,"%d",D+i);
for (i=0;i<n;i++)
fscanf(dat,"%d",G+i);
fclose(dat);
f1();
//f2();
dat=fopen("Vojnici.out","w");
fprintf(dat,"%d",broj);
fclose(dat);
}
|
|
|