Λύσεις Β' Φάσης

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Λύσεις Β' Φάσης

Δημοσίευση από stathis »

Δείξτε εδώ τις λύσεις σας!
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από thetrojan01 »

Κώδικας: Επιλογή όλων

/*
  LANG: C++
  TASK: airforce
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_N 1000

int main()
{
	register int i, j;/* Save to CPU registers if possible */
	int N, minpos[2], aeroskafos[MAX_N][3];
	double min, distance;
	FILE *fp;
	
	fp = fopen("airforce.in", "r");
	fscanf(fp, "%d", &N); 
	
	/* Load coordinates (data) - Input */
	for(i=0; i < N; ++i)
	{
		fscanf(fp, "%d %d %d\n", 
				&aeroskafos[i][0], &aeroskafos[i][1], &aeroskafos[i][2]);
	}
	fclose(fp);

	/*Suppose that the smallest distance is between the 1st (no. 0) and the 2nd (no. 1) plane */
	min = pow(   
			pow((aeroskafos[1][0]-aeroskafos[0][0]),2)+
			pow((aeroskafos[1][1]-aeroskafos[0][1]),2) + 
			pow((aeroskafos[1][2]-aeroskafos[0][2]),2)
			, 0.5);
	minpos[0]=0;
	minpos[1]=1;
	
	/* Main Algorithm */
	for (i=0; i < N; ++i)
	{
		for (j=i+1; j < N; ++j)
		{
			/* Distance Calculation */
			distance = pow(   
					pow((aeroskafos[j][0]-aeroskafos[i][0]),2)+
					pow((aeroskafos[j][1]-aeroskafos[i][1]),2) + 
					pow((aeroskafos[j][2]-aeroskafos[i][2]),2)
					, 0.5);
			/* Greedy Method. If this is smaller, keep this. */
			if(distance < min)
			{
				min = distance;
				minpos[0] = i;
				minpos[1] = j;
			}
		}
	}
	
	
	/* Print to file the two planes with danger of colision  (information) - Output */
	fp=fopen("airforce.out", "w");	
	/* minpos[0]+1 because In C++ I count from 0 to N-1 but the output is values from 1 up to N */
	fprintf(fp, "%d %d\n", minpos[0]+1, minpos[1]+1);
	fclose(fp);
	/* Returns 0 if no problems were caused during program's run */
	return 0;
}
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από thelastnicholas »

Πάρτε και μια απο μένα.

Κώδικας: Επιλογή όλων

#include <fstream>
using namespace std;

int N, array[100000][3];

int main (){

ifstream in ("airforce.in");
ofstream out ("airforce.out");
in>>N;

for(int i=0;i<N;i++)
 in>>array[i][0]>>array[i][1]>>array[i][2];

int a,b;
double min1=999999999,tmp;

for(int i=0;i<N;++i)
 for(int j=i+1;j<N;++j){

    tmp=(array[i][0]-array[j][0])*(array[i][0]-array[j][0])+ (array[i][1]-array[j][1])*(array[i][1]-array[j][1]) +(array[i][2]-array[j][2])*(array[i][2]-array[j][2]) ;

 if(tmp < min1 ){ min1=tmp;  a=i;b=j; }
}
out<<a+1<<" "<<b+1<<endl;
}
Άβαταρ μέλους
ioannidis007
Δημοσιεύσεις: 29
Εγγραφή: Τετ Δεκ 17, 2008 1:08 am
Επικοινωνία:

Re: Λύσεις Β' Φάσης

Δημοσίευση από ioannidis007 »

η λύση μου:
http://pastebin.com/f48708e3f

ή εδώ:

Κώδικας: Επιλογή όλων

/*
LANG: C++
TASK: evripos
*/
#include<iostream>
#include<algorithm>
#include<math.h>

#define inf 9999999

using namespace std;

struct poinT{
  int x,y;
  bool operator<(const poinT &a) const
  {
    return this->x < a.x;
  }
};


float dist(int &ax, int &ay, int &bx, int &by)
{
  return (float)pow((double)((ax-bx)*(ax-bx) + (ay-by)*(ay-by)) , 0.5);
}

int round(const float &a)
{
  return (int)(a+0.5);
}

int main(void)
{
  FILE *fin=fopen("evripos.in","r");
  int n;
  poinT z;
  fscanf(fin,"%d\n%d %d\n",&n ,&z.x ,&z.y);
  poinT point[n+2];
  float length[n+2][n+2];
  float path[n+2][n+2];
  float buf,l[n+2];
  for(int i=1;i<=n;++i)
    fscanf(fin,"%d %d\n", &point[i].x, &point[i].y);
  fclose(fin);
  sort(point+1, point + n);
  point[n+1].x=z.x; point[n+1].y=z.y;
  point[0].x=0; point[0].y=0;
  for(int i=0;i<=n+1;++i)
    for(int j=0;j<=n+1;++j){
      length[i][j] = dist(point[i].x, point[i].y, point[j].x, point[j].y);
      path[i][j]= 0;
    }

  for(int i=0;i<=n+1;++i)
    for(int j=i+1;j<=n+1;++j)
      for(int k=i;k<=j-1;++k)
	path[i][j] = path[i][j] + length[k][k+1];

  l[0]=0;
  l[1]=2*length[0][1];
  for(int i=2;i<=n+1;++i)
    l[i]=inf;
  
  for(int i=2;i<=n+1;++i)
    for(int k=i-2;k>=0;--k){  
      buf = l[k+1] + path[k+1][i] - length[k][k+1] + length[k][i];
      if(buf<l[i])
	l[i]=buf;
    }
  FILE *fout=fopen("evripos.out","w");  
  fprintf(fout,"%d\n",round(l[n+1]));
  fclose(fout);

  return 0;
}
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από thelastnicholas »

Και η δικιά μου

Κώδικας: Επιλογή όλων

#include <fstream>
#include <cmath>
#include <algorithm>
#include <limits>

using namespace std;

const double inf = numeric_limits<double>::max();

double dist [205][205] = {0};
double res  [205][205] = {0};
int N (0);


struct point {
 double x,y;
 point(int a,int b):x(a),y(b){} 
 point(){}
}points[205];

inline const bool operator < ( const point &a, const point &b ){
  return a.x < b.x;
}

int main()
{

 ifstream in  ("evripos.in");
 ofstream out ("evripos.out");

 in>>N;
 N+=2;

 int t1,t2;

 points[0]= point(0,0);

 for(int i=1;i<N;++i){
  in>>t1>>t2;
  points[i]=point(t1,t2);
 }
 in.close();
 sort(points,points+N);

 for(int i=0;i<N;++i)
  for(int j=0;j<N;++j){
    dist [i][j]= sqrt( pow(points[i].x-points[j].x,2) + pow(points[i].y-points[j].y,2));;
    res[i][j]=inf;
  }

 res[0][0]=0;
 for(int i=0;i<N;++i)
  for(int j=0;j<N;++j){
   res[i+1][i]      = min (res[i+1][i],   res[i][j] + dist[j][i+1]);
   res[i+1][j]      = min (res[i+1][j],   res[i][j] + dist[i][i+1]);
   res[i+1][i+1]   = min (res[i+1][i+1], res[i][j] + dist[i][i+1] + dist[i+1][j]);  
  }
 
 out<<round(res[N-1][N-1])<<endl;
 out.close();
}
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από compileGuy »

Εδώ και η δικιά μου!! Θα ήταν καλό να παραθέταμε και χρόνους!! τι λέτε??

Κώδικας: Επιλογή όλων

#include <iostream>
#include <fstream>
using namespace std;

int main()
{ 
    // Orismos Metablitwn
    ifstream TextIn;
    ofstream TextOut;
    int *stoixeia,N,ST1=0,ST2=0;
    double dist_sq,min=10000;    
    TextIn.open ("airforceae.in",ios::in);
    TextIn>>N;
    stoixeia = new int [N*3];
    for (int k=0; k<N; k++)
    {
        TextIn>>stoixeia[k]>>stoixeia[N+k]>>stoixeia[2*N+k];
    }
    TextIn.close();
    for (int i=0; i<N; i++)
    {
        for (int j=i+1; j<N; j++)
        {
            dist_sq=(stoixeia[j]-stoixeia[i])*(stoixeia[j]-stoixeia[i])+
                        (stoixeia[N+j]-stoixeia[N+i])*(stoixeia[N+j]-stoixeia[N+i])+
                        (stoixeia[2*N+j]-stoixeia[2*N+i])*(stoixeia[2*N+j]-stoixeia[2*N+i]);
            if (dist_sq<min)
            {
                         ST1=i+1;
                         ST2=j+1;
                         min=dist_sq;
            };
        }
    }
    TextOut.open ("airforce.out" , ios::out);
    TextOut<<ST1<<" "<<ST2<<"\n";
    TextOut.close();
    return 0;
}
Για 1000 αεροπλάνα 16ms
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Λύσεις Β' Φάσης

Δημοσίευση από chris »

Έχω κάνει αρκετές δοκιμές, και δεν ξέρω πια είναι η τελική έκδοση...
Νομίζω πως έστειλα αυτήν:

Κώδικας: Επιλογή όλων

/*
LANG: C
TASK: airforce
*/


#include <stdio.h>
#include <math.h>

int main(void){
	FILE*fin; 
	FILE*fout; 
	int i,j,n,cntr; 
	int aircraft1[1001],aircraft2[1001],aircraft3[1001];
	int dist1,dist2;
	int x1,x2,y1,y2,z1,z2,t1,t2,t3;
	int min1,min2;
	float min3; 
	float dist3;
	fin=fopen("airforce.in","r"); 
		
	fseek(fin, 0L, SEEK_SET );
	fscanf(fin,"%d",&n);
	for(i=1;i<=n;i++){
			fscanf(fin,"%d",&aircraft1[i]); 
			fscanf(fin,"%d",&aircraft2[i]); 
			fscanf(fin,"%d",&aircraft3[i]);
	}
			if(aircraft1[1]>aircraft1[2]){
				x2=aircraft1[1];
				x1=aircraft1[2];
			}
			
			else{
				x1=aircraft1[1];
				x2=aircraft1[2];
			}	
			if(aircraft2[1]>aircraft2[2]){
				y2=aircraft2[1];
				y1=aircraft2[2];
			}
			else{
				y1=aircraft2[1];
				y2=aircraft2[2];
			}
			if(aircraft3[1]>aircraft3[2]){
				z2=aircraft3[1];
				z1=aircraft3[2];
			}
			else{
				z1=aircraft3[1];
				z2=aircraft3[2];
			}
			
			t1=pow((x2-x1),2);
			t2=pow((y2-y1),2);
			t3=pow((z2-z1),2);
			dist3=pow((t1+t2+t3),0.5);
			dist1=1;
			dist2=2;
			//printf("The distance between plane %d and plane %d is %f\n\n", dist1[cntr], dist2[cntr] , dist3[cntr]);  		
			min1=dist1;
			min2=dist2;
			min3=dist3;
	
	
	cntr=1;
	for(i=1;i<n;i++){
		for(j=n;j>i;j--){

			dist1=i;
			dist2=j;
			if(aircraft1[dist1]>aircraft1[dist2]){
				x2=aircraft1[dist1];
				x1=aircraft1[dist2];
			}
			
			else{
				x1=aircraft1[dist1];
				x2=aircraft1[dist2];
			}	
			if(aircraft2[dist1]>aircraft2[dist2]){
				y2=aircraft2[dist1];
				y1=aircraft2[dist2];
			}
			else{
				y1=aircraft2[dist1];
				y2=aircraft2[dist2];
			}
			if(aircraft3[dist1]>aircraft3[dist2]){
				z2=aircraft3[dist1];
				z1=aircraft3[dist2];
			}
			else{
				z1=aircraft3[dist1];
				z2=aircraft3[dist2];
			}
			
			t1=pow((x2-x1),2);
			t2=pow((y2-y1),2);
			t3=pow((z2-z1),2);
			dist3=pow((t1+t2+t3),0.5);
			dist1[cntr], dist2[cntr] , dist3[cntr]);  
			printf("%d-%d %f\n",dist1,dist2,dist3);
			if(dist3<min3){
			min1=dist1;
			min2=dist2;
			min3=dist3;
			}
			/*---*/
		}
	}
	
	fout=fopen("airforce.out","w");
	if(min1<min2){
		fprintf(fout,"%d %d\n",min1,min2);
	}
	else{
		fprintf(fout,"%d %d\n",min2,min1);
	}
	fclose(fin);
	fclose(fout);
	
	printf("\n\n Finished...\n\n");
	return 0;
}			
EDIT: Ωχ, εδώ εκτύπωνα όλο το airforce.in... Τρώει αρκετά ms αυτό...
Τελευταία επεξεργασία από το μέλος chris την Δευ Μαρ 16, 2009 7:23 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από thelastnicholas »

Τα άχρηστα printf/cout σας τρώνε άχρηστο χρόνο. Μην τα βάζετε στις υποβολές σας.

Θα δούμε τον συνολικό χρόνο όταν θα μας στείλουν τα reports.
Τελευταία επεξεργασία από το μέλος thelastnicholas την Δευ Μαρ 16, 2009 6:55 pm, έχει επεξεργασθεί 1 φορά συνολικά.
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από pman »

koitaksa ligo tis lisis sas , oxi kai toso kala alla nomizo kati lipi se kapious. tha to koitakso argotera.
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Λύσεις Β' Φάσης

Δημοσίευση από kernelpanic »

SOTIRIS έγραψε:koitaksa ligo tis lisis sas , oxi kai toso kala alla nomizo kati lipi se kapious. tha to koitakso argotera.
mpros nte dwse kwdika...

Κώδικας: Επιλογή όλων

/*LANG:C
TASK:airforce*/
#include"stdio.h"
//h stdio trexei kalytera se linux
FILE * inpouty;//ena xreiazomaste
short int j,num=0,a=0,b=1,i,dx,dy,dz,*where,plane[1000][3];
long long minim=100000001,check;//giati long long? 8a deis...
unsigned char text[17000],*point;//blepe panw

int main(){
 inpouty=fopen("airforce.in","rb");
 fseek(inpouty,0,SEEK_END);//telos arxeiou
 a=ftell(inpouty);//telos - arxh
 fseek(inpouty,0,SEEK_SET);
 fread((void *)text,1,5,inpouty);//4pshfios max + enter
 point=text;//diabazei
 while(*point>47)point++;//'0'==48, teleytaio pshfio
 point--;//mono etsi doyleyei :oops: 
 for(;point>=text;point--){
  num+=(*point-48)*b;//b=power of 10
  b*=10;}//diabazw anapoda giati alliws den 3erw an to prwto pshfio einai dekades monades h ti allo
 b=1;
 if(num<1000){
  if(num<100){
   fseek(inpouty,-2,SEEK_CUR);//file cursor goes a little back
   a-=3;}//perimene...
  else{
   fseek(inpouty,-1,SEEK_CUR);
   a-=4;}}
  else a-=5;
 fread((void *)text,1,a,inpouty);//diabazw me th mia to ypoloipo arxeio & to bazw sto text
 point=text+a-1;//telos arxeioy - 1, text=arxh pinaka
 where=&plane[num-1][2];//as arxisei h anagnwsh
 for(;point>=text;point--){
  for(;*point>44;point--){
   if(*point=='-'){*where*=-1;continue;}//arnhtikos
   *where+=(*point-48)*b;
   b*=10;i=1;}//perase ap to broxo??
   if(i) where--;//alliws o xarakthras htan enter
   i=0;
   b=1;}
 j=num-1;
 for(num=0;num<j;num++){
  for(i=num+1;i<=j;i++){
   dx=plane[i][0]-plane[num][0];//thn pra3h 8a thn kanw mia fora
   dy=plane[i][1]-plane[num][1];
   dz=plane[i][2]-plane[num][2];
   check=dx*dx+dy*dy+dz*dz;//an sqrt(x)>sqrt(y) tote x>y 
   if(minim>check){minim=check;a=num;b=i;}}}//NEW RECORD!!
 freopen("airforce.out","w",inpouty);
 fprintf (inpouty,"%i %i\n",(a+1),(b+1));
 fclose(inpouty);
 return 0;}
Σε ακραίες περιπτώσεις (1000,1000,1000 - -1000,-1000,-1000)το αποτέλεσμα θα είναι πάνω από unsigned long(4.264 χιλιάδες) και δε θέλω να ρολάρει απ'την αρχή.
Η τελευταία έκδοση μετρούσε ανάποδα και γλύτωνε μια μεταβλητή--κρίμα που την σκότωσε το τεβλαμμένο τεστκασε 2 :|

Η μέγιστη απόσταση μέσα στον κύβο 2000χ2000χ2000 είναι 3464,1:P
Τελευταία επεξεργασία από το μέλος kernelpanic την Δευ Μαρ 16, 2009 7:06 pm, έχει επεξεργασθεί 3 φορές συνολικά.
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από thelastnicholas »

Για του Λυκείου λες ή του Γυμνασίου? Εσυ παίρνεις μέρος?

Edit: Δεν είδα το post σου. Στον σωτήρη αναφερόμουν.
Τελευταία επεξεργασία από το μέλος thelastnicholas την Δευ Μαρ 16, 2009 7:24 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Λύσεις Β' Φάσης

Δημοσίευση από kernelpanic »

Ναι καλε, 3η γυμνασίου(airforce)
Σόρι για το μπέρδεμα, βαριόμουν ν'αλλάξω το πληκτρολόγιο :P
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Λύσεις Β' Φάσης

Δημοσίευση από chris »

Εγώ έκανα printf όλο το airforce.in... :oops: :oops: :oops:
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Λύσεις Β' Φάσης

Δημοσίευση από kernelpanic »

Όταν ακόμη ήμουν νουμπάς στον προγραμματισμό, είχα φτιάξει ένα προγραμματάκι σε q-basic που έφτιαχνε μεγάλους και πολλούς τυχαίους αριθμούς και τους πρίνταρε.
Στον 386:
Με πριντ: 11,5 λεπτά
Χωρίς: 9.9 δεύτερα
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
Ελεύθεροσκοπευτής
Δημοσιεύσεις: 33
Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am

Re: Λύσεις Β' Φάσης

Δημοσίευση από Ελεύθεροσκοπευτής »

καταρχάς βε-βλαμμένο το τεστκέης :geek: :P :P
και στη συνέχεια:

Κώδικας: Επιλογή όλων

/*
LANG: C++
TASK: evripos
*/
#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;


int main() {
  int n,x,y;
  ifstream file_in;
  ofstream file_out;
  file_in.open ("evripos.in");
  file_in >> n>>x>>y;
  int A[n][2];
  for(int k=0;k<n;k++) {
    file_in >> A[k][1]>>A[k][2];
  }
  file_in.close();
  file_out.open ("evripos.out");
  int B[2];
  bool c=true;
  while(c==true) {
    c=false;
    for(int l=0;l<(n-1);l++) {
      if(A[l][1]>A[l+1][1]) {
        B[0] = A[l][1];
        B[1] = A[l][2];
        A[l][1] = A[l+1][1];
        A[l][2] = A[l+1][2];
        A[l+1][1] = B[0];
        A[l+1][2] = B[1];
        c=true;
      }
    }
  }
  double syn=2000000.;
  for(int bi=(pow(2,n));bi<(pow(2,n+1));bi=bi+1) {
    int bivar=bi;
    int nvar=0;
    double prwi=0.,apog=0.;
    int prwix=0,prwiy=0,apogx=0,apogy=0;
    while(bivar>1) {
      if(bivar%2==0) {
        prwi=prwi+sqrt(pow(A[nvar][1]-prwix,2)+pow(A[nvar][2]-prwiy,2));

        bivar=(bivar/2);
        prwix=A[nvar][1];
        prwiy=A[nvar][2];
      }
      else {
        apog=apog+sqrt(pow(A[nvar][1]-apogx,2)+pow(A[nvar][2]-apogy,2));
        bivar=((bivar-1)/2);
        apogx=A[nvar][1];
        apogy=A[nvar][2];
      }

      nvar++;
    }
    prwi=prwi+sqrt(pow(x-prwix,2)+pow(y-prwiy,2));
    apog=apog+sqrt(pow(x-apogx,2)+pow(y-apogy,2));
    if(prwi+apog<syn) {
      syn=prwi+apog;
    }
  }
  int tlk=int(syn+0.5);
  file_out<<tlk<<"\n";
  file_out.close();
  return(0);
}
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από thetrojan01 »

chris έγραψε:Έχω κάνει αρκετές δοκιμές, και δεν ξέρω πια είναι η τελική έκδοση...
Νομίζω πως έστειλα αυτήν:

Κώδικας: Επιλογή όλων

/*
LANG: C
TASK: airforce
*/ [...]
	for(i=1;i<n;i++){
		for(j=n;j>i;j--){

			dist1=i;
			dist2=j;
			if(aircraft1[dist1]>aircraft1[dist2]){
				x2=aircraft1[dist1];
				x1=aircraft1[dist2];
			}
			
			else{
				x1=aircraft1[dist1];
				x2=aircraft1[dist2];
			}	
			if(aircraft2[dist1]>aircraft2[dist2]){
				y2=aircraft2[dist1];
				y1=aircraft2[dist2];
			}
			else{
				y1=aircraft2[dist1];
				y2=aircraft2[dist2];
			}
			if(aircraft3[dist1]>aircraft3[dist2]){
				z2=aircraft3[dist1];
				z1=aircraft3[dist2];
			}
			else{
				z1=aircraft3[dist1];
				z2=aircraft3[dist2];
			}
			
			t1=pow((x2-x1),2);
			t2=pow((y2-y1),2);
			t3=pow((z2-z1),2);
			dist3=pow((t1+t2+t3),0.5);
	
EDIT: Ωχ, εδώ εκτύπωνα όλο το airforce.in... Τρώει αρκετά ms αυτό...

Δε χρειαζόταν αυτό. Όταν υψώνεις κάτι στο τετράγωνο θα είναι ΠΑΝΤΑ θετικός!!! η ρίζα θεωρείται στη math.h ως η θετική ρίζα. :roll:
Τελευταία επεξεργασία από το μέλος thetrojan01 την Δευ Μαρ 16, 2009 8:50 pm, έχει επεξεργασθεί 1 φορά συνολικά.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Λύσεις Β' Φάσης

Δημοσίευση από thetrojan01 »

compileGuy έγραψε:Εδώ και η δικιά μου!! Θα ήταν καλό να παραθέταμε και χρόνους!! τι λέτε??
Για 1000 αεροπλάνα 16ms
Όχι γιατί ο χρόνος εξαρτάται από τη χρήση πόρων και από το hardware, και εμείς δεν έχουμε το ίδιο.

Ερώτηση: Αν ήταν να κάνουμε μια τέτοια σύγκριση, θα συγκρίναμε τις πολυπλοκότητες των αλγορίθμων μας;

PS. Sorry for doubleposting
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Λύσεις Β' Φάσης

Δημοσίευση από stathis »

Ελεύθεροσκοπευτής, ενδιαφέρον η υλοποίησή σου σε 2^N.

Άντε, πάρτε και τη δική μου.

Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

struct pt {
  int x, y;
};

int compare(const void *va, const void *vb)
{
  return ((struct pt*)va)->x - ((struct pt*)vb)->x;
}

int main(void)
{
  struct pt p[203];
  double ans[203][203], dist[203][203];
  int i, j, N;
  
  FILE *fin = fopen("evripos.in", "r");
  fscanf(fin, "%d\n%d %d\n", &N, &p[1].x, &p[1].y); 
  p[2].x = p[2].y = 0;
  for (i=1;i<=N;i++)
      fscanf(fin, "%d %d\n", &p[i+2].x, &p[i+2].y);
  fclose(fin);
  
  N += 2;
  qsort(&p[1], N, sizeof(struct pt), compare);
  
  for(i=1;i<=N;i++)
      for(j=1;j<=N;j++) {
          dist[i][j] = sqrt( (p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y) );
          ans[i][j] = 999999999;
      }
  
  ans[1][1] = 0;
  
  for (i=1;i<=N;i++)
      for (j=1;j<=N;j++) {
          ans[i+1][i] = (ans[i+1][i] > ans[i][j]+dist[j][i+1]) ? ans[i][j]+dist[j][i+1] : ans[i+1][i];
          ans[i+1][j] = (ans[i+1][j] < ans[i][j]+dist[i][i+1]) ? ans[i+1][j] : ans[i][j]+dist[i][i+1];
          ans[i+1][i+1] = (ans[i+1][i+1] < ans[i][j]+dist[i][i+1]+dist[j][i+1]) ? ans[i+1][i+1] : ans[i][j]+dist[i][i+1]+dist[j][i+1];
      }
  
  FILE *fout = fopen("evripos.out", "w");
  fprintf(fout, "%d\n", (int)round(ans[N][N]));
  fclose(fout);
  
  return 0;
}
0.003 s για N=200
Ελεύθεροσκοπευτής
Δημοσιεύσεις: 33
Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am

Re: Λύσεις Β' Φάσης

Δημοσίευση από Ελεύθεροσκοπευτής »

@στάθης
ναι, και μένα μάρεσε η λύση μου :P ουσιαστικά χρησιμοποίησα τον τρόπο να περνάς από δεκαδικό σε 2αδικό σύστημα αρίθμισης γιατι θα μου τρωγε περισσότερα ms να ορίσω την πρόσθεση δυαδικών string-οποιόντας τα και αποστριγκοποιόντας τα κάθε φορά :Ρ :D

ρε σύ δεν πιάνω τον κώδικά σου στο σημείο:

Κώδικας: Επιλογή όλων

....
  for (i=1;i<=N;i++)
      for (j=1;j<=N;j++) {
          ans[i+1][i] = (ans[i+1][i] > ans[i][j]+dist[j][i+1]) ? ans[i][j]+dist[j][i+1] : ans[i+1][i];
          ans[i+1][j] = (ans[i+1][j] < ans[i][j]+dist[i][i+1]) ? ans[i+1][j] : ans[i][j]+dist[i][i+1];
          ans[i+1][i+1] = (ans[i+1][i+1] < ans[i][j]+dist[i][i+1]+dist[j][i+1]) ? ans[i+1][i+1] : ans[i][j]+dist[i][i+1]+dist[j][i+1];
      }
.....
τι ακριβώς κάνεις και τι είναι τα "?" και ":" ;;;

επίσης αν γίνεται κάποιος που το χει λύσει σε κάτι διαφορετικό από ν! και 2^ν να εξηγήσει λίγο τον αλγόριθμο, γιατί με χει φάει αυτό το πράγμα :roll:
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Λύσεις Β' Φάσης

Δημοσίευση από stathis »

Είναι inline ifs :P
var = (conditions) ? TRUE : FALSE;

Η λύση μου, όπως και φαντάζομαι των υπολοίπων N² υλοποιήσεων είναι Dynamic Programming. Σκέψου το σαν μείγμα bruteforce-greedy με τα καλά και των δύο. Βλέπω το πρόβλημα ως ένα επίπεδο που έχει δύο διαδρομές οι οποίες μόνο πηγαίνουν.

Το ans έχει ως indexes το που βρίσκεται η κάθε διαδρομή-σχοινί. Δηλαδή με ans[1][2] σημαίνει πως το ένα σχοινί είναι στο σημείο 1, και το δεύτερο στο σημείο δύο. Η τιμή που αποδίδεται σε αυτή την "κατάσταση" (DP state) είναι η συνολική διανυόμενη διαδρομή ως εκείνα τα σημεία. Επομένως, όταν φτάσει στο τελικό σημείο, η λύση μας βρίσκεται στο ans[N][N], εφόσον εκεί τερματίζει.

Να σημειώσω πως στα σημεία του συστήματος προσθέτω και την αρχή (0,0) όπως και το γραφείο-τέλος, επομένως η λύση μου για να ακριβολογούμε είναι (N+2)².
Απάντηση