B' Φάση 23ου ΠΔΠ

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

B' Φάση 23ου ΠΔΠ

Δημοσίευση από sotiris » Τρί Ιαν 11, 2011 9:04 pm

Ανακοινώθηκαν τα θέματα γυμνασίου-λυκείου σε δοκιμαστική έκδοση.
Δείτε εδώ
http://pdp.gr/files/23b/PDP_23_%CE%92_GYM.pdf
http://pdp.gr/files/23b/PDP_23_%CE%92_LYK.pdf
Εικόνα

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

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από chris » Τρί Ιαν 11, 2011 9:28 pm

Ωραία φένονται :)
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.

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

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από zaxeilasfc » Τετ Ιαν 12, 2011 2:14 am

απαιτώ το θέμα του γυμνασίου να αναφέρεται για το Χιονοδρομικό κέντρο Πηλίου :lol:

Καλές απαντήσεις... Ναι ωραία φαίνονται.!

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

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από chris » Τετ Ιαν 12, 2011 3:35 pm

ok. Ωραία φΑΙνονται.
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.

thanos713
Δημοσιεύσεις: 72
Εγγραφή: Τετ Αύγ 11, 2010 5:59 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από thanos713 » Τετ Ιαν 12, 2011 10:03 pm

ΛΟΛ, και σε είχα δει που το είχες με ε αλλά λέο άσ' τον... :lol: :lol:

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από kernelpanic » Τετ Ιαν 12, 2011 11:07 pm

Θέμα Γυμνασίου:
:?: Δεν καταλαβαίνω. :(

Θέμα Λυκείου:
Πολύ καλό, έχει διάφορες λύσεις :)
Αν και προσωπικά θα προτιμούσα 1-2 μηδενικά ακόμη στη μέγιστη τιμή του Ν :twisted:
Αλήθεια, αν 2 προϊστάμενες διευθύνουν άμεσα 2000 άντρες υπαλλήλους η καθεμιά, και η διευθύντρια διευθύνει άμεσα τις 2 προϊστάμενες, r_f=8000 και r_m=0, ή κάνω λάθος;
ΥΓ:
Και γιατί οι φυλετικές ανισότητες υπολογίζονται ως r_m-r_f και όχι ως |r_m-r_f| ή |r_f-r_m|; :P
ΥΓ2:
Συντρόφια ξεσηκωθείτε, η καταπίεση της εργατιάς απ'τη διευθύνουσα κεφαλαιούχα ελίτ δε ξεχωρίζει φύλο! :P
ΥΓ3:
διαφορά r_m -r_f .
Προσοχή, υποσυνείδητα μηνύματα! :shock:
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από sotiris » Πέμ Ιαν 13, 2011 12:12 am

kernelpanic έγραψε:Θέμα Γυμνασίου:
:?: Δεν καταλαβαίνω. :(

Θέμα Λυκείου:
Πολύ καλό, έχει διάφορες λύσεις :)
Αν και προσωπικά θα προτιμούσα 1-2 μηδενικά ακόμη στη μέγιστη τιμή του Ν :twisted:
Αλήθεια, αν 2 προϊστάμενες διευθύνουν άμεσα 2000 άντρες υπαλλήλους η καθεμιά, και η διευθύντρια διευθύνει άμεσα τις 2 προϊστάμενες, r_f=8000 και r_m=0, ή κάνω λάθος;
ΥΓ:
Και γιατί οι φυλετικές ανισότητες υπολογίζονται ως r_m-r_f και όχι ως |r_m-r_f| ή |r_f-r_m|; :P
ΥΓ2:
Συντρόφια ξεσηκωθείτε, η καταπίεση της εργατιάς απ'τη διευθύνουσα κεφαλαιούχα ελίτ δε ξεχωρίζει φύλο! :P
ΥΓ3:
διαφορά r_m -r_f .
Προσοχή, υποσυνείδητα μηνύματα! :shock:
Σχετικά με το απόλυτο |r_m-r_f| ή |r_f-r_m| όπως και να το γράψεις εξάλλου θα βγει θετικό και έτσι απορρίπτεις τις αρνητικές τιμές. Τώρα γιατί πρωτίμησαν το r_m -r_f , πραγματικά κανείς δεν μπορεί να απαντήσει ....
Spoiler: show
ρατσιμός! :lol:
Εικόνα

Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Virus•Hacker•Kontos » Πέμ Ιαν 13, 2011 12:25 am

Το προβλημα του λυκειου καλο μου φανηκε αλλα θα μου παρει πιστευω μερικες μερες μεχρι να το λυσω με μια ικανοποιητικη λυση...

Οσο για το προβλημα του γυμνασιου, δεν το διαβασα...
Spoiler: show
ΥΓ: Γιατι τα Μ@@@@@@ΣΜΕΝΑ windows δεν βαζουν τονο;;; (Και συμβενει μονο στον Firefox περιεργως...)
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.

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

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από chris » Παρ Ιαν 14, 2011 11:09 pm

Και εγώ δεν κατάλαβα το θέμα του Γυμνασίου στην αρχή. Αυτό που δεν λέει ξεκάθαρα, είναι πως όταν διαβάζεις στο αρχείο εισόδου πως ο αθλητής N είναι Μ-οστός, σημαίνει ότι είναι Μ-οστός μέχρι τώρα, δηλαδή M-οστός στους N πρώτους αθλητές. Εσύ στο τέλος πρέπει να βγάλεις την τελική κατάταξη :)
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.

BasilisP
Δημοσιεύσεις: 20
Εγγραφή: Σάβ Δεκ 04, 2010 9:09 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από BasilisP » Παρ Ιαν 14, 2011 11:31 pm

Πολύ ωραίο το πρόβλημα του λυκείου...το έλυσα, αλλά δεν νομίζω ότι είναι ικανοποιητική η πολυπλοκότητα, θέλει λίγη δουλειά ακόμα..

Το πρόβλημα του γυμνασίου δεν έχω προλάβει ακόμα να το κοιτάξω..

Καλή επιτυχία! :D

Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από compileGuy » Σάβ Ιαν 15, 2011 11:32 pm

Το θέμα του Λυκείου στην αρχη δεν καταλαβα καν τι ζητουσε . Ωστοσο μετα που το ξανακοίταξα φαίνεται αρκετα καλο :)

Θεμα Γυμνασιου No Clue :P

sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από sotiris » Κυρ Ιαν 16, 2011 12:05 am

Το θέμα του Λυκείου το έλυσα και εγώ , η καλύτερη λύση που μπορώ να σκεφτώ είναι NlogN . Μου φαίνεται δύσκολο να υπάρχει γραμμική λύση......
Εικόνα

Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Virus•Hacker•Kontos » Κυρ Ιαν 16, 2011 2:52 am

sotiris έγραψε:Το θέμα του Λυκείου το έλυσα και εγώ , η καλύτερη λύση που μπορώ να σκεφτώ είναι NlogN . Μου φαίνεται δύσκολο να υπάρχει γραμμική λύση......
Πιστεύω πως η "καλή" λύση μου (η καλύτερη απο τις 2 που σκέφτηκα), είναι γραμμική αλλά δεν ειμαι σιγουρος και είναι αρκετά δύσκολη στην υλοποίηση, αλλά μόλις τελείωσα την άλλη λύση (πιο εύκολη στην υλοποίηση, χειρότερη πολυπλοκότητα) που δυστυχώς ο χρόνης της στο 3ο πρόβλημα (Ν=10) είναι:

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

real	0m0.023s
user	0m0.000s
sys	0m0.004s
Spoiler: show
Δεν τυχαίνει να έχει κανείς χρόνο να φτιάξει έναν test generator να φανταστω...
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.

sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από sotiris » Κυρ Ιαν 16, 2011 12:10 pm

Virus•Hacker•Kontos έγραψε:
Spoiler: show
Δεν τυχαίνει να έχει κανείς χρόνο να φτιάξει έναν test generator να φανταστω...
Να ο test-case generator για το πρόβλημα του Λυκείου :) , αλλά δεν είμαι 100% σίγουρος ότι είναι σωστός :|

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

#include <cstdlib> 
#include <ctime> 
#include <iostream>
#define MAX 5000

using namespace std;

int i , temp , n , k , other;
char tmp;
bool place_zero;

int main(){ 
    FILE*fout=fopen("company.in","w");
    srand((unsigned)time(0)); 
    n = (rand()%MAX)+1;  
    
    fprintf(fout,"%d\n",n);
 
    for(int i=0; i<n; i++){ 
        temp = (rand()%n)+1; 
        k = (rand()%3)+1;
        other = (rand()%10)+1;
        if( k == 1 )
        tmp='m';
        else
        tmp ='f';
        
        if( (other == 5 && place_zero == false) || (i>(n/2) && place_zero == false ) ){
        place_zero = true;
        fprintf(fout,"0 %c\n",tmp);
        }else{
        fprintf(fout,"%d %c\n",temp,tmp);
        } 
    } 
    fclose(fout);
    return 0;
}

Εικόνα

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Κηπουρίδης » Κυρ Ιαν 16, 2011 5:28 pm

Ἐμένα γιὰ Ο ( Ν ) μὲ φαίνεται... γιὰ αὐτὸ καὶ μὲ παραξενεύει τὸ input ( γιὰ λύκειο ). Ἴσως γιὰ νὰ περνάει καὶ μὲ ἄλλον τρόπο πολλά... Ἀλλὰ καὶ μὲ Ο ( Ν^2 ) τὰ παιρνάει ὅλα!
Γυμνασίου πιὸ δύσκολο μὲ φαίνεται. Ο ( Ν ) best, 0 ( N^2 ) worst καὶ κόπηκα γιὰ 40.000 input :D
Εικόνα

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

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από zaxeilasfc » Κυρ Ιαν 16, 2011 7:13 pm

Μπορούμε να έχουμε ενα έγκυρο test generator? Θα ασχοληθώ και εγώ άμα δεν μπορεί κάποιος.

Btw... Ρε παίδες. Πως σας φαίνεται πιο δύσκολο ρε το θέμα Γυμνασίου? Προσωπικά το θεωρώ γελοίο.

Τώρα για το δικό μας θέμα το 'χω λύσει. (Ικανοποιητική λύση, θα σε πώ μετά πολυπλοκότητα. Αφού τελειώσω τον κώδικα). Θέλει πάντως καλύτερη διατύπωση.!

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Κηπουρίδης » Δευ Ιαν 17, 2011 12:55 am

zaxeilasfc έγραψε: Btw... Ρε παίδες. Πως σας φαίνεται πιο δύσκολο ρε το θέμα Γυμνασίου? Προσωπικά το θεωρώ γελοίο.
Γίνε πιὸ συγκεκριμένος. Σὲ Ο(Ν) τὸ ἔλυσες; Γιατί worst case O(N^2) μὲ 40.000 δεδομένα θὰ κάνεις 40.000*40.000=1.600.000.000 ποὺ εἶναι αἰσθητὰ μεγαλύτερο τοῦ 100.000.000 σὲ ἕνα δευτερόλεπτο. Ἔχεις κάτι καλύτερο νὰ προτείνεις;
Εικόνα

mr.muffin
Δημοσιεύσεις: 43
Εγγραφή: Σάβ Νοέμ 20, 2010 11:32 am

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από mr.muffin » Δευ Ιαν 17, 2011 3:13 pm

Πως θα ξερω οτι περασα την πρωτη φαση???

Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από Virus•Hacker•Kontos » Δευ Ιαν 17, 2011 4:33 pm

mr.muffin έγραψε:Πως θα ξερω οτι περασα την πρωτη φαση???
Θα το μαθουμε μολις τελειωσει η προθεσμια για της υποβολες, + ~ 1 εβδομαδα, μεχρι να βαθμολογηθουν ολες οι λυσεις. Υστερα θα βγουν τα αποτελεσματα (και πιθανο ειναι να παρεις και ενα email). Θα βγουν στο pdp.gr...

Αλλα επιπλεον αμα εισαι μεσα στο forum δεν υπαρχουν πολλες πιθανοτητες να μην το παρεις χαμπαρι...
Κηπουρίδης έγραψε:Ἐμένα γιὰ Ο ( Ν ) μὲ φαίνεται... γιὰ αὐτὸ καὶ μὲ παραξενεύει τὸ input ( γιὰ λύκειο ). Ἴσως γιὰ νὰ περνάει καὶ μὲ ἄλλον τρόπο πολλά... Ἀλλὰ καὶ μὲ Ο ( Ν^2 ) τὰ παιρνάει ὅλα!
Και εμενα μου φενεται περιεργο το input για να υλοποιηται ευκολα η γραμμικη λυση...
Ας ελπισουμε πως η τελικη εκδοση του προβληματος θα εχει το καταλληλο input για γραμμικη λυση...
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.

Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: B' Φάση 23ου ΠΔΠ

Δημοσίευση από compileGuy » Δευ Ιαν 17, 2011 4:34 pm

Θα τελειωση η Α φαση στις 23 Ιανουαρίου. Λίγες μέρες μετά οι επιτυχόντες θα ενημερωθούν με email , και τα συνολικά αποτελέσματα θα αναρτηθούν στο pdp.gr ;)

Απάντηση