Σελίδα 1 από 4

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 4:14 pm
από stathis
Δείξτε εδώ τις λύσεις σας!

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 4:19 pm
από 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;
}

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 4:35 pm
από 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;
}

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 4:39 pm
από 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;
}

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 4:48 pm
από 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();
}

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 5:31 pm
από 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

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 5:41 pm
από 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 αυτό...

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 6:17 pm
από thelastnicholas
Τα άχρηστα printf/cout σας τρώνε άχρηστο χρόνο. Μην τα βάζετε στις υποβολές σας.

Θα δούμε τον συνολικό χρόνο όταν θα μας στείλουν τα reports.

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 6:19 pm
από sotiris
koitaksa ligo tis lisis sas , oxi kai toso kala alla nomizo kati lipi se kapious. tha to koitakso argotera.

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 6:57 pm
από 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

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 6:58 pm
από thelastnicholas
Για του Λυκείου λες ή του Γυμνασίου? Εσυ παίρνεις μέρος?

Edit: Δεν είδα το post σου. Στον σωτήρη αναφερόμουν.

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 7:00 pm
από kernelpanic
Ναι καλε, 3η γυμνασίου(airforce)
Σόρι για το μπέρδεμα, βαριόμουν ν'αλλάξω το πληκτρολόγιο :P

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 7:25 pm
από chris
Εγώ έκανα printf όλο το airforce.in... :oops: :oops: :oops:

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 7:31 pm
από kernelpanic
Όταν ακόμη ήμουν νουμπάς στον προγραμματισμό, είχα φτιάξει ένα προγραμματάκι σε q-basic που έφτιαχνε μεγάλους και πολλούς τυχαίους αριθμούς και τους πρίνταρε.
Στον 386:
Με πριντ: 11,5 λεπτά
Χωρίς: 9.9 δεύτερα

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 8:01 pm
από Ελεύθεροσκοπευτής
καταρχάς βε-βλαμμένο το τεστκέης :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);
}

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 8:43 pm
από 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:

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

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

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

PS. Sorry for doubleposting

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 8:52 pm
από 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

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 9:55 pm
από Ελεύθεροσκοπευτής
@στάθης
ναι, και μένα μάρεσε η λύση μου :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:

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

Δημοσιεύτηκε: Δευ Μαρ 16, 2009 10:02 pm
από 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)².