σε κάλυψε πλήρως ο compileGuyzaxeilasfc έγραψε:themi, exw valei tin lisi sou kai trexei edw kai 2 lepta me n=1.000.000
whats goin' on
Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
-
- Δημοσιεύσεις: 170
- Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Πιστεύω πως δεν μπορώ να διαφωνίσω γιατί έχουν όλα μια βάση στην λογική της βελτίωσης της λύσης σου...kernelpanic έγραψε:Ηθικό δίδαγμα: Όταν ο διαθέσιμος χρόνος μετράται σε μήνες, οι χακιές επιβάλλονται
DFS Hole:
- Spoiler: show
-
- Δημοσιεύσεις: 14
- Εγγραφή: Παρ Δεκ 19, 2008 1:48 pm
- Τοποθεσία: Αθήνα
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Κώδικας: Επιλογή όλων
#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);}
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Ήμουν έτοιμος να το δοκιμάσω αυτό χθες, αλλά λέω δεν βαριέσαι, πόση διαφορά μπορεί να έχει;kernelpanic έγραψε:Φόρτωσα όλο το αρχείο με μια εντολή fread και μετά το επεξεργάστηκα όπως ήταν. Ο χρόνος εκτέλεσης έγινε περίπου το 1/10 του αρχικού
Και, BTW, πριν από την λήξη του διαγωνισμού κάποιος πανέξυπνος πόσταρε την λύση του στο pastebin! Δεν ήξερε μάλλον ότι όταν βάζεις κάτι public είναι public και στους crawlers του google . Είχα γελάσει πολύ εκείνη την μέρα που το βρήκα... Βέβαια η λύση είναι τελείως λάθος:
http://pastebin.com/KzfFMJxE
Τα credits για την ανακάλυψη πάνε στον sotiri! Επίσης είχα υποβάλει μία διόρθωση μέ ένα comment, αλλά το διέγραψε ο κ. Μυστήριος...
EDIT: Αχαχαχα, η δύναμη του google: Ένας skatoulis, κιάλλος ένας!
EDIT 2, τελευταίο:
Κάποιοι τα διέγραφαν κιόλας! Αλλά το google επιμένει
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
-
- Δημοσιεύσεις: 14
- Εγγραφή: Παρ Δεκ 19, 2008 1:48 pm
- Τοποθεσία: Αθήνα
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Κι όμως, 1/10 του αρχικού. Και εγώ έτσι το έκανα.chris έγραψε:Ήμουν έτοιμος να το δοκιμάσω αυτό χθες, αλλά λέω δεν βαριέσαι, πόση διαφορά μπορεί να έχει;kernelpanic έγραψε:Φόρτωσα όλο το αρχείο με μια εντολή fread και μετά το επεξεργάστηκα όπως ήταν. Ο χρόνος εκτέλεσης έγινε περίπου το 1/10 του αρχικού
- mariosal
- Δημοσιεύσεις: 63
- Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
- Τοποθεσία: Χολαργός, Ελλάδα
- Επικοινωνία:
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Τόση μεγάλη η διαφορά; Σκέφτηκα να το κάνω, αλλά μετά πίστεψα ότι δεν άξιζε η fread.madshockie έγραψε:Κι όμως, 1/10 του αρχικού. Και εγώ έτσι το έκανα.
Αμαρτία να ζητάς βοήθεια για την Α´ φάση.chris έγραψε:EDIT: Αχαχαχα, η δύναμη του google: Ένας skatoulis, κιάλλος ένας!
EDIT 2, τελευταίο:
Κάποιοι τα διέγραφαν κιόλας! Αλλά το google επιμένει
Όσο για το δεύτερο έμαθα αργότερα ότι εμφανίζεται παντού και το διέγραψα
- zaxeilasfc
- Δημοσιεύσεις: 118
- Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
- Τοποθεσία: Macintosh HD
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Ε είσαι λίγο έλεος αμα ζητάς βοήθεια για την πρώτη φάση..! Στις επόμενς τι θα κάνεις δηλαδή ?
Θα την κοιτάξω την λύση σου kernel ωραία φαίνεται!
Θα την κοιτάξω την λύση σου kernel ωραία φαίνεται!
- zaxeilasfc
- Δημοσιεύσεις: 118
- Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
- Τοποθεσία: Macintosh HD
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό??
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό??
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
- zaxeilasfc
- Δημοσιεύσεις: 118
- Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
- Τοποθεσία: Macintosh HD
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Ναι αλλα το πρόβλημα ζητούσε για Ν=1.000.000...οπου ξεφεύγει αρκετά!chris έγραψε:Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό??
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Γιατί μου φαίνεται τώρα βλακεία που χρησειμοποίησα πίνακα;;;;Πως δουλεύει ...;;; Ψάχνει την καλύτερη τιμή πώλησης και μετά την μικρότερη τιμή αγοράς μέχρι την τιμή πώλησης... 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.
- Spoiler: show
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Είμαι σχεδόν βέβαιος πως τα testcases θα είναι έτσι μοιρασμένα ώστε να περνάς και με N^2...zaxeilasfc έγραψε:Ναι αλλα το πρόβλημα ζητούσε για Ν=1.000.000...οπου ξεφεύγει αρκετά!chris έγραψε:Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό??
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Α΄ φάση είναιthanos713 έγραψε:Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Βγήκαν τα αποτελέσματαchris έγραψε:Α΄ φάση είναιthanos713 έγραψε:Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
http://www.pdp.gr/default.asp?pid=6&la=1&fid=1
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ?
- Spoiler: show
- mariosal
- Δημοσιεύσεις: 63
- Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
- Τοποθεσία: Χολαργός, Ελλάδα
- Επικοινωνία:
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Εφ´ όσον δουλεύει ορθώς η λύση σου, χρησιμοποιήσε τα μέγιστα όρια.Memas έγραψε:Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ?
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Αν είναι προβληματικός αλγόριθμος που όμως λύνει τα παραδείγματα, είναι πιθανό να κοπείς από % επιτυχίας(50% νομίζω για Β' Φάση).Memas έγραψε:Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ?
Αν το λύσεις ειδικά για τα παραδείγματα, μάλλον θα σε αποκλείσουν.
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.
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
1ον: Αρχαΐζοντες το πάτε φιρί φιρί για ολιγοήμερο banιο.
2ον: Θα δω τις δημοσιεύσεις του καθενός όταν γυρίσω Ρόδο
3ον: Νίκο πολύ κομψή η λύση σου
την έγραψα σε ένα βράδυ και την άφησα έτσι.
2ον: Θα δω τις δημοσιεύσεις του καθενός όταν γυρίσω Ρόδο
3ον: Νίκο πολύ κομψή η λύση σου
Κώδικας: Επιλογή όλων
#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;
}
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς
Τι βαθμολογία χρειάζεσαι για να περάσεις στην Β φάση;;;;;
- Spoiler: show