10034 - Freckles

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf » Mon Oct 27, 2003 5:38 am

thanks for reply, Grinder, but that's not the problem...
i have make stupid mistake at the part u point..

i compare set[k] with set[e[j].v2] but value of set[e[j].v2] will change in the loop..

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

10034 "Problem A: Freckles" Input/Output & WA

Post by jandujar » Tue Mar 09, 2004 11:16 pm

I recode this code

I have this code


[cpp]
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <math.h>

using namespace std;

/* Tipos */

struct EdgeOfGraph {
int vertex1,vertex2;
float weight;
};

typedef EdgeOfGraph edge;


typedef struct tipo{
float x;
float y;
}tipo;
typedef vector<tipo>punto;


/* Variables globales */

edge *edges,*edgesOfTree;
int v1,v2,nEdges,nVertices,*set;

punto puntos(101); //hay numero de puntos maximo de 100 el 0 no lo utilizo
int numeropuntos=0;



/* Make Set */
void Make_set(int set[])
{
int ctr1;
for(ctr1=1;ctr1<=set[0];ctr1++)
set[ctr1]=ctr1;
};

/* Link */
void Link(int set[],int x1,int x2)
{
int ctr1,ctr2,prevVal;
if(set[x1]==set[x2]) return ;
if(set[x1]<set[x2])
{prevVal=set[x2];
set[x2]=set[x1];
for(ctr1=1;ctr1<=set[0];ctr1++)
if(set[ctr1]==prevVal) set[ctr1]=set[x2];
return ;
}
if(set[x2]<set[x1])
{prevVal=set[x1];
set[x1]=set[x2];
for(ctr1=1;ctr1<=set[0];ctr1++)
if(set[ctr1]==prevVal) set[ctr1]=set[x1];
return ;
}
}


float distancia(float x1,float y1, float x2, float y2){
return ((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}

void get_Edges(){

int ctrl=1;
int vertice1=1;
int vertice2=2;

while (ctrl<=nEdges){
while (vertice2<=numeropuntos){
edges[ctrl].vertex1=vertice1;
edges[ctrl].vertex2=vertice2;
edges[ctrl].weight=distancia(puntos[vertice1].x,puntos[vertice1].y,puntos[vertice2].x,puntos[vertice2].y);
vertice2++;
ctrl++;
}

vertice1++;
vertice2=vertice1+1;
}

}

/* Sort Edges */
void sort_Edges(edge edges[])
{
int ctr1,ctr2,ctr3;
edge temp;
for(ctr1=2;ctr1<=nEdges;ctr1++)
{
temp=edges[ctr1];
ctr2=ctr1;
while(ctr2>1 && temp.weight<edges[ctr2-1].weight)
{edges[ctr2]=edges[ctr2-1];
ctr2--;
};
if(ctr2!=ctr1)
edges[ctr2]=temp;
}
}

/* Kruskal */

void implementKruskal(edge edges[],edge edgesOfTree[],int set[])
{int ctr1,ctr2=1;
for(ctr1=1;ctr1<=edges[0].vertex1;ctr1++)
{if(set[edges[ctr1].vertex1]!=set[edges[ctr1].vertex2])
{
Link(set,edges[ctr1].vertex1,edges[ctr1].vertex2);
edgesOfTree[ctr2++]=edges[ctr1];
};
}
edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=ctr2-1;
}

/* Recorremos los arcos sumando el resultado */
void muestraResultado(){
float salida=0;
int i;

for (i=1;i<=edgesOfTree[0].vertex1;i++){
salida+=sqrt(edges.weight);
}
printf("%.2lf\n",salida);
}



/* Ejecucion Kruskal */

int Kruskal(int nNodos)
{

set=(int *)malloc(sizeof(int) * (nNodos+1));
nEdges=nNodos*(nNodos -1)/2; //Maximo numero de nodos

edges=(edge *)malloc(sizeof(edge) * (nEdges+1));
edgesOfTree=(edge *)malloc(sizeof(edge) * (nEdges+1));

edges[0].vertex1=edges[0].vertex2=edges[0].weight=nEdges;
edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=nEdges;

// Carga las aristas
get_Edges();

// Ordena
sort_Edges(edges);

// Preparo el set
set[0]=nNodos;
Make_set(set);

// Ejecuto kruskal
implementKruskal(edges,edgesOfTree,set);

muestraResultado();


return 0;
}




/* A partir de aqui se acaba kruskal */


float distancia_minima(int indice){
float min=100000000;
float temp=100000000;
int i;

for(i=indice+1;i<numeropuntos;i++){

temp=distancia(puntos[indice].x,puntos[indice].y,puntos.x,puntos.y);
//cout<<"temp es:"<<temp<<endl;
if (temp<min){min=temp;}
}

return min;
}



int main(int argc, char *argv[])
{
int numerotest=0;
int i=0;
float x,y;
float salida=0;

// 200 es el tama
Last edited by jandujar on Wed Mar 10, 2004 8:25 am, edited 1 time in total.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed Mar 10, 2004 6:19 am

It seems that you have used the proper algorithm( Kruskal), but your code is far too long. I think you are considering extra things which is not required. For example, there is no need to define your own sort function, when a built in one is available.

Another thing, I have noticed in your code is you are passing parameters to the main function, which although not wrong, but is unnecessary.

You are also using dynamic memory allocation at various places, this is redundand. Since the number of points is given in advance, just use static array.

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

I still need help

Post by jandujar » Wed Mar 10, 2004 8:21 am

Thank, I know the code isn't acurancy. (I will recode when it's necessary)

I have got a "kruskal" algorithm and then I have recode it.

Seems that works , but always give me Wrong Answer. Why?

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Wed Mar 10, 2004 10:13 am

You can replace float by double.(infact all)
You wrote:
void muestraResultado(){
float salida=0;
int i;

for (i=1;i<=edgesOfTree[0].vertex1;i++){
salida+=sqrt(edges.weight);
}
printf("%.2lf\n",salida);
}
cuii e

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

Float -> Double

Post by jandujar » Wed Mar 10, 2004 11:22 am

I tried with all floats to doubles and don't work.
Thanks

Any other suggest?

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

I think the problem is output

Post by jandujar » Wed Mar 10, 2004 11:25 am

I Think the problem is output.

I write:

while(numtests>0)

cout<<number whith 2 decimal precition (redonded, shall i try truncated?)
cout<<endl;

end while


Is this correct?

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

INPUT/OUTPUT example

Post by jandujar » Thu Mar 11, 2004 8:23 am

I have this input:
[cpp]
10

2
1.4 0.4
1.0 0.3

1
3.4 5.0

10
4.2 1.6
0.3 4.6
6.2 0.0
8.9 6.8
3.9 6.7
6.0 3.3
9.7 7.4
1.5 0.7
6.5 8.9
2.1 3.0

1
6.6 7.3

9
8.0 3.2
0.9 9.7
6.8 7.6
8.9 2.1
9.6 6.0
8.6 6.2
6.4 9.1
5.0 8.8
3.1 1.8

9
4.0 7.7
4.4 1.7
8.3 2.0
1.8 8.2
2.8 7.0
2.4 2.2
4.4 0.1
7.9 2.4
7.3 6.2

2
0.6 4.0
9.1 8.5

6
8.0 3.4
7.7 5.4
7.7 4.6
9.9 0.3
8.7 6.9
3.4 1.6

1
6.7 7.5

4
9.1 0.8
8.0 9.0
9.0 9.1
7.5 5.1

[/cpp]

And this output

[cpp]
0.41

0.00

22.69

0.00

16.15

15.90

9.62

8.37

0.00

9.21
[/cpp]

Is this correct? Thanks

Nota: I use this program to generate inputs.

[cpp]
#include <iostream.h>
#include <time.h>
#include <stdlib.h>

void puntorandom(){
int input1, input2;

input1 = rand() * 10 / (RAND_MAX + 1);
input2 = rand() * 10 / (RAND_MAX + 1);

cout<<input1<<"."<<input2;
}


int main()
{
int puntos,i,j;
srand(time(NULL));

cout<<10<<endl<<endl;

for (i=0; i<10 ; i++)
{
puntos= rand() * 10 / (RAND_MAX + 1) +1;
cout<<puntos<<endl;
for (j=0;j<puntos;j++){

puntorandom();
cout<<" ";
puntorandom();
cout<<endl;
}
cout<<endl;

}
}
[/cpp]

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Thu Mar 11, 2004 12:22 pm

jandujar, my acepted program prints the following output for your given input:

Code: Select all

0.41

0.00

23.94

0.00

20.06

18.22

9.62

12.42

0.00

9.52

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

Post by jandujar » Thu Mar 11, 2004 2:56 pm

Thanks Subeen!!!

So, my code is incorrect :evil: (only works in some cases!!!!)

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

Finaly I Did it

Post by jandujar » Thu Mar 11, 2004 10:53 pm

Thanks to Subeen your output save me.

Finally I implement Prim's Algorithm but i hava "Presentation Errors"

Basicaly I do.



[cpp]
While (num--){
...
...

printf("%.2lf\n\n",salida);

}

[/cpp]

with

[cpp]
While (num--){
...
...

printf("%.2lf\n",salida);
if (num>0){
cout<<endl;
}

}

[/cpp]


I tried too , and have the same problem PE

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Fri Mar 12, 2004 2:32 pm

try this.

scanf("%d",&test);

while(test--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf(...);//inputs
}

//your algo

printf("%.2lf\n",salida);
if(test)printf("\n");
}
cuii e

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

10034 P.E.?

Post by adnan2nd » Sat Jul 03, 2004 1:44 pm

I am getting presentation error WHY?????
Done by prims algo.

Code:
#include<stdio.h>
#include<math.h>
main()
{
int t[100][2],nr[101],n,m,i,j,k;
unsigned long c;
float cost[101][101];
float x[101],y[101],x1,y1;
float min,temp;
scanf("%lu",&c);
while(c)
{ min=0.0;c--;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%f %f",&x1,&y1);
x=x1*10;y=y1*10;
}
for(i=1;i<=n;i++) cost=0.0;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
cost[j]=(x-x[j])*(x-x[j])+(y-y[j])*(y-y[j]);
cost[j]=cost[i][j];
}
for(i=2;i<=n;i++) nr[i]=1;
nr[1]=0;

for(i=1;i<n;i++)
{ m=-2;
for(j=2;j<=n;j++)
{
if(nr[j]!=0 && m==-2) m=j;
if(nr[j]!=0)
if(cost[j][nr[j]]<cost[m][nr[m]]) m=j;
}
temp=cost[m][nr[m]]*100;
temp=sqrt(temp);
min=min+temp ;
nr[m]=0;
for(k=2;k<=n;k++)
{
if(nr[k]!=0)
if(cost[k][nr[k]]>cost[k][m]) nr[k]=m;
}
}
printf("%.2f",min/100);
if(c!=0) printf("\n\n");
}
}
sobhani

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Mon Aug 30, 2004 8:59 pm

I am not sure, but I got RTE for the following input

1

4
0.0 0.0
1.0 0.0
5.0 0.0
7.0 0.0
Where's the "Any" key?

troy
New poster
Posts: 8
Joined: Fri Jul 23, 2004 10:39 am
Location: New Zealand

10034 Freckles - Java Help!! WA

Post by troy » Tue Nov 16, 2004 11:33 am

Hi,

I keep getting WA for this problem.
I used Prims Alg to find the MST.

Is there a special Input case Im Missing?

Any suggestions?


// Code content Removed //.

Post Reply

Return to “Volume 100 (10000-10099)”