Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
themis5
Δημοσιεύσεις: 5
Εγγραφή: Δευ Ιαν 24, 2011 6:43 pm
Επικοινωνία:

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από themis5 »

zaxeilasfc έγραψε:themi, exw valei tin lisi sou kai trexei edw kai 2 lepta me n=1.000.000
whats goin' on :?:
σε κάλυψε πλήρως ο compileGuy ;)
Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από Virus•Hacker•Kontos »

kernelpanic έγραψε:Ηθικό δίδαγμα: Όταν ο διαθέσιμος χρόνος μετράται σε μήνες, οι χακιές επιβάλλονται :P
Πιστεύω πως δεν μπορώ να διαφωνίσω γιατί έχουν όλα μια βάση στην λογική της βελτίωσης της λύσης σου...
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.
madshockie
Δημοσιεύσεις: 14
Εγγραφή: Παρ Δεκ 19, 2008 1:48 pm
Τοποθεσία: Αθήνα

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από madshockie »

Κώδικας: Επιλογή όλων

#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);}
:|
Εικόνα
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από chris »

kernelpanic έγραψε:Φόρτωσα όλο το αρχείο με μια εντολή fread και μετά το επεξεργάστηκα όπως ήταν. Ο χρόνος εκτέλεσης έγινε περίπου το 1/10 του αρχικού :D
Ήμουν έτοιμος να το δοκιμάσω αυτό χθες, αλλά λέω δεν βαριέσαι, πόση διαφορά μπορεί να έχει; :P

Και, BTW, πριν από την λήξη του διαγωνισμού κάποιος πανέξυπνος πόσταρε την λύση του στο pastebin! Δεν ήξερε μάλλον ότι όταν βάζεις κάτι public είναι public και στους crawlers του google :). Είχα γελάσει πολύ εκείνη την μέρα που το βρήκα... Βέβαια η λύση είναι τελείως λάθος:

http://pastebin.com/KzfFMJxE

Τα credits για την ανακάλυψη πάνε στον sotiri! Επίσης είχα υποβάλει μία διόρθωση μέ ένα comment, αλλά το διέγραψε ο κ. Μυστήριος...

EDIT: Αχαχαχα, η δύναμη του google: Ένας skatoulis, κιάλλος ένας!

EDIT 2, τελευταίο:
Κάποιοι τα διέγραφαν κιόλας! Αλλά το google επιμένει
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
madshockie
Δημοσιεύσεις: 14
Εγγραφή: Παρ Δεκ 19, 2008 1:48 pm
Τοποθεσία: Αθήνα

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από madshockie »

chris έγραψε:
kernelpanic έγραψε:Φόρτωσα όλο το αρχείο με μια εντολή fread και μετά το επεξεργάστηκα όπως ήταν. Ο χρόνος εκτέλεσης έγινε περίπου το 1/10 του αρχικού :D
Ήμουν έτοιμος να το δοκιμάσω αυτό χθες, αλλά λέω δεν βαριέσαι, πόση διαφορά μπορεί να έχει; :P
Κι όμως, 1/10 του αρχικού. Και εγώ έτσι το έκανα. :arrow:
Εικόνα
Άβαταρ μέλους
mariosal
Δημοσιεύσεις: 63
Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
Τοποθεσία: Χολαργός, Ελλάδα
Επικοινωνία:

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από mariosal »

madshockie έγραψε:Κι όμως, 1/10 του αρχικού. Και εγώ έτσι το έκανα. :arrow:
Τόση μεγάλη η διαφορά; Σκέφτηκα να το κάνω, αλλά μετά πίστεψα ότι δεν άξιζε η fread.
chris έγραψε:EDIT: Αχαχαχα, η δύναμη του google: Ένας skatoulis, κιάλλος ένας!

EDIT 2, τελευταίο:
Κάποιοι τα διέγραφαν κιόλας! Αλλά το google επιμένει
Αμαρτία να ζητάς βοήθεια για την Α´ φάση.

Όσο για το δεύτερο έμαθα αργότερα ότι εμφανίζεται παντού και το διέγραψα :P
Άβαταρ μέλους
zaxeilasfc
Δημοσιεύσεις: 118
Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
Τοποθεσία: Macintosh HD

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από zaxeilasfc »

Ε είσαι λίγο έλεος αμα ζητάς βοήθεια για την πρώτη φάση..! Στις επόμενς τι θα κάνεις δηλαδή ?

Θα την κοιτάξω την λύση σου kernel ωραία φαίνεται!
Άβαταρ μέλους
zaxeilasfc
Δημοσιεύσεις: 118
Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
Τοποθεσία: Macintosh HD

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από zaxeilasfc »

Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό?? :?:
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από chris »

zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό?? :?:
Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Άβαταρ μέλους
zaxeilasfc
Δημοσιεύσεις: 118
Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
Τοποθεσία: Macintosh HD

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από zaxeilasfc »

chris έγραψε:
zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό?? :?:
Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.
Ναι αλλα το πρόβλημα ζητούσε για Ν=1.000.000...οπου ξεφεύγει αρκετά!
Memas
Δημοσιεύσεις: 87
Εγγραφή: Παρ Δεκ 31, 2010 4:13 pm
Επικοινωνία:

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από Memas »

Γιατί μου φαίνεται τώρα βλακεία που χρησειμοποίησα πίνακα;;;;Πως δουλεύει ...;;; Ψάχνει την καλύτερη τιμή πώλησης και μετά την μικρότερη τιμή αγοράς μέχρι την τιμή πώλησης... :D 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.

chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από chris »

zaxeilasfc έγραψε:
chris έγραψε:
zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό?? :?:
Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.
Ναι αλλα το πρόβλημα ζητούσε για Ν=1.000.000...οπου ξεφεύγει αρκετά!
Είμαι σχεδόν βέβαιος πως τα testcases θα είναι έτσι μοιρασμένα ώστε να περνάς και με N^2...
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
thanos713
Δημοσιεύσεις: 72
Εγγραφή: Τετ Αύγ 11, 2010 5:59 pm

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από thanos713 »

Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από chris »

thanos713 έγραψε:Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
Α΄ φάση είναι ;)
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από pman »

chris έγραψε:
thanos713 έγραψε:Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
Α΄ φάση είναι ;)
Βγήκαν τα αποτελέσματα
http://www.pdp.gr/default.asp?pid=6&la=1&fid=1
Memas
Δημοσιεύσεις: 87
Εγγραφή: Παρ Δεκ 31, 2010 4:13 pm
Επικοινωνία:

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από Memas »

Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ? :D
Άβαταρ μέλους
mariosal
Δημοσιεύσεις: 63
Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
Τοποθεσία: Χολαργός, Ελλάδα
Επικοινωνία:

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από mariosal »

Memas έγραψε:Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ? :D
Εφ´ όσον δουλεύει ορθώς η λύση σου, χρησιμοποιήσε τα μέγιστα όρια.
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από kernelpanic »

Memas έγραψε:Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ? :D
Αν είναι προβληματικός αλγόριθμος που όμως λύνει τα παραδείγματα, είναι πιθανό να κοπείς από % επιτυχίας(50% νομίζω για Β' Φάση).
Αν το λύσεις ειδικά για τα παραδείγματα, μάλλον θα σε αποκλείσουν.
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από thetrojan01 »

1ον: Αρχαΐζοντες το πάτε φιρί φιρί για ολιγοήμερο banιο.
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.
Memas
Δημοσιεύσεις: 87
Εγγραφή: Παρ Δεκ 31, 2010 4:13 pm
Επικοινωνία:

Re: Λύσεις Α´ Φάσεως ΚΓ´ Πανελληνίου Διαγωνισμοῦ Πληροφορικῆς

Δημοσίευση από Memas »

Τι βαθμολογία χρειάζεσαι για να περάσεις στην Β φάση;;;;; :D
Απάντηση