Λύσεις Β' Φάσης
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Λύσεις Β' Φάσης
Δείξτε εδώ τις λύσεις σας!
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Λύσεις Β' Φάσης
Κώδικας: Επιλογή όλων
/*
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.
-
- Δημοσιεύσεις: 74
- Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm
Re: Λύσεις Β' Φάσης
Πάρτε και μια απο μένα.
Κώδικας: Επιλογή όλων
#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: Λύσεις Β' Φάσης
η λύση μου:
http://pastebin.com/f48708e3f
ή εδώ:
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;
}
-
- Δημοσιεύσεις: 74
- Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm
Re: Λύσεις Β' Φάσης
Και η δικιά μου
Κώδικας: Επιλογή όλων
#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: Λύσεις Β' Φάσης
Εδώ και η δικιά μου!! Θα ήταν καλό να παραθέταμε και χρόνους!! τι λέτε??
Για 1000 αεροπλάνα 16ms
Κώδικας: Επιλογή όλων
#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;
}
Re: Λύσεις Β' Φάσης
Έχω κάνει αρκετές δοκιμές, και δεν ξέρω πια είναι η τελική έκδοση...
Νομίζω πως έστειλα αυτήν:
EDIT: Ωχ, εδώ εκτύπωνα όλο το airforce.in... Τρώει αρκετά ms αυτό...
Νομίζω πως έστειλα αυτήν:
Κώδικας: Επιλογή όλων
/*
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;
}
Τελευταία επεξεργασία από το μέλος chris την Δευ Μαρ 16, 2009 7:23 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
-
- Δημοσιεύσεις: 74
- Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm
Re: Λύσεις Β' Φάσης
Τα άχρηστα printf/cout σας τρώνε άχρηστο χρόνο. Μην τα βάζετε στις υποβολές σας.
Θα δούμε τον συνολικό χρόνο όταν θα μας στείλουν τα reports.
Θα δούμε τον συνολικό χρόνο όταν θα μας στείλουν τα reports.
Τελευταία επεξεργασία από το μέλος thelastnicholas την Δευ Μαρ 16, 2009 6:55 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Re: Λύσεις Β' Φάσης
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: Λύσεις Β' Φάσης
mpros nte dwse kwdika...SOTIRIS έγραψε:koitaksa ligo tis lisis sas , oxi kai toso kala alla nomizo kati lipi se kapious. tha to koitakso argotera.
Κώδικας: Επιλογή όλων
/*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;}
Η τελευταία έκδοση μετρούσε ανάποδα και γλύτωνε μια μεταβλητή--κρίμα που την σκότωσε το τεβλαμμένο τεστκασε 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.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
-
- Δημοσιεύσεις: 74
- Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm
Re: Λύσεις Β' Φάσης
Για του Λυκείου λες ή του Γυμνασίου? Εσυ παίρνεις μέρος?
Edit: Δεν είδα το post σου. Στον σωτήρη αναφερόμουν.
Edit: Δεν είδα το post σου. Στον σωτήρη αναφερόμουν.
Τελευταία επεξεργασία από το μέλος thelastnicholas την Δευ Μαρ 16, 2009 7:24 pm, έχει επεξεργασθεί 1 φορά συνολικά.
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: Λύσεις Β' Φάσης
Ναι καλε, 3η γυμνασίου(airforce)
Σόρι για το μπέρδεμα, βαριόμουν ν'αλλάξω το πληκτρολόγιο
Σόρι για το μπέρδεμα, βαριόμουν ν'αλλάξω το πληκτρολόγιο
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
Re: Λύσεις Β' Φάσης
Εγώ έκανα printf όλο το airforce.in...
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: Λύσεις Β' Φάσης
Όταν ακόμη ήμουν νουμπάς στον προγραμματισμό, είχα φτιάξει ένα προγραμματάκι σε q-basic που έφτιαχνε μεγάλους και πολλούς τυχαίους αριθμούς και τους πρίνταρε.
Στον 386:
Με πριντ: 11,5 λεπτά
Χωρίς: 9.9 δεύτερα
Στον 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.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
-
- Δημοσιεύσεις: 33
- Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am
Re: Λύσεις Β' Φάσης
καταρχάς βε-βλαμμένο το τεστκέης
και στη συνέχεια:
και στη συνέχεια:
Κώδικας: Επιλογή όλων
/*
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);
}
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Λύσεις Β' Φάσης
chris έγραψε:Έχω κάνει αρκετές δοκιμές, και δεν ξέρω πια είναι η τελική έκδοση...
Νομίζω πως έστειλα αυτήν:EDIT: Ωχ, εδώ εκτύπωνα όλο το airforce.in... Τρώει αρκετά ms αυτό...Κώδικας: Επιλογή όλων
/* 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);
Δε χρειαζόταν αυτό. Όταν υψώνεις κάτι στο τετράγωνο θα είναι ΠΑΝΤΑ θετικός!!! η ρίζα θεωρείται στη math.h ως η θετική ρίζα.
Τελευταία επεξεργασία από το μέλος thetrojan01 την Δευ Μαρ 16, 2009 8:50 pm, έχει επεξεργασθεί 1 φορά συνολικά.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Λύσεις Β' Φάσης
Όχι γιατί ο χρόνος εξαρτάται από τη χρήση πόρων και από το hardware, και εμείς δεν έχουμε το ίδιο.compileGuy έγραψε:Εδώ και η δικιά μου!! Θα ήταν καλό να παραθέταμε και χρόνους!! τι λέτε??
Για 1000 αεροπλάνα 16ms
Ερώτηση: Αν ήταν να κάνουμε μια τέτοια σύγκριση, θα συγκρίναμε τις πολυπλοκότητες των αλγορίθμων μας;
PS. Sorry for doubleposting
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Λύσεις Β' Φάσης
Ελεύθεροσκοπευτής, ενδιαφέρον η υλοποίησή σου σε 2^N.
Άντε, πάρτε και τη δική μου.
0.003 s για N=200
Άντε, πάρτε και τη δική μου.
Κώδικας: Επιλογή όλων
#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;
}
-
- Δημοσιεύσεις: 33
- Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am
Re: Λύσεις Β' Φάσης
@στάθης
ναι, και μένα μάρεσε η λύση μου ουσιαστικά χρησιμοποίησα τον τρόπο να περνάς από δεκαδικό σε 2αδικό σύστημα αρίθμισης γιατι θα μου τρωγε περισσότερα ms να ορίσω την πρόσθεση δυαδικών string-οποιόντας τα και αποστριγκοποιόντας τα κάθε φορά :Ρ
ρε σύ δεν πιάνω τον κώδικά σου στο σημείο:
τι ακριβώς κάνεις και τι είναι τα "?" και ":" ;;;
επίσης αν γίνεται κάποιος που το χει λύσει σε κάτι διαφορετικό από ν! και 2^ν να εξηγήσει λίγο τον αλγόριθμο, γιατί με χει φάει αυτό το πράγμα
ναι, και μένα μάρεσε η λύση μου ουσιαστικά χρησιμοποίησα τον τρόπο να περνάς από δεκαδικό σε 2αδικό σύστημα αρίθμισης γιατι θα μου τρωγε περισσότερα ms να ορίσω την πρόσθεση δυαδικών string-οποιόντας τα και αποστριγκοποιόντας τα κάθε φορά :Ρ
ρε σύ δεν πιάνω τον κώδικά σου στο σημείο:
Κώδικας: Επιλογή όλων
....
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^ν να εξηγήσει λίγο τον αλγόριθμο, γιατί με χει φάει αυτό το πράγμα
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Λύσεις Β' Φάσης
Είναι inline ifs
var = (conditions) ? TRUE : FALSE;
Η λύση μου, όπως και φαντάζομαι των υπολοίπων N² υλοποιήσεων είναι Dynamic Programming. Σκέψου το σαν μείγμα bruteforce-greedy με τα καλά και των δύο. Βλέπω το πρόβλημα ως ένα επίπεδο που έχει δύο διαδρομές οι οποίες μόνο πηγαίνουν.
Το ans έχει ως indexes το που βρίσκεται η κάθε διαδρομή-σχοινί. Δηλαδή με ans[1][2] σημαίνει πως το ένα σχοινί είναι στο σημείο 1, και το δεύτερο στο σημείο δύο. Η τιμή που αποδίδεται σε αυτή την "κατάσταση" (DP state) είναι η συνολική διανυόμενη διαδρομή ως εκείνα τα σημεία. Επομένως, όταν φτάσει στο τελικό σημείο, η λύση μας βρίσκεται στο ans[N][N], εφόσον εκεί τερματίζει.
Να σημειώσω πως στα σημεία του συστήματος προσθέτω και την αρχή (0,0) όπως και το γραφείο-τέλος, επομένως η λύση μου για να ακριβολογούμε είναι (N+2)².
var = (conditions) ? TRUE : FALSE;
Η λύση μου, όπως και φαντάζομαι των υπολοίπων N² υλοποιήσεων είναι Dynamic Programming. Σκέψου το σαν μείγμα bruteforce-greedy με τα καλά και των δύο. Βλέπω το πρόβλημα ως ένα επίπεδο που έχει δύο διαδρομές οι οποίες μόνο πηγαίνουν.
Το ans έχει ως indexes το που βρίσκεται η κάθε διαδρομή-σχοινί. Δηλαδή με ans[1][2] σημαίνει πως το ένα σχοινί είναι στο σημείο 1, και το δεύτερο στο σημείο δύο. Η τιμή που αποδίδεται σε αυτή την "κατάσταση" (DP state) είναι η συνολική διανυόμενη διαδρομή ως εκείνα τα σημεία. Επομένως, όταν φτάσει στο τελικό σημείο, η λύση μας βρίσκεται στο ans[N][N], εφόσον εκεί τερματίζει.
Να σημειώσω πως στα σημεία του συστήματος προσθέτω και την αρχή (0,0) όπως και το γραφείο-τέλος, επομένως η λύση μου για να ακριβολογούμε είναι (N+2)².