10034 - Freckles
Moderator: Board moderators
-
- New poster
- Posts: 44
- Joined: Wed Aug 14, 2002 3:02 am
10034 "Problem A: Freckles" Input/Output & WA
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
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.
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.
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.
I still need help
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?
I have got a "kruskal" algorithm and then I have recode it.
Seems that works , but always give me Wrong Answer. Why?
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
Float -> Double
I tried with all floats to doubles and don't work.
Thanks
Any other suggest?
Thanks
Any other suggest?
I think the problem is output
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?
I write:
while(numtests>0)
cout<<number whith 2 decimal precition (redonded, shall i try truncated?)
cout<<endl;
end while
Is this correct?
INPUT/OUTPUT example
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]
[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]
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
Finaly I Did it
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
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
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
10034 P.E.?
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");
}
}
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
10034 Freckles - Java Help!! WA
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 //.
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 //.