Questão da maratona de programação de 2005, consiste em determinar a quantidade de ladrilhos para recobrir a piscina e obter o menor custo, nesta questão usamos o famoso algoritmo guloso, sendo que o melhor custo/área coberta é em ordem: 30x30, 15x15, 5x5. Assim você primeiro recobre primeiro com 30x30 e assim por diante.
Quando eu tentei resolver pela primeira vez calculei a área total da piscina depois dividí pela área de 30x30, 15x15, e 5x5 respectivamente, mas, com isso foi necessário quebrar os ladrilhos. Assim, a melhor solução é calcular os ladrilhos para cada parede, simples!
Aí o código:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int P = 0, M = 0, G = 0;
void ladrilhos05 (int Xa, int Xb, int *p, int *m, int *g) {
int i, mod=Xa/5;
for (i=0; i<mod; i++) {
(*p)+=Xb/5;
P-=Xb/5;
}
}
void ladrilhos15 (int Xa, int Xb, int *p, int *m, int *g) {
int i, mod=Xa/15, aux;
for (i=0; i<mod; i++) {
if (Xb/15>M) {
(*m)+=aux=M;
M=0;
}
else {
(*m)+=aux=Xb/15;
M-=Xb/15;
}
aux*=15;
if (Xb-aux) ladrilhos05 (15, Xb-aux, &(*p), &(*m), &(*g));
}
ladrilhos05 (Xa-mod*15, Xb, &(*p), &(*m), &(*g));
}
void ladrilhos30 (int Xa, int Xb, int *p, int *m, int *g) {
int i, mod=Xa/30, aux=0;
for (i=0; i<mod; i++) {
if (Xb/30>G) {
(*g)+=aux=G;
G=0;
}
else {
(*g)+=aux=Xb/30;
G-=Xb/30;
}
aux*=30;
if (Xb-aux) ladrilhos15 (30, Xb-aux, &(*p), &(*m), &(*g));
}
ladrilhos15 (Xa-mod*30, Xb, &(*p), &(*m), &(*g));
}
int main () {
do {
int Xa = 0, Xb = 0, Ya = 0, Yb = 0, Za = 0, Zb = 0;
scanf ("%d.%d %d.%d %d.%d", &Xa, &Xb, &Ya, &Yb, &Za, &Zb);
Xa = (10*Xa+Xb)*10;
Ya = (10*Ya+Yb)*10;
Za = (10*Za+Zb)*10;
if (Xa==0 && Ya==0 && Za==0) break;
scanf ("%d %d %d", &P, &M, &G);
int qtdG = 0, qtdM = 0, qtdP = 0;
int tempP=P, tempM=M, tempG=G;
ladrilhos30 (Xa, Za, &qtdP, &qtdM, &qtdG);
ladrilhos30 (Xa, Za, &qtdP, &qtdM, &qtdG);
ladrilhos30 (Ya, Za, &qtdP, &qtdM, &qtdG);
ladrilhos30 (Ya, Za, &qtdP, &qtdM, &qtdG);
ladrilhos30 (Xa, Ya, &qtdP, &qtdM, &qtdG);
if (qtdP>tempP) printf ("impossivel\n");
else printf ("%d %d %d\n", qtdP, qtdM, qtdG);
} while (1);
return 0;
}
SITE: http://br.spoj.com/problems/PISCINA/
