Λύσεις Β' Φάσης
Δημοσιεύτηκε: Δευ Μαρ 16, 2009 4:14 pm
Δείξτε εδώ τις λύσεις σας!
Κώδικας: Επιλογή όλων
/*
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;
}
Κώδικας: Επιλογή όλων
#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;
}
Κώδικας: Επιλογή όλων
/*
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;
}
Κώδικας: Επιλογή όλων
#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();
}
Κώδικας: Επιλογή όλων
#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;
}
Κώδικας: Επιλογή όλων
/*
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;
}
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;}
Κώδικας: Επιλογή όλων
/*
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);
}
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);
Όχι γιατί ο χρόνος εξαρτάται από τη χρήση πόρων και από το hardware, και εμείς δεν έχουμε το ίδιο.compileGuy έγραψε:Εδώ και η δικιά μου!! Θα ήταν καλό να παραθέταμε και χρόνους!! τι λέτε??
Για 1000 αεροπλάνα 16ms
Κώδικας: Επιλογή όλων
#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;
}
Κώδικας: Επιλογή όλων
....
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];
}
.....