Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Δημοσιεύτηκε: Δευ Ιαν 24, 2011 11:38 pm
σε κάλυψε πλήρως ο compileGuyzaxeilasfc έγραψε:themi, exw valei tin lisi sou kai trexei edw kai 2 lepta me n=1.000.000
whats goin' on
Το επίσημο forum του ΠΔΠ
https://www.pdpforum.eu.org/forum/
σε κάλυψε πλήρως ο compileGuyzaxeilasfc έγραψε:themi, exw valei tin lisi sou kai trexei edw kai 2 lepta me n=1.000.000
whats goin' on
Πιστεύω πως δεν μπορώ να διαφωνίσω γιατί έχουν όλα μια βάση στην λογική της βελτίωσης της λύσης σου...kernelpanic έγραψε:Ηθικό δίδαγμα: Όταν ο διαθέσιμος χρόνος μετράται σε μήνες, οι χακιές επιβάλλονται
Κώδικας: Επιλογή όλων
#include<stdio.h>
int main(){
double N,M = 0,a,m=1e6;
scanf("%lf",&N);
while(N--)scanf("%lf",&a),m=(m<a)?m:a,M=(M>a/m)?M:a/m;
printf("%.3lf\n",M);}
Ήμουν έτοιμος να το δοκιμάσω αυτό χθες, αλλά λέω δεν βαριέσαι, πόση διαφορά μπορεί να έχει;kernelpanic έγραψε:Φόρτωσα όλο το αρχείο με μια εντολή fread και μετά το επεξεργάστηκα όπως ήταν. Ο χρόνος εκτέλεσης έγινε περίπου το 1/10 του αρχικού
Κι όμως, 1/10 του αρχικού. Και εγώ έτσι το έκανα.chris έγραψε:Ήμουν έτοιμος να το δοκιμάσω αυτό χθες, αλλά λέω δεν βαριέσαι, πόση διαφορά μπορεί να έχει;kernelpanic έγραψε:Φόρτωσα όλο το αρχείο με μια εντολή fread και μετά το επεξεργάστηκα όπως ήταν. Ο χρόνος εκτέλεσης έγινε περίπου το 1/10 του αρχικού
Τόση μεγάλη η διαφορά; Σκέφτηκα να το κάνω, αλλά μετά πίστεψα ότι δεν άξιζε η fread.madshockie έγραψε:Κι όμως, 1/10 του αρχικού. Και εγώ έτσι το έκανα.
Αμαρτία να ζητάς βοήθεια για την Α´ φάση.chris έγραψε:EDIT: Αχαχαχα, η δύναμη του google: Ένας skatoulis, κιάλλος ένας!
EDIT 2, τελευταίο:
Κάποιοι τα διέγραφαν κιόλας! Αλλά το google επιμένει
Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό??
Ναι αλλα το πρόβλημα ζητούσε για Ν=1.000.000...οπου ξεφεύγει αρκετά!chris έγραψε:Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό??
Γιατί μου φαίνεται τώρα βλακεία που χρησειμοποίησα πίνακα;;;;Πως δουλεύει ...;;; Ψάχνει την καλύτερη τιμή πώλησης και μετά την μικρότερη τιμή αγοράς μέχρι την τιμή πώλησης... Worst case 1000000 κάπως έτσι 1000...1000 999 1000 998 999 997 998..1 2 5'' σε windows..
Κώδικας: Επιλογή όλων
program PDP23;
var
pin:array[1..1000000] of integer;
max_p :real;
max,min:Integer;
all : Boolean;
fin,fout :Text;
x,i,orio_tel,sum: LongInt;
begin
assign (fin ,'profit.in');
reset (fin);
assign (fout ,'profit.out');
rewrite (fout);
readln (fin,sum);
For x:=1 to sum do
read (fin,pin[x]);
close(fin);
orio_tel:=1;
max_p:=0;
repeat
x:=orio_tel+1;
max:=pin[x];
for i:=orio_tel+2 to sum do
begin
if pin[i]>=max then
begin
max:=pin[i];
x:=i;
end;
end;
min:=max;
For i:=orio_tel to x-1 do
begin
If pin[i]<min THEN min:=pin[i];
end;
If max/min>max_p then
max_p:=max/min;
orio_tel:=x+1 ;
all:=FALSE;
i:=orio_tel;
while (i<sum) and (all=FALSE) do
begin
if pin[i]<min then all:=TRUE;
i:=i+1;
end;
until all=False;
writeln (fout,max_p:4:3);
close (fout);
halt(0)
end.
Είμαι σχεδόν βέβαιος πως τα testcases θα είναι έτσι μοιρασμένα ώστε να περνάς και με N^2...zaxeilasfc έγραψε:Ναι αλλα το πρόβλημα ζητούσε για Ν=1.000.000...οπου ξεφεύγει αρκετά!chris έγραψε:Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό??
Α΄ φάση είναιthanos713 έγραψε:Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
Βγήκαν τα αποτελέσματαchris έγραψε:Α΄ φάση είναιthanos713 έγραψε:Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
Εφ´ όσον δουλεύει ορθώς η λύση σου, χρησιμοποιήσε τα μέγιστα όρια.Memas έγραψε:Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ?
Αν είναι προβληματικός αλγόριθμος που όμως λύνει τα παραδείγματα, είναι πιθανό να κοπείς από % επιτυχίας(50% νομίζω για Β' Φάση).Memas έγραψε:Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ?
Κώδικας: Επιλογή όλων
#include <stdio.h>
#define MAXVAL 9999
unsigned long int N;
int min, max, max2, min2, tmp;
float ans; /* asnwer */
int main()
{
register unsigned long int i=0;
FILE *fin = fopen("profit.in", "r");
FILE *fout = fopen("profit.out", "w");
min = min2 = MAXVAL;
fscanf(fin, "%lu\n", &N);
for(i=0; i < N; i++)
{
fscanf(fin, "%d", &tmp);
if(tmp < min2) {
if(min > 0) {
min2 = tmp;
max2 = 0;
}
else
min = min2 = tmp;
}
else if(tmp >= max) {
max2 = max = tmp;
min = min2;
}
else if(min2 < min)
{
if( ((float)tmp / min2) > ((float)max / min) )
{
min = min2;
max = tmp;
}
}
}
if(max > min)
ans = (float)max / min;
else
ans = 1;
fprintf(fout, "%.3f\n", ans);
fclose(fin);
fclose(fout);
return 0;
}