Re: Λύσεις Β' Φάσης
Δημοσιεύτηκε: Δευ Μαρ 16, 2009 10:12 pm
@στάθης είσαι σίγουρος ότι η λύση σου είναι σωστή? Δεν έχω κοιτάξει ακόμα προσεκτικά την λύση σου, απλώς το λέω διότι ως καλύτερη επίλυση στην εκφώνηση είχαν την Ν^3.
(Υπάρχουν τρεις τουλάχιστον αλγοριθμικές επιλύσεις του παραπάνω προβλήματος με πολυπλοκότητα Ο(Ν!), Ο(2Ν) και Ο(Ν3))
Κώδικας: Επιλογή όλων
/*
LANG: C++
TASK: evripos
*/
#include <iostream>
#include <fstream>
#include <cmath>
#define BIG 9007199254740991.0
using namespace std;
struct Point
{
int x,y;
};
int N;
Point p[205];
double sol[205][205];
int n;
void quicksort (int l,int r)
{
int i=l,j=r;
Point m=p[(l+r)/2];
while (i<=j)
{
while (i<=j && p[i].x<m.x) ++i;
while (i<=j && p[j].x>m.x) --j;
if (i<=j)
{
Point x=p[i];
p[i]=p[j];
p[j]=x;
++i;
--j;
}
}
if (l<j) quicksort(l,j);
if (i<r) quicksort(i,r);
}
int main ()
{
ifstream fin ("evripos.in");
fin >> N;
p[1].x=p[1].y=0;
fin >> p[N+2].x >> p[N+2].y;
for (int i=2;i<=N+1;++i)
fin >> p[i].x >> p[i].y;
fin.close();
quicksort(1,N+2);
sol[1][1]=0;
sol[2][1]=sqrt((p[1].x-p[2].x)*(p[1].x-p[2].x)+(p[1].y-p[2].y)*(p[1].y-p[2].y));
for (int i=3;i<=N+2;++i)
for (int j=1;j<=i;++j)
{
if (i==j && i!=N+2)
continue;
if (i>j+1)
{
sol[i][j]=sol[i-1][j]+sqrt((p[i].x-p[i-1].x)*(p[i].x-p[i-1].x)+(p[i].y-p[i-1].y)*(p[i].y-p[i-1].y));
++n;
continue;
}
double MIN=BIG;
for (int k=1;k<j;++k)
{
++n;
double cost=sol[j][k]+sqrt((p[k].x-p[i].x)*(p[k].x-p[i].x)+(p[k].y-p[i].y)*(p[k].y-p[i].y));
if (MIN>cost)
MIN=cost;
}
sol[i][j]=MIN;
}
ofstream fout ("evripos.out");
fout << round(sol[N+2][N+2]) << endl;
fout << n << endl;
return 0;
}
Κώδικας: Επιλογή όλων
chiossif@chiossif-6400:~/Code/PDP_21B/PDP_21_B_GYM$ cat gym.c
#include <stdio.h>
#include <stdlib.h>
int inline int_sqr(int x) {
return x*x;
}
int main(void) {
int *x, *y, *z, d, a, b, s1, s2, s3, s, n, n_1;
register int i, j;
scanf("%d",&n);
n_1=n-1;
x=malloc(n*sizeof(int));
y=malloc(n*sizeof(int));
z=malloc(n*sizeof(int));
for (i=0;i<n;i++)
scanf("%d %d %d", &x[i], &y[i],&z[i]);
d=int_sqr(x[1]-x[0])+int_sqr(y[1]-y[0])+int_sqr(z[1]-z[0]);
a=0;
b=1;
for (i=0;i<n_1;i++)
for (j=i+1;j<n;j++)
if ((s1=int_sqr(x[j]-x[i]))<=d &&
(s2=int_sqr(y[j]-y[i]))<=d &&
(s3=int_sqr(z[j]-z[i]))<=d && (s=s1+s2+s3)<d) {
a=i;
b=j;
d=s;
}
printf("%d %d\n",a+1,b+1);
return 0;
}
chiossif@chiossif-6400:~/Code/PDP_21B/PDP_21_B_GYM$ time ./gym <gym_10000.in
5540 8477
real 0m0.557s
user 0m0.528s
sys 0m0.004s
chiossif@chiossif-6400:~/Code/PDP_21B/PDP_21_B_GYM$
Κώδικας: Επιλογή όλων
PROGRAM evripos;
{LANG: Pascal
TASK: evripos}
USES
SysUtils;
CONST
MaxPoints = 204;
INF = 100000;
TYPE
coordinates = record
X:integer;
Y:integer;
end;
Coordsys = array[1..MaxPoints] of coordinates;
VAR
N,
I,J,K,
d:integer;
q:real;
input,output:text;
points:Coordsys;
l:array[1..MaxPoints,1..MaxPoints] of real;
FUNCTION dist(a,b:coordinates):real; //euclidean distiance//
BEGIN
dist:=sqrt(sqr(a.X-b.X)+sqr(a.Y-b.Y))
END;
(*---------------- start of quicksort ------------------*)
PROCEDURE swap(VAR a, b: coordinates);
VAR
t: integer;
BEGIN
t := a.X;
a.X := b.X;
b.X := t;
t := a.Y;
a.Y := b.Y;
b.Y := t;
END;
FUNCTION Split(start, stop: integer): integer;
VAR
left, right: integer;
pivot: integer;
BEGIN
pivot := points[start].X;
left := start + 1;
right := stop;
WHILE left <= right DO BEGIN
WHILE (left <= stop) AND (points[left].X < pivot) DO
left := left + 1;
WHILE (right > start) AND (points[right].X >= pivot) DO
right := right - 1;
IF left < right THEN
swap(points[left], points[right]);
END;
swap(points[start], points[right]);
Split := right
END;
PROCEDURE QuicksortRecur(start, stop: integer);
VAR
splitpt: integer;
BEGIN
IF start < stop THEN BEGIN
splitpt := Split(start, stop);
QuicksortRecur(start, splitpt-1);
QuicksortRecur(splitpt+1, stop);
END
END;
PROCEDURE Quicksort(size: Integer; VAR points: Coordsys);
BEGIN
QuicksortRecur(1, size)
END;
(*------------- end of quicksort ------------------*)
BEGIN
(*------------- input data -------------------*)
assign(input,'evripos.in');
reset(input);
readln(input,N);
N:=N+2;
points[1].X:=0;
points[1].Y:=0;
readln(input,points[N].X,points[N].Y);
FOR I := 2 TO N-1 DO
readln(input,points[I].X,points[I].Y);
close(input);
(*--------------- end of input ---------------------*)
(*-------- sorting coordinates by increasing X -----*)
Quicksort(N, points);
(*--------------------------------------------------*)
(*--- computing all minimum normal bitonic paths ---*)
FOR J := 2 TO N DO
FOR I := 1 TO J-1 DO
IF (I=1) AND (J=2) THEN
l[I,J] := dist(points[i],points[j])
ELSE IF J>I+1 THEN
l[I,J]:= l[I,J-1] + dist(points[J-1],points[J])
ELSE BEGIN
l[I,J] := INF;
FOR K := 1 TO I-1 DO BEGIN
q:= l[K,I] + dist(points[K],points[J]);
IF q < l[I,J] THEN
l[I,J]:= q;
END;
END;
(*------------------------------------------------*)
(*----- computing the shortest bitonic tour ------*)
d:= Round( l[n-1,n] + dist(points[n-1],points[n]));
(*------------------------------------------------*)
(*---------------- output data -------------------*)
assign(output,'evripos.out');
rewrite(output);
writeln(output,d);
close(output);
(*--------------- end of output ------------------*)
end.
Ouchdarksaga έγραψε:συγγνομι
Κώδικας: Επιλογή όλων
program evripos;
type CoordSet = record
x, y: Integer
end;
var Fi: TextFile;
i, j, tmp, N: Integer;
ans, dist: Array [1..203, 1..203] of Real;
Coord: Array [1..203] of CoordSet;
begin
Assign(Fi, 'evripos.in');
Reset(Fi);
ReadLn(Fi, N);
ReadLn(Fi, Coord[N+1].x, Coord[N+1].y);
for i:=1 to N do
ReadLn(Fi, Coord[i].x, Coord[i].y);
Close(Fi);
N := N+2;
Coord[N].x := 0;
Coord[N].y := 0;
for i:=1 to N do
for j:=1 to N do
if Coord[i].x > Coord[j].x then begin
tmp := Coord[i].x;
Coord[i].x := Coord[j].x;
Coord[j].x := tmp;
tmp := Coord[i].y;
Coord[i].y := Coord[j].y;
Coord[j].y := tmp;
end;
for i:=1 to N do
for j:=1 to N do begin
dist[i, j] := sqrt( (Coord[i].x-Coord[j].x)*(Coord[i].x-Coord[j].x) + (Coord[i].y-Coord[j].y)*(Coord[i].y-Coord[j].y) );
ans[i, j] := 99999999;
end;
ans[1, 1] := 0;
for i:=1 to N do
for j:=1 to N do begin
if ans[i+1, i] > ans[i, j]+dist[j, i+1] then
ans[i+1, i] := ans[i, j]+dist[j, i+1];
if ans[i+1, j] > ans[i, j]+dist[i, i+1] then
ans[i+1, j] := ans[i, j]+dist[i, i+1];
if ans[i+1, i+1] > ans[i, j]+dist[i, i+1]+dist[j, i+1] then
ans[i+1, i+1] := ans[i, j]+dist[i, i+1]+dist[j, i+1];
end;
Assign(Fi, 'evripos.out');
Rewrite(Fi);
WriteLn(Fi, Round(ans[N, N]));
Close(Fi);
Halt(0);
end.
αν καταλαβα βρισκει δυο διαδρομες παραλληλα μια για να παει και μια για να γυρισειstathis έγραψε: Βλέπω το πρόβλημα ως ένα επίπεδο που έχει δύο διαδρομές οι οποίες μόνο πηγαίνουν.
Το ans έχει ως indexes το που βρίσκεται η κάθε διαδρομή-σχοινί. Δηλαδή με ans[1][2] σημαίνει πως το ένα σχοινί είναι στο σημείο 1, και το δεύτερο στο σημείο δύο. Η τιμή που αποδίδεται σε αυτή την "κατάσταση" (DP state) είναι η συνολική διανυόμενη διαδρομή ως εκείνα τα σημεία. Επομένως, όταν φτάσει στο τελικό σημείο, η λύση μας βρίσκεται στο ans[N][N], εφόσον εκεί τερματίζει.
Είναι αρκετοί που δε το καταλαβαίνουν.darksaga έγραψε:lol
το ιδιο κανει