Σελίδα 2 από 3

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

Δημοσιεύτηκε: Δευ Ιαν 24, 2011 11:38 pm
από themis5
zaxeilasfc έγραψε:themi, exw valei tin lisi sou kai trexei edw kai 2 lepta me n=1.000.000
whats goin' on :?:
σε κάλυψε πλήρως ο compileGuy ;)

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

Δημοσιεύτηκε: Δευ Ιαν 24, 2011 11:39 pm
από Virus•Hacker•Kontos
kernelpanic έγραψε:Ηθικό δίδαγμα: Όταν ο διαθέσιμος χρόνος μετράται σε μήνες, οι χακιές επιβάλλονται :P
Πιστεύω πως δεν μπορώ να διαφωνίσω γιατί έχουν όλα μια βάση στην λογική της βελτίωσης της λύσης σου...

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 12:21 am
από 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);}
:|

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 12:35 am
από 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 επιμένει

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 1:05 am
από madshockie
chris έγραψε:
kernelpanic έγραψε:Φόρτωσα όλο το αρχείο με μια εντολή fread και μετά το επεξεργάστηκα όπως ήταν. Ο χρόνος εκτέλεσης έγινε περίπου το 1/10 του αρχικού :D
Ήμουν έτοιμος να το δοκιμάσω αυτό χθες, αλλά λέω δεν βαριέσαι, πόση διαφορά μπορεί να έχει; :P
Κι όμως, 1/10 του αρχικού. Και εγώ έτσι το έκανα. :arrow:

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

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

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

Όσο για το δεύτερο έμαθα αργότερα ότι εμφανίζεται παντού και το διέγραψα :P

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 1:25 am
από zaxeilasfc
Ε είσαι λίγο έλεος αμα ζητάς βοήθεια για την πρώτη φάση..! Στις επόμενς τι θα κάνεις δηλαδή ?

Θα την κοιτάξω την λύση σου kernel ωραία φαίνεται!

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 2:29 am
από zaxeilasfc
Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό?? :?:

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 4:03 pm
από chris
zaxeilasfc έγραψε:Ναι με κάλυψε πλήρως...! Δεν έκατσα να μελετήσω την πολυπλοκότητα σου αλλα φαίνεται να έχει δίκιο ο compileGuy.! Τέτοιες λύσεις περνάνε στον διαγωνισμό?? :?:
Φυσικά... Με N <= 3000 προλαβαίνεις άνετα σε χρόνο <1 sec.

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

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

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 4:15 pm
από 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.


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

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

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 4:57 pm
από thanos713
Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 6:32 pm
από chris
thanos713 έγραψε:Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
Α΄ φάση είναι ;)

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 6:44 pm
από pman
chris έγραψε:
thanos713 έγραψε:Άμα μαζευτούν πάρα πολλοί μπορεί και να μην περάσει η Ν^2...
Α΄ φάση είναι ;)
Βγήκαν τα αποτελέσματα
http://www.pdp.gr/default.asp?pid=6&la=1&fid=1

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 9:16 pm
από Memas
Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ? :D

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 9:38 pm
από mariosal
Memas έγραψε:Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ? :D
Εφ´ όσον δουλεύει ορθώς η λύση σου, χρησιμοποιήσε τα μέγιστα όρια.

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 10:07 pm
από kernelpanic
Memas έγραψε:Θέλω τη συμβουλή σας...Το πρόβλημα της Β φάσης εφόσον περάσω ...να το κάνω ειδικά για τα παραδείγματα ή γενικά μέχρι και για Ν=5000 ? :D
Αν είναι προβληματικός αλγόριθμος που όμως λύνει τα παραδείγματα, είναι πιθανό να κοπείς από % επιτυχίας(50% νομίζω για Β' Φάση).
Αν το λύσεις ειδικά για τα παραδείγματα, μάλλον θα σε αποκλείσουν.

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

Δημοσιεύτηκε: Τρί Ιαν 25, 2011 11:19 pm
από 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;
}
την έγραψα σε ένα βράδυ και την άφησα έτσι. :)

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

Δημοσιεύτηκε: Παρ Ιαν 28, 2011 4:23 pm
από Memas
Τι βαθμολογία χρειάζεσαι για να περάσεις στην Β φάση;;;;; :D