10043 - Chainsaw Massacre
Moderator: Board moderators
-
brianfry713
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10043 - Chainsaw Massacre WA???
Post or PM me your code.
Check input and AC output for thousands of problems on uDebug!
-
brianfry713
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10043 - Chainsaw Massacre WA???
Input:AC output:
Code: Select all
10
2467 1797
1 1655 600
2 1369 902 -371 -54
0
6761 7844
1 3629 7342
4 1561 1617 1629 -187
1 3600 1964
0
8070 5291
2 7858 1035 -7816 4093
4 4702 3963 -686 -1178
2 5149 4020 -670 -2093
1 6877 3645
1 4383 3482
0
1138 4404
1 34 4353
1 475 91
1 76 1370
2 185 4365 -93 -2003
0
4244 7766
1 3548 6481
1 1143 5753
1 2510 6603
0
5803 4766
1 1083 3895
1 5078 3172
1 5636 2070
1 3540 1074
1 3593 716
1 842 593
1 667 915
1 1101 4000
1 5475 2805
0
7614 1737
1 572 1376
1 5919 96
1 4733 890
1 1436 843
2 6946 320 -6281 851
1 4892 74
1 6549 400
1 32 341
0
14 9164
1 9 852
2 11 166 -8 8978
1 9 8938
0
8687 9526
1 8048 7674
1 2410 8977
1 514 8977
1 7828 4370
0
2059 5858
1 1626 3632
1 34 909
0
Code: Select all
2207965
36360658
15986256
4470604
24415732
14683084
5885803
113204
70271956
9325936
Check input and AC output for thousands of problems on uDebug!
-
mack_attack
- New poster
- Posts: 3
- Joined: Mon May 05, 2014 11:10 pm
Re: 10043 - Chainsaw Massacre WA???
Thanks, very much got it Accepting now.
It was a combination of reading in the paddock sizes like the puzzle says length then width,
but it would appear the data actually passes width (x) then length (y) and not having a endl after my final puzzle.
I did try swapping those around in previous submissions and adding/removing the final endl but must have change both as same time, causing it to be wrong each time.
That test data is very useful.
Thanks again.
It was a combination of reading in the paddock sizes like the puzzle says length then width,
but it would appear the data actually passes width (x) then length (y) and not having a endl after my final puzzle.
I did try swapping those around in previous submissions and adding/removing the final endl but must have change both as same time, causing it to be wrong each time.
That test data is very useful.
Thanks again.
Chainsaw Massacre RE??
Help me please, i have compiled and test it in my computer and it works, but I am getting runtime error for a reason i don't know.
Code: Select all
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAX 1000
#define MAXSC 10000
using namespace std;
bool acabar = true;
void clean(bool **location, bool *vert, int solVect[1000][5], int sol){
for(int y = 0; y<sol; y++){
if(solVect[y][4]==false) continue;
if(solVect[y][3]-solVect[y][1]==1) continue;
else {
int f=solVect[y][1]+1; bool trovat = false;
while(!trovat && f<solVect[y][3]){
if(vert[f]){
int f2=solVect[y][0]+1; bool trovat2 = false;
while(!trovat2 && f2<solVect[y][2]){
if(location[f2][f]){
trovat2=true;
trovat=true;
solVect[y][4]=false;
}
f2++;
}
}
f++;
}
}
}
}
int area(int solucion[4]){
int altura = solucion[3]-solucion[1];
int base = solucion[2]-solucion[0];
return base*altura;
}
int main( int argc, char *argv[] ){
const int location_num = 10000;
//posiciones de arboles
bool **location_matrix;
int numCasos;
//largo y ancho del campo
int l,w;
//soluciones temporales para el algoritmo
int solVect[1000][5];
int solTemp = 0;
//numero de soluciones temporales
int solac = 0;
//arboles que hay en el escenario actual
int arb[1000][2];
int cont = 0;
//vectores para saber si hay algun arbol en su fila o columna
bool *vertical;
bool *horitzontal;
char * linia;
//posiciones y cantidad de arboles
int arboles, posX, posY, dX, dY;
scanf( "%d", &numCasos );
int solFi[numCasos];
int cantidad = numCasos;
//Cota superior
int max = 0;
//datos para el algoritmo
bool salida = false; bool intermedio = false; bool sal = false;
int derecha = l, izquierda = 0;
int superior = 20000;
int baux=0;
//area calculada
int a=0;
//vector con una solucion
int s_t[4];
while( --numCasos >= 0 ){
//cota superior actual
max=0;
scanf( "%d %d", &l, &w );
//printf("%d %d ",l,w);
vertical = (bool *)malloc((w+1)*sizeof(bool));
if (!vertical)
{
cout<<"error 1 allocating vertical" << endl;
return 0;
}
for (int j=0; j<=w; j++)
vertical[j] = false;
horitzontal = (bool *)malloc((l+1)*sizeof(bool));
if (!horitzontal)
{
cout<<"error 1 allocating horitzontal" << endl;
return 0;
}
for (int j=0; j<=l; j++)
horitzontal[j] = false;
location_matrix = (bool **)malloc((l+1)*sizeof(bool *));
if (!location_matrix)
{
cout<<"error 1 allocating location_matrix" << endl;
return 0;
}
for (int i=0; i<l+1; i++)
{
location_matrix[i] = (bool *) malloc((w+1)*sizeof(bool ));
if (!location_matrix[i])
{
cout<<"error 2 allocating location_matrix" << endl;
return 0;
}
for (int j=0; j<w+1; j++)
location_matrix[i][j] = false;
}
//for(int i = 0;i<l;i++)for(int j=0;j<w;j++)location_matrix[i][j]=false;
while(arboles!=0 || acabar==1){
acabar=false;
scanf( "%d", &arboles );
//printf("arboles:%d ",arboles);
if(arboles!=0){
if(arboles==1){
scanf( " %d %d", &posX, &posY );
location_matrix[posX][posY]=true;
vertical[posY]=true;
horitzontal[posX]=true;
arb[cont][0]=posX;
arb[cont][1]=posY;
cont++;
} else {
scanf( " %d %d %d %d", &posX, &posY, &dX, &dY );
//printf("posicion1: %d %d posicion2: %d %d ",posX + dX*1-1,posY + dY*1-1,posX + dX*2-1,posY + dY*2-1);
for(int p =0;p<arboles;p++){
location_matrix[posX + dX*p][posY + dY*p]=true;
//printf("posicion1: %d %d posicion2: %d %d ",posX + dX*0,posY + dY*0,posX + dX*1,posY + dY*1);
vertical[posY + dY*p]=true;
horitzontal[posX + dX*p]=true;
arb[cont][0]=posX + dX*p;
arb[cont][1]=posY + dY*p;
cont++;
}
}
}
}
acabar=true;
/* for(int n = 0;n<=l;n++){
printf("\n");
for(int t=0;t<=w;t++)printf("%d",location_matrix[n][t]);
}*/
// printf("\n\n");
//aqui va el algoritmo
//para cada arbol del escenario
for(int j = 0; j<cont; j++){
//limpiamos la basura
//clean(location_matrix, vertical, solVect, solTemp);
salida = false; intermedio = false;
derecha = l; izquierda = 0;
superior = 20000;
baux=0;
//parte de arriba
if(arb[j][1]!=0){
for(int b1=arb[j][1]-1;!salida && b1>=0;b1--){
switch(intermedio)
{
case false:
//solucion inmediata
if(vertical[b1] || b1==0){
s_t[0] = 0;
s_t[1] = b1;
s_t[2] = l;
s_t[3] = arb[j][1];
a = area(s_t);
if(a>max){
//insertar solucion
solVect[solTemp][0] = 0;
solVect[solTemp][1] = b1;
solVect[solTemp][2] = l;
solVect[solTemp][3] = arb[j][1];
solVect[solTemp][4] = true;
solTemp++;
//actualizar cota
max=a;
}
intermedio = true;
baux=b1;
if(location_matrix[arb[j][0]][b1] || b1==0) salida = true;
}
break;
case true:
//solucion con bordes
if(location_matrix[arb[j][0]][b1]){
superior = b1;
b1=-1;
}
if(b1==0) superior=0;
break;
}
//if(b1==0 && area()>max){ solVect[solTemp]={0,0,};solTemp++;continue;}
}
//derecha
sal = false;
if(salida==true) sal=true;
if(arb[j][0]!=l){
for(int b2=arb[j][0]+1;!sal && b2<=l;b2++){
if(horitzontal[b2]){
for(int temR=baux;temR>superior && !sal;temR--){
if(location_matrix[b2][temR]) {
sal = true;
derecha=b2;
}
}
}
}
} else{
derecha=l;
}
//if(sal) salida = false;
//izquierda
if(arb[j][0]!=0){
for(int b3=arb[j][0]-1;!salida && b3>=0;b3--){
if(horitzontal[b3]){
for(int temR2=baux;temR2>superior && !salida;temR2--){
if(location_matrix[b3][temR2]) {
salida=true;
izquierda=b3;
}
}
}
}
} else{
izquierda=0;
}
if(superior!=20000){
//insertar solucion con superior izquierda y derecha mas el arbol como limites
s_t[0] = izquierda;
s_t[1] = superior;
s_t[2] = derecha;
s_t[3] = arb[j][1];
a = area(s_t);
if(a>max){
//insertar solucion
solVect[solTemp][0] = izquierda;
solVect[solTemp][1] = superior;
solVect[solTemp][2] = derecha;
solVect[solTemp][3] = arb[j][1];
solVect[solTemp][4] = true;
solTemp++;
//actualizar cota
max=a;
}
}
}
//vamos con la derecha
salida = false; intermedio = false;
derecha = w; izquierda = 0;
superior = 20000;
baux=0;
if(arb[j][0]!=l){
for(int b1=arb[j][0]+1;!salida && b1<=l;b1++){
switch(intermedio)
{
case false:
//solucion inmediata
if(horitzontal[b1] || b1==l){
s_t[0] = arb[j][0];
s_t[1] = 0;
s_t[2] = b1;
s_t[3] = w;
a = area(s_t);
if(a>max){
//insertar solucion
solVect[solTemp][0] = arb[j][0];
solVect[solTemp][1] = 0;
solVect[solTemp][2] = b1;
solVect[solTemp][3] = w;
solVect[solTemp][4] = true;
solTemp++;
//actualizar cota
max=a;
}
intermedio = true;
baux=b1;
if(location_matrix[b1][arb[j][1]] || b1==l) salida = true;
}
break;
case true:
//solucion con bordes
if(location_matrix[b1][arb[j][1]]){
superior = b1;
b1=l+1;
}
if(b1==l) superior=l;
break;
}
//if(b1==0 && area()>max){ solVect[solTemp]={0,0,};solTemp++;continue;}
}
//derecha
sal = false;
if(salida==true) sal=true;
if(arb[j][1]!=w){
for(int b2=arb[j][1]+1;!sal && b2<=w;b2++){
if(vertical[b2]){
for(int temR=baux;temR<superior && !sal;temR++){
if(location_matrix[temR][b2]) {
sal = true;
derecha=b2;
}
}
}
}
} else{
derecha=w;
}
//if(sal) salida = false;
//izquierda
if(arb[j][1]!=0){
for(int b3=arb[j][1]-1;!salida && b3<=0;b3--){
if(horitzontal[b3]){
for(int temR2=baux;temR2<superior && !salida;temR2++){
if(location_matrix[temR2][b3]) {
salida=true;
izquierda=b3;
}
}
}
}
} else{
izquierda=0;
}
if(superior!=20000){
//insertar solucion con superior izquierda y derecha mas el arbol como limites
s_t[0] = arb[j][0];
s_t[1] = izquierda;
s_t[2] = superior;
s_t[3] = derecha;
a = area(s_t);
if(a>max){
//insertar solucion
solVect[solTemp][0] = arb[j][0];
solVect[solTemp][1] = izquierda;
solVect[solTemp][2] = superior;
solVect[solTemp][3] = derecha;
solVect[solTemp][4] = true;
solTemp++;
//actualizar cota
max=a;
}
}
}
//vamos con la parte de debajo
salida = false; intermedio = false;
derecha = 0; izquierda = l;
superior = 20000;
baux=0;
if(arb[j][1]!=w){
for(int b1=arb[j][1]+1;!salida && b1<=w;b1++){
switch(intermedio)
{
case false:
//solucion inmediata
if(vertical[b1] || b1==w){
s_t[0] = 0;
s_t[1] = arb[j][1];
s_t[2] = l;
s_t[3] = b1;
a = area(s_t);
if(a>max){
//insertar solucion
solVect[solTemp][0] = 0;
solVect[solTemp][1] = arb[j][1];
solVect[solTemp][2] = l;
solVect[solTemp][3] = b1;
solVect[solTemp][4] = true;
solTemp++;
//actualizar cota
max=a;
}
intermedio = true;
baux=b1;
if(location_matrix[arb[j][0]][b1] || b1==w) salida = true;
}
break;
case true:
//solucion con bordes
if(location_matrix[arb[j][0]][b1]){
superior = b1;
b1=w+1;
}
if(b1==w) superior=w;
break;
}
//if(b1==0 && area()>max){ solVect[solTemp]={0,0,};solTemp++;continue;}
}
//derecha
sal = false;
if(salida==true) sal=true;
if(arb[j][0]!=0){
for(int b2=arb[j][0]-1;!sal && b2>=0;b2--){
if(horitzontal[b2]){
for(int temR=baux;temR<superior && !sal;temR++){
if(location_matrix[b2][temR]) {
sal = true;
derecha=b2;
}
}
}
}
} else{
derecha=0;
}
//if(sal) salida = false;
//izquierda
if(arb[j][0]!=l){
for(int b3=arb[j][0]+1;!salida && b3<=l;b3++){
if(horitzontal[b3]){
for(int temR2=baux;temR2<superior && !salida;temR2++){
if(location_matrix[b3][temR2]) {
salida=true;
izquierda=b3;
}
}
}
}
} else{
izquierda=l;
}
if(superior!=20000){
//insertar solucion con superior izquierda y derecha mas el arbol como limites
s_t[0] = derecha;
s_t[1] = arb[j][1];
s_t[2] = izquierda;
s_t[3] = superior;
a = area(s_t);
if(a>max){
//insertar solucion
solVect[solTemp][0] = derecha;
solVect[solTemp][1] = arb[j][1];
solVect[solTemp][2] = izquierda;
solVect[solTemp][3] = superior;
solVect[solTemp][4] = true;
solTemp++;
//actualizar cota
max=a;
}
}
}
//vamos con la izquierda
salida = false; intermedio = false;
derecha = 0; izquierda = w;
superior = 20000;
baux=0;
if(arb[j][0]!=0){
for(int b1=arb[j][0]-1;!salida && b1>=0;b1--){
switch(intermedio)
{
case false:
//solucion inmediata
if(horitzontal[b1] || b1==0){
s_t[0] = b1;
s_t[1] = 0;
s_t[2] = arb[j][0];
s_t[3] = w;
a = area(s_t);
if(a>max){
//insertar solucion
solVect[solTemp][0] = b1;
solVect[solTemp][1] = 0;
solVect[solTemp][2] = arb[j][0];
solVect[solTemp][3] = w;
solVect[solTemp][4] = true;
solTemp++;
//actualizar cota
max=a;
}
intermedio = true;
baux=b1;
if(location_matrix[b1][arb[j][1]] || b1==0) salida = true;
}
break;
case true:
//solucion con bordes
if(location_matrix[b1][arb[j][1]]){
superior = b1;
b1=-1;
}
if(b1==0) superior=0;
break;
}
//if(b1==0 && area()>max){ solVect[solTemp]={0,0,};solTemp++;continue;}
}
//derecha
sal = false;
if(salida==true) sal=true;
if(arb[j][1]!=0){
for(int b2=arb[j][1]-1;!sal && b2>=0;b2--){
if(vertical[b2]){
for(int temR=baux;temR>superior && !sal;temR--){
if(location_matrix[temR][b2]) {
sal = true;
derecha=b2;
}
}
}
}
} else{
derecha=0;
}
//if(sal) salida = false;
//izquierda
if(arb[j][1]!=w){
for(int b3=arb[j][1]+1;!salida && b3<=w;b3++){
if(vertical[b3]){
for(int temR2=baux;temR2>superior && !salida;temR2--){
if(location_matrix[temR2][b3]) {
salida=true;
izquierda=b3;
}
}
}
}
} else{
izquierda=w;
}
if(superior!=20000){
//insertar solucion con superior izquierda y derecha mas el arbol como limites
s_t[0] = superior;
s_t[1] = derecha;
s_t[2] = arb[j][0];
s_t[3] = izquierda;
a = area(s_t);
if(a>max){
//insertar solucion
solVect[solTemp][0] = superior;
solVect[solTemp][1] = derecha;
solVect[solTemp][2] = arb[j][0];
solVect[solTemp][3] = izquierda;
solVect[solTemp][4] = true;
solTemp++;
//actualizar cota
max=a;
}
}
}
}//fin del arbol actual
if(max!=0)solFi[numCasos]=max; else solFi[numCasos]=l*w;
free(location_matrix);
free(vertical);
free(horitzontal);
}//fin del caso actual
//mostramos por pantalla el resultado
for(int nu = cantidad-1;nu>-1;nu--){
printf("%d\n",solFi[nu]);
}
return 0;
}//fin del main